Let $\{S_k\}_{k\geq0}$, $S_0=0$ be a symmetric simple random walk. For an integer $n\geq1$, let $\tau_n=min\{k\geq1:S_k\notin(-n,n)\}$ be the first time k such that $S_k$ leaves the region $(-n,n)$, $n\geq1$ where $\tau_n=\infty$ if there is no such k. Find the moment generating function of $S_{\tau_n}$, $E[S_{\tau_n}]$ and $Var(S_{\tau_n})$.
If I can find the probability generating function of $S_{\tau_n}$, then I can find the expectation and variance of it. I tried to use conditional expectation. I got $E[e^{tS_{\tau_n}}|\tau_n]=(\frac{e^t+e^{-t}}{2})^{\tau_n}$. Since $E[e^{tS_{\tau_n}}]=E[E[e^{tS_{\tau_n}}|\tau_n]]$, to find $E[e^{tS_{\tau_n}}]$, I need to find the probability generating function of $\tau_n$ and that's where my problem starts. I tried to find its pmf first but couldn't succeed. Should I continue with this way or is there any other way?
Best Answer
In view of symmetry, $S_{\tau_n}$ has a very simple distribution: it is $n$ or $-n$ with probabilities $1/2$, so $$E[e^{S_{\tau_n}}] = \frac{e^{nt} + e^{-nt}}2 = \cosh nt. $$
If you want to find the pgf of $\tau_n$, denote by $E_m$ the expectation under the condition that $S_0 = m$. Then, clearly, $$f_m(z):= E_m[z^{\tau_n}] = \frac z2\big(f_{m-1}(z)+f_{m+1}(z)\big)\tag{1}$$ for $x\in(-n,n)$ and $f_{\pm n}(z) = 1$. Moreover, $f_{m}(z) = f_{-m}(z)$ by symmetry. Then, solving the recursion$^*$, we get $$f_{m}(z) = f_0(z)[x^m](1-x/z)(1-2x/z + x^2)^{-1},\ m\in[2,n],$$ where $[x^m]A(x)$ means the coefficient of $A$ before $x^m$. Thus, taking into account that $f_n(z) = 1$, $$ f_0(z) = \frac{1}{[x^n](1-x/z) (1-2x/z + x^2)^{-1}} $$ e.g. for $n=2$ $$ E[z^{\tau_n}] = \frac{1}{[x^2](1-x/z) (1-2x/z + x^2)^{-1}} = \frac{z^2}{2-z^2}, $$ which can be confirmed using a simple counting.
Naturally, it is possible to write $E[z^{\tau_n}]$ explicitly by expanding $(1-2x/z + x^2)^{-1}$.
$^*$In order to solve it, consider the generating function $F(x,z) = \sum_{m=0}^n f_m(z)x^m$. Then the recurrence (1) translates to $$ F(x,z) = (2x/z-x^2)F(x,z) + 1-x/z. $$