Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A marker is placed at zero on the number line and a fair coin is flipped. On each flip we move one unit to the right. If it lands on heads, the marker is moved one unit up. If it lands on tails, the marker is moved one unit down.

If the first flip is a head the marker goes to position A(1,1). If the second flip is a head the marker goes to position B(2,2). If the third flip is a tail the marker goes to C(3,1). So with each flip we move one unit to the right on the x axis, and +/- one unit on the y axis depending on the landing on the coin.

When the marker is stationed at 0, I know that it has a 50-50 chance of going to either 1 or -1. So in this simple case the probability is proportional to the distance traveled.

Do I still get to say the same thing about the probability of the marker going to 1 in raport to the probability of it going to -2? Can I now say that the marker has a 66,6% chance of going to 1 and a 33,3% chance of going to -2? (Remember that initially the marker is stationed at 0 and it can reach any of the two points in every possibile way. There are no conditions regarding how it gets there or how long it takes to get there)

What about 1 and -3? Can I say that when the marker is stationed at 0 it has a 25% chance of going to -3 and a 75% chance of going to 1?

In other words, just like the title says, are these probabilities proportional to the distance traveled in a random walk? If the raport between the distances is 3:1 is it correct to say that the probabilities have a raport of 1:3?

The second part of my question refers to the initial position of the marker. What if all the other initial conditions stay true, but the marker is initially placed at 0.2? I now know that I have a 50% chance of going to 1.2 and a 50% chance of going to -0,8. But what are the chances of getting to -1 and what are the chances of getting to 1? How does this change in initial position affects things? Do probabilities remain proportional to the distances? Since there is a raport of 1.2/0,8 between the two distances, can I conclude that the marker has 60% chances of getting to 1 and 40% chances of getting to -1? (60%/40% = 1,2/0,8)

share|improve this question

2 Answers 2

up vote 2 down vote accepted

The short answer: your intuition is mostly right. The long answer:

The magic word for the sort of problem you're interested in is martingales.

The key idea is this. Suppose you let $X_n$ denote the position of your walk at time $n$. Since you're equally likely to go to $+1$ and $-1$ at each step, on average, you don't move each step. To put it mathematically, if we condition on the first $n-1$ steps, the expected position at time $n$ is exactly your location at time $n-1$. We sometimes denote this by $$E(X_n | X_1, X_2, \dots, X_{n-1} ) = X_n.$$

If you think about this, this also means that for any fixed $n$ we also have $$E(X_n)=X_0.$$ All this is saying is that if you don't move an average at each step, you also don't move on average after $n$ steps.

On your walk question, though, we aren't stopping after a fixed number of steps. We're stopping after we hit one of the ends of our interval. What turns out to be true is that this "average" property still holds in this case: If we let $X_{stop}$ denote the value of $X$ when we stop, we have $$E(X_{stop})=X_0$$ This theorem (the so-called Optional Stopping Theorem) is less obvious than it looks -- for example, it's false if we replace, say "stop when we hit $1$ or $-3$" by "stop only when we hit $1$.

But if you assume it to be true, it pretty much answers all of your questions. For example, consider the "stop when you hit $1$ or $-3$" rule. If we denote by $p$ the probability you stop at $1$, we have $$0=X_0=E(X_{stop})=1 \times p + -3 \times (1-p),$$ Solving gives you $p=3/4$ as you expect. The one thing you need to be careful about is your finishing point. For example, if you start at $0.8$ and step left or right by $1$, then "stop when you hit $1$" really means "stop when you hit $1.8$" if you want it to make sense at all.

share|improve this answer
    
Thank you for your comments and link references. It's exactly what I was looking for. –  Cristian Nov 26 '11 at 18:55

When the marker is stationed at 0, I know that it has a 50-50 chance of going to either 1 or -1. So in this simple case the probability is proportional to the distance traveled.

This is only true after 1 coin flip. After 1 flip, there is an equal probability of landing on 1 or -1. After 2 flips, the probability of landing on either is 0. After 3 flips, the probability of landing on 3 is $.5^3$, the probability of landing on 2 is 0, the probability of landing on 1 is $3\cdot.5^3$, the probability of landing on 0 is 0, the probability of landing on -1 is $3\cdot.5^3$, the probability of landing on -2 is 0, and the probability of landing on -3 is $.5^3$. You can carry on doing this, the point is, the probability is completely dependent on how many steps you take (and will never be .5 again after more than 1 flip, since there are other possible outcomes at that point). The simple symmetric random walk in one dimension (which is what this is) is recurrent. Which means that after an infinite amount of steps we will have visited every state infinitely often.

Do I still get to say the same thing about the probability of the marker going to 1 in raport to the probability of it going to -2? Can I now say that the marker has a 66,6% chance of going to 1 and a 33,3% chance of going to -2? (Remember that initially the marker is stationed at 0 and it can reach any of the two points in every possibile way. There are no conditions regarding how it gets there or how long it takes to get there)

One of these is even while the other is odd. Which means they can never be reached after the same amount of steps. Again, since the symmetric simple random walk is recurrent, these states will be visited infinitely often. We can look at, the probability of being in state 1 after $x$ steps though. This can never be 66% though. After an even amount of flips the probability of being in state 1 is 0. After an odd amount it depends on the amount of steps, the exact probabilities can be determined using the Chapman-Kolmogorov equations.

What about 1 and -3? Can I say that when the marker is stationed at 0 it has a 25% chance of going to -3 and a 75% chance of going to 1?

In other words, just like the title says, are these probabilities proportional to the distance traveled in a random walk? If the raport between the distances is 3:1 is it correct to say that the probabilities have a raport of 1:3?

In short, no. Due to the reasons listed above.

The second part of my question refers to the initial position of the marker. What if all the other initial conditions stay true, but the marker is initially placed at 0.2? I now know that I have a 50% chance of going to 1.2 and a 50% chance of going to -0,8. But what are the chances of getting to -1 and what are the chances of getting to 1? How does this change in initial position affects things? Do probabilities remain proportional to the distances? Since there is a raport of 1.2/0,8 between the two distances, can I conclude that the marker has 60% chances of getting to 1 and 40% chances of getting to -1? (60%/40% = 1,2/0,8)

Given your problem description, when the initial state is not an integer then the integers lie outside of your state space. The marker always moves 1 up or 1 down. If you don't start at an integer value, you can never reach one in this manner. This directly implies the probabilities of ever reaching an integer value is 0.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.