Boundary value problem- Random Walker

[potatocake]

Homework Statement

A walker performs a random walk on the grid points from 0 to N. Each time he tosses a fair coin, he moves one step forward if it is a head otherwise he moves one step backward. The random walk stops when the walker is at either 0 or N. What is the probability that the walker ends up at 0 given that he begins at i?

Relevant Equations

let the probability of the walker at i point to be P_i , P_0 = 1, P_N =0

I want to solve this using difference equation. So I set up the general equation to be
P_i = 0.5 P_i+1 + 0.5 _i-1

I changed it to euler's form p_i = z
0.5z²-z+0.5 = 0
z = 1
since z is a repeated real root
I set up general formula
P_n = A(1)ⁿ+B(1)ⁿ
then
P₀ = A = 1
P_N = A+BN = 0 -> A= -BN

This gives a general formula
P_n = 1- 1/N *n

However, I have no idea how I can show the probability that the walker ends up at 0 given that he begins at i. would it still be 1?

 

[pasmith]

You've calculated P_n as the probability that the walker reaches 0 given that he is at position n, even if you didn't acutally define it that way. So you're done.

 

[haruspex]

let the probability of the walker at i point to be P_i , P_0 = 1, P_N =0

You can't define the probability of being at a particular point this way. There will be a probability of being at a particular point given having been at some other specified point some specified number of steps earlier.
Indeed, having set P₀ to 1 the probability of being anywhere else must be zero.
Since the problem specifies starting at 1, you can define P_k(n) as the probability of being at n after k steps. Then P₀(1)=1, etc.

But a more convenient approach is turn it around and let P_n be the probability of terminating at 0 given that we start at n. That avoids having to specify the number of steps. I think you'll find the algebra largely the same as you wrote.

since z is a repeated real root
I set up general formula
P_n = A(1)ⁿ+B(1)ⁿ

I think you left out a factor n on one term.

This gives a general formula
P_n = 1- 1/N *n

I assume you mean 1-n/N, but that does not give a probability distribution since it does not sum to 1.

 

[potatocake]

I assume you mean 1-n/N, but that does not give a probability distribution since it does not sum to 1.

Does that mean my general formula is wrong?

But a more convenient approach is turn it around and let Pn be the probability of terminating at 0 given that we start at n. That avoids having to specify the number of steps. I think you'll find the algebra largely the same as you wrote

Does that mean I have to get
P_n(0) ?

 

[haruspex]

Does that mean my general formula is wrong?

The entire method is wrong, as I indicated:

You can't define the probability of being at a particular point this way. There will be a probability of being at a particular point given having been at some other specified point some specified number of steps earlier.

That said, I suspect you landed on the right answer by sheer luck. This is why @pasmith thought you had got there.

Does that mean I have to get
P_n(0) ?

No, I may have confused you by completely redefining P. To avoid confusion I'll reword it:

a more convenient approach is to turn it around and let Q_n be the probability of terminating at 0 given that we start at n.

With this definition, what is the relationship between Q_n-1, Q_n and Q_n+1?

 

[potatocake]

With this definition, what is the relationship between Q_n-1, Q_n and Q_n+1?

I suppose it will form
Q_n = 0.5Q_n+1+0.5Q_n-1 ...?

then will the probability of terminating at 0 given that we start from 0 is
Q₀ = 1
and probability of terminating at 0 given that we start from N is
Q_N = 0.5Q_N+1 + 0.5Q_N-1??

Then how would I solve the differential equation? Through iterations? or using Euler's form?
If Q_N does not give me a constant value, I don't have boundary conditions.

 

[pasmith]

I suppose it will form
Q_n = 0.5Q_n+1+0.5Q_n-1 ...?

then will the probability of terminating at 0 given that we start from 0 is
Q₀ = 1
and probability of terminating at 0 given that we start from N is
Q_N = 0.5Q_N+1 + 0.5Q_N-1??

Then how would I solve the differential equation? Through iterations? or using Euler's form?
If Q_N does not give me a constant value, I don't have boundary conditions.

Q_N is constant: it's zero. That's one of your boundary conditions, the other being Q_0 = 1. You solved this recurrence relation correctly in your original post; your error was to describe P_n as "probability of being at n" rather than "probabilty of reaching 0 given being at n".