finding the generating function $\phi(s) = \mathbb{E}(s^{H_0})$.

Question

i just started the course of markov chains and i'm having a few problems with one of the excercises.

Let $Y_1,Y_2, \dots$ be i.i.d random variables with:

$\mathbb{P}(Y_1 = 1) = \mathbb{P}(Y_1 = -1) = \frac{1}{2}$ and set $X_0 = 1, X_n = X_0 + Y_1+ \cdots + Y_n$ for $n \geq0$. Further define:

$$H_0 = \inf\{n \geq0: X_n = 0\}$$

find $\phi(s) = \mathbb{E}(s^{H_0})$.

Know i know that for $0 \leq s < 1$ we have:

$$\phi(s) = \mathbb{E}(s^{H_0}) = \sum_{n<\infty} s^n \mathbb{P} (H_0 = n)$$

the most confusing part is how do i know when $X_n = 0$? The most logical thing to do here for me is to take $n = 1$, then $X_1 = X_0 + Y_1$ and $\mathbb{P}(X_1 = 0) = \mathbb{P}(X_0 = 1,Y_1 = -1) = \mathbb{P}(X_0 = 1)\mathbb{P}(Y_1 = -1) = \frac{1}{2}$

So is $\phi(s) = \frac{1}{2}s$?

Help would be appreciated :)

Kees

Answer 1

If $Y_1=-1$, then $X_1=0$ hence $H_0=1$. If $Y_1=1$, then $X_1=2$ hence $H_0=1+H'_0+H''_0$, where, in the RHS, $1$ accounts for the first step, $H'_0$ for the time to hit $1$ starting from $2$ and $H''_0$ for the time to hit $0$ starting from $1$. Thus, $H'_0$ and $H''_0$ are independent and distributed like $H_0$.

Turning to generating functions, this reads $$E(s^{H_0})=\frac12s+\frac12sE(s^{H_0})^2.$$ Solving the quadratics yields $$E(s^{H_0})=\frac{1\pm\sqrt{1-s^2}}s.$$ Finally, the LHS is $0$ when $s=0$ hence, for every $|s|\leqslant1$, $$E(s^{H_0})=\frac{1-\sqrt{1-s^2}}s=\frac{s}{1+\sqrt{1-s^2}}.$$

Answer 2

As $X$ can reach level $0$ only in and odd number of steps, we have $$\mathbb{E}[s^{H_0}] = \sum_{i\geq1}s^{2i-1}P(H_0=2i-1).$$ Then we note that: $$P(H_0=1) = \left(\frac{1}{2}\right)\cdot 1, $$ as there is only one path with $1$ step that first reaches level $0$ on the $1$-st step, and the probability of this path is $1/2$.

Similarly, we have: $$P(H_0=2i-1) = \left(\frac{1}{2}\right)^{2i-1}\cdot \frac{(2i-2)!}{i!(i-1)!}, $$ as there are $ \frac{1}{2i-1}\binom{2i-1}{i} = \frac{(2i-2)!}{i!(i-1)!}$ paths with $2i-1$ steps that first reach level $0$ on step $2i-1$ (this is an application of Ballot Theorem), and the probability of each of these paths is $\left(1/2\right)^{2i-1}$.

So, $$\mathbb{E}[s^{H_0}] = \sum_{i\geq1}\left(\frac{s}{2}\right)^{2i-1}\frac{(2i-2)!}{i!(i-1)!}.$$

The formula posted in the other answer can be Taylor expanded to show it coincides with this series:

$$\sqrt{1-x} = 1- \left(\sum_{i\geq 1}\left(\frac{1}{2}\right)^{2i-1}\frac{(2i-2)!}{(i!(i-1)!}x^i\right).$$