Random 1D Walk with different step sizes.

  • Context: Undergrad 
  • Thread starter Thread starter chrisphd
  • Start date Start date
  • Tags Tags
    1d Random
Click For Summary

Discussion Overview

The discussion revolves around a random walk scenario where a walker makes decisions to move either a certain number of steps to the right or left with given probabilities. Participants explore the implications of the walker stopping at position 0, the calculation of expectation values after a series of decisions, and the behavior of the walk as the number of decisions approaches infinity.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant describes the random walk scenario, specifying the probabilities and step sizes involved.
  • Another participant questions the relevance of the walker stopping at position 0 to the calculations being proposed.
  • Some participants argue that the stopping condition at 0 is indeed significant, especially in cases where the step sizes are equal, suggesting it influences the final position of the walker.
  • There is a discussion about modeling the scenario using Markov chains, with one participant expressing concern about the transition matrix being infinite.
  • Another participant counters that an infinite transition matrix is not inherently problematic, though it complicates calculations.
  • Several participants inquire about the procedure for calculating expectation values once a transition matrix is established.
  • One participant proposes that as the number of decisions approaches infinity, the expected final position may always be zero, while another participant suggests that it could also diverge based on specific step sizes and probabilities.
  • A suggestion is made to construct a transition matrix with an absorbing state at 0 and to explore a series expansion based on a binomial tree for further analysis.

Areas of Agreement / Disagreement

Participants express differing views on the implications of the stopping condition at 0, the behavior of the walk as the number of decisions increases, and the use of Markov chains. There is no consensus on the final position of the walker as n approaches infinity.

Contextual Notes

The discussion includes assumptions about the probabilities and step sizes, as well as the implications of stopping at 0, which may not be fully resolved. The complexity of the transition matrix and the methods for calculating expectation values are also noted as potential limitations.

chrisphd
Messages
60
Reaction score
0
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?
 
Physics news on Phys.org
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
 
Borek said:
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?
 
Not sure how I could use Markov chains because the transition matrix would have infinite dimensions.
 
chrisphd said:
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.
 
Do you know the procedure for finding expectation value once I've determined a transition matrix?
 
chrisphd said:
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.
 
micromass said:
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?
 
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.
 
  • #10
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.
 

Similar threads

Undergrad Jump probability of a random walker
  • · Replies 11 ·
Replies
11
Views
2K
Graduate Will a random walk hit every point infinitely often?
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Random Walks in 2D: Recurrence of (a), (b), (c)
  • · Replies 6 ·
Replies
6
Views
4K
Undergrad Why Does Yₙ Converge to Zero for q < 1/2 in a Random Walk?
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Mean squared distance traveled by an unbiased random walker in 1-D?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Martingale, Optional sampling theorem
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Average number of times a random walk passes a point
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Particle clusters in a random lattice
  • · Replies 3 ·
Replies
3
Views
850
Graduate Are Random Walks with Different Step Sizes Identical in Brownian Motion Limit?
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Probability of a random walk reaching the point X; maximal c
  • · Replies 1 ·
Replies
1
Views
2K