w******l 发帖数: 58 | 1 Given a 1-D random walk starting at 0, with equal probability of going +1 or
-1, what is the probability P(n) that after n steps the random walk stayed
above 0, never hitting 0? | a**m 发帖数: 102 | 2 1/2 - 1/2 * { Pr[S(n-1)=1] + 2 * Pr[S(n-1)>1] }.
or
stayed
【在 w******l 的大作中提到】 : Given a 1-D random walk starting at 0, with equal probability of going +1 or : -1, what is the probability P(n) that after n steps the random walk stayed : above 0, never hitting 0?
| J*****n 发帖数: 4859 | 3
I don't think so
my ans= 1/2*[1-2*Pr(S_{n-1}<=-1)]
S_{n}- accumulated sum of Binomial (n,1/2)
【在 a**m 的大作中提到】 : 1/2 - 1/2 * { Pr[S(n-1)=1] + 2 * Pr[S(n-1)>1] }. : : or : stayed
| a**m 发帖数: 102 | 4 you deal with the case of the S(n)=-1 and the case of S(n)<-1 in the same
way, which I think is wrong, because the former one doesn't need any
reflection principle to put the multiple 2, otherwise you overcount.
【在 J*****n 的大作中提到】 : : I don't think so : my ans= 1/2*[1-2*Pr(S_{n-1}<=-1)] : S_{n}- accumulated sum of Binomial (n,1/2)
| J*****n 发帖数: 4859 | 5
U r right, 3x.
【在 a**m 的大作中提到】 : you deal with the case of the S(n)=-1 and the case of S(n)<-1 in the same : way, which I think is wrong, because the former one doesn't need any : reflection principle to put the multiple 2, otherwise you overcount.
| a****9 发帖数: 418 | 6 \sum_{i=0}^{n/2}[ {n \choose i}* (n-2i)/n* /2^n]
i: number of stepping left
the term (n-2i)/n is from the Bertrand's Ballot problem
or
stayed
【在 w******l 的大作中提到】 : Given a 1-D random walk starting at 0, with equal probability of going +1 or : -1, what is the probability P(n) that after n steps the random walk stayed : above 0, never hitting 0?
| p*****k 发帖数: 318 | 7 by symmetry, attm's result could be further simplified to
(1/2) * { Pr[S(n-1)=1] + Pr[S(n-1)=0] },
so depends on whether n is odd or even, one gets:
(1/2)^n * C(n-1,floor[n/2])
this agrees exactly with apc999's result, as C(n,i) * [(n-i)-i]/n = C(n-1,i) - C(n-1,i-1), then terms with alternating signs get canceled when summed over from i=0 to floor[n/2].
(no surprise as the standard approach to the ballot problem is by reflection principle) |
|