Originally Posted by

**cryptic26** Questions on random walk. Pls hint to approach.

Let Xn n>= 1 be i.id Bernoulli random variables that take value +1 or -1 with probability = 0.5. All the Xs have zero mean and let S0 = 0.

Sn = Summation Xk ( k = 1, 2...n).

1) Let Un = P(Sn=0), what is the formula for Un.

Solution Attempt: Since Sn can be zero only if there are even number of variables and that there are equal number of 1 as there are equal number of -1.

Hence, P(Sn=0), when n= 2m = 2mCm * 2^(-2m).

And P(S2m+1 = 0 ) = 0, that is the sum can't be zero for odd n.

2). Now, let fn = P(S1 not zero, S2 not zero, ... Sn =0). That is fn = P (Sn = 0 for the first time at n). Also, f0 = 0. Find the explicit formula for fn.

Also, show that un = Summation (fk*u(n-k)) , k= 1,2... n. (where u(n-k) is "u subscript "n-k")

I would need help with the question 2. Thanks.