Random walk. Finding a distribution

Question

Suppose that $\xi_1, \xi_2,..$ are independent copies of random variable $\xi$ having distribution $$\mathbb{P}(\xi=1)=\frac{1}{3}, \text{ } \mathbb{P(\xi=-1)=\frac{2}{3}}.$$

Define: $S_0=0$, $S_k=x_1+\xi_2+...+\xi_k,$ $k\geq 1,$

$\sigma_8 = \begin{cases} \min\{ 1 \leq k\leq 8 : S_k=0\} \\ 9 \text{ if } S _k \neq 0 \text{ for }1 \leq k \leq 8. \end{cases} $

Find distribution of random variable $\sigma_8$.

I have no examples how to solve this problem. I don't know how to start. I understand that I have $8$ steps to reach $0$ and I start from $0$.

I think I should do this:

$S_1=\xi_1$ and $$\mathbb{P}(S_1=1)=\mathbb{P}(\xi_1=1)=\frac{1}{3}$$ $$\mathbb{P}(S_1=-1)=\mathbb{P}(\xi_1=-1)=\frac{2}{3} $$

$S_1=\xi_1+\xi_2$ $$\mathbb{P}(S_2=0)=\mathbb{P}(\xi_1=1,\xi_2=-1)+\mathbb{P}(\xi_1=-1,\xi_2=1)=\frac{1}{3}*\frac{2}{3}+\frac{2}{3}*\frac{1}{3}=\frac{4}{9}$$.

I think $S_3\neq 0 $ so do I need to find only $S_4=0$,$S_6=0$ and $S_8=0$? Maybe there is shorter way to find it?

Answer 1

You can only return to the origin in even number of steps, so $P(\sigma_8=k)=0$ if $k$ is odd and $\neq 9$. $P(\sigma_8=2)=\frac 1 3 \frac 2 3$, $P(\sigma_8=4)=2(\frac 1 3 \frac 2 3)^{2}$ since the only possible routes here are $0\to 1\to 2\to 1\to 0$ and $0 \to -1\to -2 \to -1 \to 0$. Can you now compute $P(\sigma_8=6)$ and $P(\sigma_8=8)$? Note that $P(\sigma_8=9)=1-P(\sigma_8=2)-P(\sigma_8=4)-P(\sigma_8=6)-P(\sigma_8=8)$

Answer 2

We solve the more general problem of computing the distribution of $\sigma=\inf\{k\geqslant1\mid S_k=0\}$ in a more general setting, then we show that this answers your question.

Assume that $P(\xi=1)=p$ and $P(\xi=-1)=q$ with $q=1-p$, for some $p$ in $(0,1)$.

Then the Markov property at time $1$ shows that $\sigma=1+\sigma_\downarrow$ with probability $p$ and $\sigma=1+\sigma_\uparrow$ with probability $q$, where $\sigma_\downarrow$ denotes the first hitting time of $0$ starting from $1$ and $\sigma_\uparrow$ denotes the first hitting time of $0$ starting from $-1$.

Another application of the Markov property at time $1$ and the homogeneity of the transition probabilities of $(S_k)$, show that $\sigma_\downarrow=1$ with probability $q$ and $\sigma_\downarrow=1+\sigma_\downarrow'+\sigma_\downarrow''$ with probability $p$, where $\sigma_\downarrow'$ and $\sigma_\downarrow''$ are independent copies of $\sigma_\downarrow$.

Likewise, $\sigma_\uparrow=1$ with probability $p$ and $\sigma_\uparrow=1+\sigma_\uparrow'+\sigma_\uparrow''$ with probability $q$, where $\sigma_\uparrow'$ and $\sigma_\uparrow''$ are independent copies of $\sigma_\uparrow$.

In terms of generating functions, these decompositions translate as follows. Consider, for some fixed $|s|<1$, $$g=E(s^\sigma)\qquad g_\uparrow=E(s^{\sigma_\uparrow})\qquad g_\downarrow=E(s^{\sigma_\downarrow})$$ Then $$g=s(pg_\downarrow+qg_\uparrow)$$ while $$g_\downarrow=qs+ps(g_\downarrow)^2\qquad g_\uparrow=ps+qs(g_\uparrow)^2$$ Solving the latter yields $$g_\downarrow=\frac{1-\sqrt{1-4pqs^2}}{2ps}\qquad g_\uparrow=\frac{1-\sqrt{1-4pqs^2}}{2qs}$$ where one chooses the roots of the quadratics with a minus sign to guarantee that $g_\downarrow\leqslant1$ and $g_\uparrow\leqslant1$.

Finally, these formulas for $g_\downarrow$ and $g_\uparrow$ yield $$g=1-\sqrt{1-4pqs^2}$$ Thus, for every $k\geqslant1$,

$$P(\sigma=2k)=\frac2k\binom{2k-2}{k-1}(pq)^k$$

In terms of Catalan numbers (see here for quite a few first values), this reads $$P(\sigma=2k)=2C_{k-1}(pq)^k$$ The random time you consider is $$\sigma_8=\min\{9,\sigma\}$$ hence $P(\sigma_8=2k)=P(\sigma=2k)$ for every $k$ in $\{1,2,3,4\}$, that is, $$P(\sigma_8=2)=2pq\qquad P(\sigma_8=4)=2(pq)^2$$ $$P(\sigma_8=6)=4(pq)^6\qquad P(\sigma_8=8)=10(pq)^6$$ and $$P(\sigma_8=9)=1-\sum\limits_{k=1}^4P(\sigma=2k)$$