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.