Question

Consider a random walk on the discrete line in which the particle’s initial position is 0,
and the position increases by 1 in a step with the probability p and decreases by 1 in
a step with the probability q = 1 − p, independently over different time steps, where
0 < p < 1. Given an integer x > 0, what is the probability that the particle ever visits
the point of coordinate x?

I have no idea where to even begin. There is a mess of equations in the class notes, and he's offered a hint, but I'm unsure how they go together.

Answer 1

what's the hint ?

Answer 2

Hm. Yeah, that may be helpful, huh.

"We used the notation $S_1(1)$ for the probability the particle ever visits the region to the right. Moving to the right means moving from y to y + 1. To get from 0 to x, the particle must visit 0, 1, 2, ... x - 1, x"

Answer 3

After some crazy arithmetic I don't understand, he says \[S_1(1)=\frac{p}{q}\]

Answer 4

One of the "I don't understand" is \[\sqrt{1-4pq} = |p - q|\] .. Wat?

Answer 5

crap. \[S_1(z)=\frac{1-(1-4pqz^2)^{1/2}}{2qz}\]

Answer 6

To at least clarify one result, we have that

\(\begin{aligned}\sqrt{1-4pq} &= \sqrt{1-4p(1-p)}\\&= \sqrt{1-4p+4p^2}\\ &= \sqrt{(1-2p)^2}\\ &= \sqrt{(1-p -p)^2}\\&= \sqrt{(q-p)^2} \\ &= |p-q| \end{aligned}\)

Answer 7

Great. That makes sense! So obvious now.

Answer 8

I think you need to also specify how many steps are allowed, because if you allow infinitely many steps, the probability for reaching any x ccoordinate is 1

Answer 9

Yeah. I wonder if that's what he's looking for.

Answer 10

Maybe you could find the probability for visiting the value "x" at "nth" step,
then add the probabilities for \(n \in \mathbb{N}\)

Answer 11

I believe probability would be more like \(\left(\dfrac{p}{q}\right)^x\) if you hit each one in order of 1,2,.., x-1, x without moving to the left once...but that would just be too easy. XD

Answer 12

I'm not sure. This class drives me insane.

Answer 13

To reach the value "x" at "nth" step,
the particle must take (n+x)/2 moves to right and (n-x)/2 moves to left

that should allow you to cookup an expression for probability for particle to be at position x at nth step

Answer 14

since the events, moving left/right, are indpendent, we can simply add up all the different probabilities

Answer 15

What the ... The hint says the particle would move in 1, 2, ..., x - 1, x in that order. But that doesn't make sense. if x = 4, it could go 1, 2, 3, 2, 3, 4. To your point @ganeshie8

Answer 16

right, there are infinitely many ways to reach the point x if you are not fixing the "number of steps taken"

Answer 17

Alright. I think I have what I need. Thank you.

Answer 18

go through this if u can
http://physics.gu.se/~frtbm/joomla/media/mydocs/LennartSjogren/kap2.pdf

it derives below expression for the probability for the particle to be at coordinate m after N steps

Answer 19

Even better. Makes sense! Appreciate the help!