probabilityrandom walkself-learning
Let $S_n= \sum_{i =1}^n X_i$ where $P(X_i = 1) = p < \frac{1}{2}; P(X_i= -1) = 1-p$ Assume $S_0 = 0$ and $M > 0$ Find the probability that $S_n$ ever reaches $M$.
My first question is am I calculating $P(S_n = M)$ or $P(S_n \ge M)$?
If the former it should be $P(S_n = M) =$ $ {n \choose (n+M)/2}p^{(n+M)/2}(1-p)^{(n-M)/2}$
But seems that maybe it is the latter I am after.
I don't know if what I will write is a "purely probabilistic proof" as the question requests, or a combinatorial proof, but Did should decide that. At the end I do use combinatorial identities (UPDATE 12-1-2014: an alternative final step of the proof has been found that does not use the identities. The initial final step is preserved at the end, in grey).
The LHS of the identity can be re-written as
$$E[(S_n)^2;S_{2n}=0] = E\left[\left(\sum_{i=1}^nX_i\right)^2 ; S_{2n}=0\right]=E\left[\sum_{i=1}^nX_i^2 + \sum_{i\neq j}X_iX_j ; S_{2n}=0\right]$$ hence $$E[(S_n)^2;S_{2n}=0]=E\left[\sum_{i=1}^nX_i^2 ; S_{2n}=0\right]+ E\left[\sum_{i\neq j}X_iX_j ; S_{2n}=0\right] $$
But $X_i^2=1$ almost surely for every $i$. Likewise, the distribution of $(X_i,X_j)$ conditionally on $S_{2n}=0$ does not depend on $i\ne j$ since the $X_i$s are i.i.d and $S_{2n}$ is a symmetric function of $(X_i)$. So we arrive at
$$E[(S_n)^2;S_{2n}=0] = nP[S_{2n}=0] +n(n-1)E\left(X_{2n-1}X_{2n}; S_{2n}=0\right)$$
The random variable $X_{2n-1}X_{2n}$ takes on the values $\{-1,1\}$. Let $q \equiv P[X_{2n-1}X_{2n}=-1; S_{2n}=0]$. Then $P[X_{2n-1}X_{2n}=1; S_{2n}=0]=P[S_{2n}=0]-q$ hence $$E\left(X_{2n-1}X_{2n};S_{2n}=0\right) = -1\cdot q + 1\cdot(P[S_{2n}=0]-q) = P[S_{2n}=0]-2q$$
Note that if $X_{2n-1}X_{2n}=-1$ then $X_{2n-1}+X_{2n} = 0$ and $S_{2n-2}=S_{2n}$, therefore $$q= P[S_{2n-2}=0,S_{2n}=0]= P[S_{2n-2}=0,X_{2n-1}+X_{2n} = 0]= \frac 12 P[S_{2n-2}=0]$$ the last equality being due to the fact that $S_{2n-2}$ and $X_{2n-1}+X_{2n}$ are independent and that $P[X_{2n-1}+X_{2n} = 0]= \frac 12$. So $$ E\left(X_{2n-1}X_{2n}; S_{2n}=0\right) =P[S_{2n}=0]-P[S_{2n-2}=0]$$
Inserting into the main expression and multiplying out we have
$$E[(S_n)^2;S_{2n}=0] = nP[S_{2n}=0] +n(n-1)\Big (P[S_{2n}=0] - P[S_{2n-2}=0]\Big) $$
$$=n^2P[S_{2n}=0] - n(n-1)P[S_{2n-2}=0] \tag{A}$$
Guided by what we want to prove, the issue now is to express $P[S_{2n}=0]$ in terms of $P[S_{2n-2}=0]$. We note that the event $\{S_{2n}=0\}$ can only occur and so has strictly positive probability, if and only if one of the following events occur:
1) $E_0 \equiv [\{S_{2n-2}=0\}\; \cap \{X_{2n-1}+X_{2n}= 0\}]$
2) $E_1 \equiv [\{S_{2n-2}=2\}\; \cap \{X_{2n-1}+X_{2n}= -2\}]$
3) $E_2 \equiv [\{S_{2n-2}=-2\}\; \cap \{X_{2n-1}+X_{2n}= 2\}]$
The events inside the brackets, if we look at them as elements of a $3\times 2$ matrix, are (pardon my language) ... "horizontally independent and vertically mutually exclusive". Combined these imply that $$P[S_{2n}=0] = P[E_0 \cup E_1 \cup E_2] = P[E_0] + P[E_1]+P[E_2]$$
while the "horizontal" independence implies that the joint probabilities can be separated as the product of the probabilities of the two events involved in each case. More over, by symmetry we have that $P[S_{2n-2}=-2]= P[S_{2n-2}=2]$, while
$P[X_{2n-1}+X_{2n}= 0]= 1/2 $ , $P[X_{2n-1}+X_{2n}= -2]= 1/4 $ , $P[X_{2n-1}+X_{2n}= 2]= 1/4$. Using all these results we arrive at
$$ P[S_{2n}=0] = \frac 12 P[S_{2n-2}=0] + \frac 12 P[S_{2n-2}=2]$$
Inserting this into equation $[A]$ we obtain
$$E[(S_n)^2;S_{2n}=0] = n^2\left( \frac 12 P[S_{2n-2}=0] + \frac 12 P[S_{2n-2}=2]\right) - n(n-1)P[S_{2n-2}=0] $$
$$\Rightarrow E[(S_n)^2;S_{2n}=0] = \frac n2 (2-n)P[S_{2n-2}=0] + \frac {n^2}2P[S_{2n-2}=2] \tag{B}$$
Equation $[B]$ is an improvement over eq. $[A]$ because, through probabilistic arguments, only $S_{2n-2}$ is now present in the RHS. Now, if we denote by $Y_k$ a binomial random variable with probability of success $1/2$, $Y_k = Bin(k,1/2)$, then, the probabilities related to $S_{2n-2}$ can be expressed in terms of $Y_{2n-2}$,
$$P[S_{2n-2}=0] = P[Y_{2n-2}=n-1],\;\; P[S_{2n-2}=2] = P[Y_{2n-2}=n]$$
It is then a natural step to use the probability generating function of $Y_{2n-2}$, which is
$$G_Y(z) = \left (\frac 12 +\frac 12z\right)^{2n-2}$$ while we have
$$P[S_{2n-2}=0] = P[Y_{2n-2}=n-1] = \frac 1 {(n-1)!}G_Y^{(n-1)}(0)$$ $$P[S_{2n-2}=2] = P[Y_{2n-2}=n] = \frac 1 {n!}G_Y^{(n)}(0)$$
where the superscript parentheses denote the order of derivative taken. But
$$G_Y^{(n)}(0) = (n-1)G_Y^{(n-1)}(0) = (n-1)\cdot[(n-1)!]P[Y_{2n-2}=n-1]$$
and so
$$P[S_{2n-2}=2] = P[Y_{2n-2}=n] = \frac {n-1}{n} P[Y_{2n-2}=n-1] = \frac {n-1}{n}P[S_{2n-2}=0]$$
Inserting this into equation $[B]$ we obtain
$$E[(S_n)^2;S_{2n}=0] = \frac n2 (2-n)P[S_{2n-2}=0] + \frac {n^2}2\frac {n-1}{n}P[S_{2n-2}=0] $$
$$\Rightarrow \frac n2P[S_{2n-2}=0] \cdot (2-n+n-1) = \frac n2P[S_{2n-2}=0]$$
which is what we wanted to prove. One could argue that the use of the probability generating function is too "algebraic" a step, and that in general, the moment we enter binomial distribution territory, combinatorics rage in the background -but at least now they rage only in the background.
--
And don't forget, on the side, rearranging the relations above we can obtain the conditional expectation
$$E[(S_n)^2 \mid S_{2n}=0] = \frac {n^2}{2n-1}$$
INITIAL final step of the proof (using combinatorial identities)
We have arrived at equation $[A]$.
Using $Y_k$ to denote a binomial random variable with probability of success $1/2$, $Y_k = B(k,1/2)$, the probabilities related to $S_n$ can be expressed as probabilities of binomial random variables, $$P[S_{2n}=0] = P[Y_{2n}=n],\qquad P[S_{2n-2}=0] =P[Y_{2n-2}=n-1]$$
Since we want at the end to have only $P[S_{2n-2}=0]$ present, we must somehow express $P[Y_{2n}=n]$ in terms of $P[Y_{2n-2}=n-1]$, and here is where I use the combinatorial identities, since one can arrive through them at
$$P[Y_{2n}=n] = \frac 1{2^{2n}}{2n \choose n} = \frac 12 \frac {2n-1}{n}\frac 1{2^{2n-2}}{2n-2 \choose n-1} = \frac {2n-1}{2n}P[Y_{2n-2}=n-1]$$
Reverting back to $S$- notation and inserting in the main expression, we have
$$E[(S_n)^2;S_{2n}=0] = n^2\frac {2n-1}{2n}P[S_{2n-2}=0] - n(n-1)P[S_{2n-2}=0]$$
$$=\frac{n}2\,P[S_{2n-2}=0]\Big (2n-1 - 2(n-1)\Big) = \frac{n}2\,P[S_{2n-2}=0]$$
which is what we wanted to prove. Maybe there are other ways to relate $P[S_{2n}=0]$ and $P[S_{2n-2}=0]$, but they currently escape me.
Best Answer
Let $q=1-p$.
Method 1:
Let $r_k$ be the probability that $S_n$ ever reaches $k$. Then also $r_k$ is the probability that $S_n$ with $S_0=c$ ever reaches $k+c$. Consequently:
$$r_k=pr_{k-1}+qr_{k+1}$$
so that $r_k=c_1 \left ( \frac{1 + \sqrt{1-4pq}}{2q} \right )^k+c_2 \left ( \frac{1-\sqrt{1-4pq}}{2q} \right )^k$, from the usual theory of linear recurrence relations with constant coefficients.
In order to go to zero as $k \to \infty$, the first term must be zero. And certainly $r_0=1$, so $c_2=1$, and now we are done.
Method 2:
Let $r$ be the probability that $S_n$ ever net-moves to the right by $1$. Then $r=p+qr^2$: either the process immediately moves right, or else it initially moves left and then net-moves right at least twice. Thus $r=\frac{1-\sqrt{1-4pq}}{2q}$. Then by the same logic that got us $r^2$, we conclude that the probability to ever net-move to the right by $M$ steps is $r^M$.
As a side remark about simplification, $\sqrt{1-4pq}=|2p-1|=1-2p$ since $p<1/2$, so in fact $\frac{1-\sqrt{1-4pq}}{2q}=\frac{p}{q}$ and $\frac{1+\sqrt{1-4pq}}{2q}=1$. You could've figured this out without using the quadratic formula on $qx^2+p=x$ like I did. Note the coefficients sum to zero (after moving them all to one side), so $1$ is a root, then note that the product of the roots is $p/q$, so the other one is $p/q$.