Random 1D Walk with different step sizes.

[chrisphd]

I am interested in the following random walk scenario, where a walker starts at a defined position greater than 0, say A, and then makes a "decision" to walk to either walk "b steps to the right" or walk "c steps to the left." He will choose the first option with probability p, and the second option with probability (1-p). If the walker gets to position 0 he stops.

I wish to calculate:
- the expectation value of the walker's position after a total of n decisions.
- what happens as n approaches infinite?

 

[Borek]

How are things that you want to calculate related to the fact walker stops at 0 - seems to me like this is unrelated to the problem. But perhaps I am missing something.

Writing a program that will simulate the walker so that you can test it and find numerical solution should take an hour. Perhaps two.

At least that's what I did in the past when faced with a related problem. See http://onlinelibrary.wiley.com/doi/10.1002/elan.1140040603/abstract

 

[micromass]

How are things that you want to calculate related to the fact walker stops at 0 - seems to me like this is unrelated to the problem. But perhaps I am missing something.

It is not unrelated to the problem at all and could have a profound impact on the problem. For example, in the special case that b=c, the condition will take care that it the end, the walker almost always ends up in 0. If the walker does not stop at 0, then the walker would end up visiting every position an infinite number of time.

Anyway, this is a classical problem with stochastic processes. For example, the situation can be modeled using a Markov chain. Do you know Markov chains?? What would be the transition matrix in this case?

 

[chrisphd]

Not sure how I could use Markov chains because the transition matrix would have infinite dimensions.

 

[micromass]

Not sure how I could use Markov chains because the transition matrix would have infinite dimensions.

I don't really see that as a problem, it just makes the calculations more difficult.

 

[chrisphd]

Do you know the procedure for finding expectation value once I've determined a transition matrix?

 

[micromass]

Do you know the procedure for finding expectation value once I've determined a transition matrix?

It's been a long time ago since I've done such a thing. I'll have a look at it and answer later, if nobody else answered.

 

[Borek]

It is not unrelated to the problem at all and could have a profound impact on the problem. For example, in the special case that b=c, the condition will take care that it the end, the walker almost always ends up in 0. If the walker does not stop at 0, then the walker would end up visiting every position an infinite number of time.

OK. If so, for n approaching infinity, final position seems to be always zero and expected value of the displacement is -A.

Or am I wrong again?

 

[chrisphd]

My intuition would say that it is possible for the final position to approach infinite as n approaches infinite. For example, let's say b = 100000 and c = 1, and p = 90% and say A = 100. There is a 90% chance the walker will move 100000 units further from 0, and then only a 10% chance he will move a mere 1 unit back towards 0. I think in a situation like this, after many decisions, the walker will move further and further from 0.

 

[chiro]

Hey chrisphd.

You need to setup a transition matrix with an absorbing state at 0 and the other states relevant to where you are and how many steps you move.

For a finite n you can construct a matrix with the right values (it will be very sparse).

In terms of where it should end up at infinite steps, if you can show the system will always end up at the absorbent state then you have shown that the probability that you will eventually end up at 0 is 1 given enough time.

I would suggest apart from the sparse matrix approach that you try and construct a series expansion based on a binomial tree (which was suggested) and then see if you can use this finite summation in terms of n to evaluate your expression.

The summation would be based on difference equation in which you can take that and see if you can get something global for evaluating the expectation in terms of n.