Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is to find a purely probabilistic proof of the following identity, valid for every integer $n\geqslant1$, where $(S_n)_{n\geqslant0}$ denotes a standard simple random walk:

$$ E[(S_n)^2;S_{2n}=0]=\frac{n}2\,P[S_{2n-2}=0]. $$

Standard simple random walk is defined as $S_0=0$ and $S_n=\sum\limits_{k=1}^nX_k$ for every $n\geqslant1$, where $(X_k)_{k\geqslant1}$ is an i.i.d. sequence such that $P[X_k=+1]=P[X_k=-1]=\frac12$.

Of course, the RHS of the identity is $$ \frac{n}{2^{2n-1}}\,{2n-2\choose n-1}. $$ For a combinatorial proof, see this MSE question and its comments.

For an accessible introduction to the subject, see the corresponding chapter of the Chance project.

share|improve this question
    
Here, are you using $\mathbb{E}[X; A]$ to denote the integral taken only over the subset $A$? –  Nicholas R. Peterson Jul 14 '13 at 13:38
3  
@nrpeterson Yes, $E[X;A]=E[X\mathbf 1_A]$. –  Did Jul 14 '13 at 21:28
2  
This is an interesting question... I'll do some thinking on it. –  Nicholas R. Peterson Jul 14 '13 at 21:36

1 Answer 1

up vote 17 down vote accepted
+250

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 added that does not use the identities).

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] \qquad [A]$$

INITIAL final step of the proof

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.

NEW final step of the proof

We have arrived at equation $[A]$.The issue 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] \qquad [B]$$

Equation $[B]$ is an improvement over eq. $[A]$ because, through probabilistic arguments, only $S_{2n-2}$ is now present in the RHS. This means that the two probabilities can be expressed as the probabilities of different values of the same binomial r.v. $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]$$

Again, 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}$$

share|improve this answer
1  
This is excellent. I rewrote marginally the post to avoid the conditioning/deconditioning steps, which (I think) were unnecessary. +1 of course. If no further answer is posted, I plan to "accept" this one in a while. –  Did Jan 9 at 8:32
    
Thank you. I do appreciate also the re-writing, I used the conditional framework only because I am a bit more familiar with it compared to the "censored" one - but it is now evident it wasn't necessary. –  Alecos Papadopoulos Jan 9 at 9:25
    
@Did An ex post bounty award is a very gratifying gesture, although you had already clearly stated your appreciation for this effort of mine. Thank you Did. –  Alecos Papadopoulos Jan 11 at 19:43
    
The bounty is well earned--although, to be honest, and as you stress yourself, the step from $P[S_{2n-2}=n-1]$ to $P[S_{2n}=n]$ uses a not "purely probabilistic" workaround. One can complete this step using the generating function of the first return time to $0$ and such, but the ways I see to do so are still all, at the moment, slightly artificial. –  Did Jan 12 at 16:09
    
@Did I added an alternative final step of the proof, a bit more probabilistic I think. –  Alecos Papadopoulos Jan 13 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.