4 ms·

I think this is more slightly more on-topic as a reply here > Consider the integers from [0,1000]. Suppose a particle starts at position n. At discrete instant

by VMG 15y ago

I think this is more slightly more on-topic as a reply here > Consider the integers from [0,1000]. Suppose a particle starts at position n. At discrete instants of time t=0,1,2,…, the particle moves up or down with p=0.5. What is the probability that the particle reaches 0 before t=1000? The answer is 50%, right? I can't explain it properly, but my thinking is that the random walk is symmetric and 0 and 1000 should have equal weights. Maybe a good explanation is harder than the correct answer in this case.

yummyfajitas 15y ago
The particle doesn't necessarily start out in the middle.
- VMG 15y ago
  So the question is "How likely is for a particle to reach 0 or 1000 depending on the starting position"? Then I got the question wrong, thinking it was about the average likelihood for many particles.
mturmon 15y ago
The problem may have a simple answer, but 0.5 is not it, because the answer will be a function of n, the starting position. If n is near 0, the chance you hit zero before 1000 steps is larger. The keyword is "random walk hitting time".
dxbydt 15y ago
I believe the right answer is about 2.5% (0.0247) Here's some imperative scala: object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(1000) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<1000) z==0 }) println( reachedZero.count(_==true)*1.0d/simulations ) } } --- >scala particle 1000000 >0.024782 Some intuition: If there were only 2 positions {1,2}, and you picked 1 with probability 0.5, you could get to 0 by going down once with probability 0.5. Going up wouldn't help since you'd have to go down to be back at 1, at which point you've exhausted your chances. Suppose you picked 2 with probability 0.5, you'd have to go down twice consecutively to hit 0, which has a probability of 0.5^2. So overall, your probability is 0.5^2 + 0.5^3 = 0.375 You can try working it out with 3 positions & 3 turns, and suddenly its not so easy....:)
- bacr 15y ago
  Nice simulation work! Initially I thought this was a one dimensional random walk problem where the answer is a function of n (as other comments have pointed out). In that case, there (n choose k) paths that take k steps in a single direction of n total steps, and each occurs with p(0.5^n). In this problem we are given n, but not k. Given a starting point, we can easily calculate the probability of crossing 0. So my question is, how are you dealing with the initial condition?
  - dxbydt 15y ago
    The initial condition is assigned to you randomly, from the closed interval [1,1000]. Suppose there were [1,k] spots. You are assigned an intial value from [1,k] and you then have to reach 0 before time t=k. Here's my code to solve the general case object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random (2 to 1000).foreach(spots=>{ val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(spots) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<spots) z==0 }) val prob = reachedZero.count(_==true)*1.0d/simulations printf("%4d spots: %.4f\n",spots,prob ) }) } } >scala particle 1000000 2 0.3773 3 0.329 4 0.292 5 0.2714 6 0.2624 7 0.2428 8 0.2247 9 0.222 10 0.2157 .... So your chances drop from 37% to 21% as the interval expands to 10 spots. At 100 spots, its 8%. By 1000 spots, you have a meager 2.5% chance of crossing 0 before 1000 seconds.
theprettyllama 15y ago
I read this problem a few days ago and just decided to give it some thought now (I would love to know the correct solution). The answer will certainly be a function of n (because, for example, I could give you n = 1001 and that should have 0 probability whereas if I were to give you n = 1, that would have a very high probability). My first thought was to write out a recurrence relation f of n and k (where n is the current level and k is the number of moves left). From this, we get: f(n, k) = .5f(n-1, k-1) + .5f(n+1, k-1) with f(n, k) = 0 when n > k and f(0, k) = 1. So to solve this, we just take f(n, 1000) = [a rapidly exploding function]. Any thoughts?
- theprettyllama 15y ago
  I posted this to /r/math on reddit and got some very interesting insight. (http://www.reddit.com/r/math/comments/ryy5n/interesting_little_probability_question/ http://www.reddit.com/r/math/comments/ryy5n/interesting_litt...) It appears that a basic knowledge of stochastic processes is required to actually be able to solve this problem, so it's one of those things that are actually much more complicated than they first appear.

by VMG 15y ago

yummyfajitas 15y ago

The particle doesn't necessarily start out in the middle.

VMG 15y ago
So the question is "How likely is for a particle to reach 0 or 1000 depending on the starting position"? Then I got the question wrong, thinking it was about the average likelihood for many particles.

mturmon 15y ago

The problem may have a simple answer, but 0.5 is not it, because the answer will be a function of n, the starting position. If n is near 0, the chance you hit zero before 1000 steps is larger. The keyword is "random walk hitting time".

dxbydt 15y ago

I believe the right answer is about 2.5% (0.0247) Here's some imperative scala: object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(1000) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<1000) z==0 }) println( reachedZero.count(_==true)*1.0d/simulations ) } } --- >scala particle 1000000 >0.024782 Some intuition: If there were only 2 positions {1,2}, and you picked 1 with probability 0.5, you could get to 0 by going down once with probability 0.5. Going up wouldn't help since you'd have to go down to be back at 1, at which point you've exhausted your chances. Suppose you picked 2 with probability 0.5, you'd have to go down twice consecutively to hit 0, which has a probability of 0.5^2. So overall, your probability is 0.5^2 + 0.5^3 = 0.375 You can try working it out with 3 positions & 3 turns, and suddenly its not so easy....:)

bacr 15y ago
Nice simulation work! Initially I thought this was a one dimensional random walk problem where the answer is a function of n (as other comments have pointed out). In that case, there (n choose k) paths that take k steps in a single direction of n total steps, and each occurs with p(0.5^n). In this problem we are given n, but not k. Given a starting point, we can easily calculate the probability of crossing 0. So my question is, how are you dealing with the initial condition?
- dxbydt 15y ago
  The initial condition is assigned to you randomly, from the closed interval [1,1000]. Suppose there were [1,k] spots. You are assigned an intial value from [1,k] and you then have to reach 0 before time t=k. Here's my code to solve the general case object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random (2 to 1000).foreach(spots=>{ val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(spots) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<spots) z==0 }) val prob = reachedZero.count(_==true)*1.0d/simulations printf("%4d spots: %.4f\n",spots,prob ) }) } } >scala particle 1000000 2 0.3773 3 0.329 4 0.292 5 0.2714 6 0.2624 7 0.2428 8 0.2247 9 0.222 10 0.2157 .... So your chances drop from 37% to 21% as the interval expands to 10 spots. At 100 spots, its 8%. By 1000 spots, you have a meager 2.5% chance of crossing 0 before 1000 seconds.

theprettyllama 15y ago

I read this problem a few days ago and just decided to give it some thought now (I would love to know the correct solution). The answer will certainly be a function of n (because, for example, I could give you n = 1001 and that should have 0 probability whereas if I were to give you n = 1, that would have a very high probability). My first thought was to write out a recurrence relation f of n and k (where n is the current level and k is the number of moves left). From this, we get: f(n, k) = .5f(n-1, k-1) + .5f(n+1, k-1) with f(n, k) = 0 when n > k and f(0, k) = 1. So to solve this, we just take f(n, 1000) = [a rapidly exploding function]. Any thoughts?

theprettyllama 15y ago
I posted this to /r/math on reddit and got some very interesting insight. (http://www.reddit.com/r/math/comments/ryy5n/interesting_little_probability_question/ http://www.reddit.com/r/math/comments/ryy5n/interesting_litt...) It appears that a basic knowledge of stochastic processes is required to actually be able to solve this problem, so it's one of those things that are actually much more complicated than they first appear.