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....:)
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?
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.
Here's some imperative scala:
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....:)