Random Walks: Understanding Probability and First Visits to a Specific Location

[Kate2010]

Homework Statement

I'm trying to revise for a probability exam in a few weeks and still getting really confused :( so I'd be really grateful for a push in the right direction:

Consider a random walker on f0; 1; 2g who moves as follows:
- if at 0, probability 1/2 of staying at 0 and 1/2 of moving to 1;
- if at 1, probability 1/2 of moving to 0 and 1/2 of moving to 2;
- if at 2, probability 1/2 of moving to 1 and 1/2 of staying at 2.

Let the location of the random walker after k steps be Xk. Let X0 = 0.

(a) Let N be the number of steps until the first visit to 1. Consider
p_k = P(N = k) and q_k = P(Xk = 1).

(i) Explain why p_k \geq q_k for all k > 0.
(ii) Calculate pk and qk for all k \geq 0. (Hint: show q_k+1 = 1/2(1-q_k)

Homework Equations

The Attempt at a Solution

i) It is asking me to explain why the probability that the walker takes k steps until the 1st visit to is less than or equal to the probability that the kth location of the walker is 1.

If the walker takesk steps until the 1st visit to 1 then his kth location is 1?

ii) I think I need to condition on something, I think the 1st step?

P(N=k | X0=0) = P(N=k| X0 = 0 and X1=0)P(X1=0) + P(N=k| X0 = 0 and X1=1)P(X1=1)
gives me p_k = 1/2 p_k + 1/2 p_k+1

P(Xk=1| X0=0) = P(Xk=1 | X0=0 and X1=0)P(X1=0) + P(Xk=1 | X0=0 and X1=1)P(X1=1)
gives q_k = 1/2 q_k+1 + 1/2 I think

This is not what I had to show?! Once I have the recurrence relations I think I can solve them.

Thanks :)

 

[lanedance]

this looks like a simple markov chain problem, as the probability of the next state is only dependent on the last state... are you working with Markov chains?

to get started, first draw a diagram, showing the 3 states & transistion probabilities between each

now how turning that into a 3x3 matrix, P, whose entries are conditional probabilities p_ij, with:
p_{ij} = P[X_n = x_i |X_{n-1} = x_j]
ie. p_ij = the probability if you start in state x_j, at the next step you will be in state x_i

 

[lanedance]

though thinking about it the transition matrix is useful & may be needed for part ii), but i think you can get through part i) with just a bit of thought... though if you do ii) first, i) falls out...

First hints for p_k... the probability for being in position 1 for the first time, at step k, will just be the multiplied probabilities of a transition out of zero at each time step, which should be relatively straightforward to write down...

 

[lanedance]

now for q_k... if you are in position 1 at step k-1, there is zero probability to be in pos 1 at the next step, whilst if you are in the others spots (0 or 2), then there is a probability of 1/2 to be at 1 in the next step...

now compare that with the probability to jump from 0 to 1 at each step for p_k...

if its still not making sense try writing down the matrix i suggested...