Today we discuss the Ballot theorem as an extension of the path counting and probability estimation in simple random walks that we have been discussing in previous posts. This theorem is stated as follows:
The probability that S0 = 0 and Sn = y > 0, the random walk never becomes zero upto time n is given by (y/n)
Its written as P0 ( S1 > 0, S2 > 0, ... Sn > 0 | Sn = y ) = y / n
We rephrase the left hand side of this equation as the ratio of the probability for (1,1) to (n,y) to be above the horizontal axis to the probability for (0,0 to (n,y) to be above the horizontal axis.
Substituting m = 1 x = 1 and m = 0 x = 0 for the two probabilities, we use the equation for
probability as the ratio of the count of paths between (m,x) to (n,y) as ( n - m) Choose ( n - m + y - x ) / 2 to the total possible paths as 2 ^ n.
and taking out the common terms in the expansion of the n Choose r as n!/ r!(n-r)! we get the result as (y/n)
The probability that S0 = 0 and Sn = y > 0, the random walk never becomes zero upto time n is given by (y/n)
Its written as P0 ( S1 > 0, S2 > 0, ... Sn > 0 | Sn = y ) = y / n
We rephrase the left hand side of this equation as the ratio of the probability for (1,1) to (n,y) to be above the horizontal axis to the probability for (0,0 to (n,y) to be above the horizontal axis.
Substituting m = 1 x = 1 and m = 0 x = 0 for the two probabilities, we use the equation for
probability as the ratio of the count of paths between (m,x) to (n,y) as ( n - m) Choose ( n - m + y - x ) / 2 to the total possible paths as 2 ^ n.
and taking out the common terms in the expansion of the n Choose r as n!/ r!(n-r)! we get the result as (y/n)
No comments:
Post a Comment