Today I wrote a document with a draft for a book. That said we will continue our discussion on Ballot theorem and probability from simple random walk. Ballot theorem was originally used with urns. Suppose that there is an urn with a azure balls and b black balls totalling n balls. A sequence of a balls when drawn has a uniform distribution. The ballot theorem originally proposed in 1887 posed a question this way. If there is such an urn and there is sampling without replacement what is the pro ability that the azure balls will lead the black ones for some positive finite and restricted draw. The problem was solved the same year and the probability was found to be (a-b)/n as long as a > b
Saturday, August 9, 2014
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)
Thursday, August 7, 2014
Today we will continue our discussion on counting paths in random walks. In the previous posts, we discussed the number of paths from (0,0) to (n,y) where y >= 0 and remain above the horizontal axis. We also counted the number of paths from (0,0) to (n,0) that remain above the horizontal axis. as well as the number of paths that start from (0, 0) and have length n and remain above the horizontal axis.
With the paths of length n that start at (0, 0) and remain above the horizontal axis, we showed that they represent the shaded region in the lower right half triangle above the horizontal axis. By reflection, the same holds true for below the horizontal axis. However, what we went ahead and in proving but did not conjecture apriori is that the paths of Ilength n starting at (0,0) that remain above the horizontal axis is the the sum of the paths of length n starting at (0, 0) and ending at (n, 0) both above and below the horizontal axis. When the shaded area is represented in the graph, we can see by symmetry and reflection how this is self-evident.
We will next look at probability calculations.
Since all paths of certain length have the same probability, we can translate the path counting formulae into corresponding probability formulae:
The probability distribution after n steps is as follows:
P0(Sn = y) = (n Choose (n+y)/2) times (2 ^ -n)
Pn (Sn = y | Sm = x) = ( n-m Choose ((n - m + y - x) / 2) times 2 ^ (-n+m)
These equations are written based on the definitions of the probability as a ratio of paths satisfying an event to the total possible paths as in a grid. We have introduced this in earlier posts. In particular with the above two equations if we take n as even, then
u (n) = P0 (Sn = 0) = (n Choose n/2) times 2 ^ (-n).
The proof is described as below :
For the first equation we take the fraction of the number of paths from (0,0) to (n, y ) to 2^n
For the second equation we take the fraction of the number of paths from (m, x) to (n, y) to 2 ^ ( n -m).
The number of paths between two points (m, x) and (n, y) is given by (n-m) Choose (n-m+y-x )/ 2 ^ (n-m)
Substituting m = 0 and x = 0 we get equation 1
The two equations are thus proved.
Courtesy : Konstantopoulous mcrw.pdf
With the paths of length n that start at (0, 0) and remain above the horizontal axis, we showed that they represent the shaded region in the lower right half triangle above the horizontal axis. By reflection, the same holds true for below the horizontal axis. However, what we went ahead and in proving but did not conjecture apriori is that the paths of Ilength n starting at (0,0) that remain above the horizontal axis is the the sum of the paths of length n starting at (0, 0) and ending at (n, 0) both above and below the horizontal axis. When the shaded area is represented in the graph, we can see by symmetry and reflection how this is self-evident.
We will next look at probability calculations.
Since all paths of certain length have the same probability, we can translate the path counting formulae into corresponding probability formulae:
The probability distribution after n steps is as follows:
P0(Sn = y) = (n Choose (n+y)/2) times (2 ^ -n)
Pn (Sn = y | Sm = x) = ( n-m Choose ((n - m + y - x) / 2) times 2 ^ (-n+m)
These equations are written based on the definitions of the probability as a ratio of paths satisfying an event to the total possible paths as in a grid. We have introduced this in earlier posts. In particular with the above two equations if we take n as even, then
u (n) = P0 (Sn = 0) = (n Choose n/2) times 2 ^ (-n).
The proof is described as below :
For the first equation we take the fraction of the number of paths from (0,0) to (n, y ) to 2^n
For the second equation we take the fraction of the number of paths from (m, x) to (n, y) to 2 ^ ( n -m).
The number of paths between two points (m, x) and (n, y) is given by (n-m) Choose (n-m+y-x )/ 2 ^ (n-m)
Substituting m = 0 and x = 0 we get equation 1
The two equations are thus proved.
Courtesy : Konstantopoulous mcrw.pdf
Wednesday, August 6, 2014
In this post, we continue our discussion on counting paths in single dimension simple random walks. Tonight we look at Catalan numbers. The number of paths from (0, 0) to (n, 0) that remain >= 0 is given by 1 / (n+1) times (n + 1) Choose (n/2)
How do we prove this? We take the formula we described in the previous post for finding the number of paths from (0,0) to (n, y), where y >= 0, that remain >= 0. And in this formula we substitute y=0
That number of paths was given by n Choose (n + Y) / 2 - n Choose (( n + y ) / 2 + 1)
And substituting y = 0 we get
N Choose n/2 - n Choose (n/2 - 1)
We can expand the definition of the combination n Choose r = n! / r! (N-r)!
And we will reduce the result to 1/(n+1) times (n+1) Choose n/2
We look at another corollary as well. The number of paths that start from (0,0), have length n, and remain non-negative is given by :
How do we prove this? We take the formula we described in the previous post for finding the number of paths from (0,0) to (n, y), where y >= 0, that remain >= 0. And in this formula we substitute y=0
That number of paths was given by n Choose (n + Y) / 2 - n Choose (( n + y ) / 2 + 1)
And substituting y = 0 we get
N Choose n/2 - n Choose (n/2 - 1)
We can expand the definition of the combination n Choose r = n! / r! (N-r)!
And we will reduce the result to 1/(n+1) times (n+1) Choose n/2
We look at another corollary as well. The number of paths that start from (0,0), have length n, and remain non-negative is given by :
(n Choose ceil(n/2)) where ceil(x) denotes the smallest integer that is just greater than or equal to x.
This is different from the other corollaries we have mentioned so far. This one talks about paths that have length n. We show that their number is (n Choose ceil(n/2)) this way.
We take the number of paths we computed earlier in this post for paths from (0,0) to (n,y) that don’t touch the horizontal axis as = n Choose (n+y)/2 - n Choose ((n+y)/2 + 1)
and then we sum over all y >= 0.
If n is even (2m) then we need to take y as even (2z) otherwise the formula above is equal to zero, and we have the number of desired paths
Sum z >= 0 ( 2m Choose (m+z) - 2m Choose (m+z+1))
which we can expand the series by listing each z >= 0 and summing it.
We will see that adjacent terms cancel out and we will get the result as the first term = 2m Choose m which is n Choose n/2
If n is odd (2m +1) then we need to take y as odd (2z + 1) otherwise the formula is again equal to zero, and we have
the number of paths from (0,0) to (2m+1, any) where paths remain above horizontal) =
Sum ( z >= 0 [ (2m + 1) Choose (m+z+1) - (2m + 1) Choose (m+z+2)]
and again we expand this series for each term z >= 0 , we see that the adjacent terms cancel out leaving us with only the first term as 2m+1 Choose m+1 which is
(n Choose ceil(n/2))
Tuesday, August 5, 2014
Today we will continue our discussion on path counting in random walks.
The number of paths from (m,x) to (n,y) that do not touch level z < min(x,y) is given by :
(n-m) Choose 1/2 (n-m+y-x) - (n-m) Choose (1/2(n-m-y-x)-z)
We prove it this way:
Here the relative positions of x and y with respect to z plays any role as compared to the equation we derived in the earlier post where we found the number of paths for level z = 0 or the horizontal axis. So we can take the relative distance the other way and state that
the number of paths between (m,x) to (n,y) that do not touch level z =
the number of paths between (m, x+z) to (n, y+z) that do not touch level 0 or horizontal axis.
which is equal to
(n-m) Choose 1/2(n-m+ y + z -x -z ) - (n-m) Choose 1/2 (n - m - y -z -x -z )
resulting in
(n-m) Choose 1/2 (n-m+y-x) - (n-m) Choose (1/2(n-m-y-x)-z)
Another corollary is that the number of paths from (0,0) to (n,y) where y >=0 , that remain >= 0 is given by
n Choose (n+y)/2 - n Choose ((n+y)/2 + 1)
We prove it this way:
The target number of paths is the same as the number of paths that do not touch level -1 and are above it
which is the same as
the number of paths between (0,1) and (n, y+1) that remain > 0
which we can write as
n Choose 1/2(n+y) - n Choose 1/2(n-y-1-1)
=n Choose 1/2(n+y) - n Choose (1/2(n-y) - 1)
Now we use the equation we derived at the beginning of this post for paths that do not touch level z < min(x,y) = -1
and rewrite the above as
n Choose 1/2(n+y) - n Choose (1/2 (n-y-1-1) - (-1))
The number of paths from (m,x) to (n,y) that do not touch level z < min(x,y) is given by :
(n-m) Choose 1/2 (n-m+y-x) - (n-m) Choose (1/2(n-m-y-x)-z)
We prove it this way:
Here the relative positions of x and y with respect to z plays any role as compared to the equation we derived in the earlier post where we found the number of paths for level z = 0 or the horizontal axis. So we can take the relative distance the other way and state that
the number of paths between (m,x) to (n,y) that do not touch level z =
the number of paths between (m, x+z) to (n, y+z) that do not touch level 0 or horizontal axis.
which is equal to
(n-m) Choose 1/2(n-m+ y + z -x -z ) - (n-m) Choose 1/2 (n - m - y -z -x -z )
resulting in
(n-m) Choose 1/2 (n-m+y-x) - (n-m) Choose (1/2(n-m-y-x)-z)
Another corollary is that the number of paths from (0,0) to (n,y) where y >=0 , that remain >= 0 is given by
n Choose (n+y)/2 - n Choose ((n+y)/2 + 1)
We prove it this way:
The target number of paths is the same as the number of paths that do not touch level -1 and are above it
which is the same as
the number of paths between (0,1) and (n, y+1) that remain > 0
which we can write as
n Choose 1/2(n+y) - n Choose 1/2(n-y-1-1)
=n Choose 1/2(n+y) - n Choose (1/2(n-y) - 1)
Now we use the equation we derived at the beginning of this post for paths that do not touch level z < min(x,y) = -1
and rewrite the above as
n Choose 1/2(n+y) - n Choose (1/2 (n-y-1-1) - (-1))
In the previous post, we discussed a path counting technique in a simple symmetric random walk in one dimension. We said that we can compute the probability of an event described by elements in a sample space by counting paths that make up the event and representing it as a fraction of all the possible paths. As an example, we took a grid with unit distance squares and the path as a sequence of + or -1. Taking the initial position S0 = 0 and a choice of other positions, we have an event. We then draw all the paths and take the ratio with 2^n paths because there are that many elements in the space.
We next looked at the number of paths that start from a specific position and end at another specific position. We represented it as a combination in terms of x and y axis displacement in the sample space
In today's post we continue the discussion on paths that start and end at specific points (m, x) and (n,y) and and do not touch the horizontal axis at all. The number of such paths is given by
(n-m) Choose 1/2(n-m+y-x) - (n-m) Choose 1/2 (n-m-y-x).
Such paths cover a shaded region that lie above the horizontal axis in the sample space grid/graph. Consider a path that does touch the horizontal axis From the point where it touches the horizontal axis, let us consider a path that we get based on reflection of this path. If we know the reflected path, we can find the original path. So we can count the number of reflected paths. Each reflected path starts from (m,x) but ends at (n,-y) so we substitute -y in place of y in the general case as (n-m)Choose 1/2(n-m-y-x).
Now we can find the number of paths that don't touch zero as the difference between the total number of paths for all x, y > 0 and the count of all reflected paths.
This gives us the formula (n-m) Choose 1/2(n-m+y-x) - (n-m) Choose 1/2 (n-m-y-x)
For a special case where we look at the paths from {1,1} to (n,y) where any y > 0 and the path doesn't touch the horizontal axis. Here we can show that the number of such paths is y Choose n times the total number of paths between {0,0} and {n,y} by substituting m =1 x = 1 in the formula above.
We next looked at the number of paths that start from a specific position and end at another specific position. We represented it as a combination in terms of x and y axis displacement in the sample space
In today's post we continue the discussion on paths that start and end at specific points (m, x) and (n,y) and and do not touch the horizontal axis at all. The number of such paths is given by
(n-m) Choose 1/2(n-m+y-x) - (n-m) Choose 1/2 (n-m-y-x).
Such paths cover a shaded region that lie above the horizontal axis in the sample space grid/graph. Consider a path that does touch the horizontal axis From the point where it touches the horizontal axis, let us consider a path that we get based on reflection of this path. If we know the reflected path, we can find the original path. So we can count the number of reflected paths. Each reflected path starts from (m,x) but ends at (n,-y) so we substitute -y in place of y in the general case as (n-m)Choose 1/2(n-m-y-x).
Now we can find the number of paths that don't touch zero as the difference between the total number of paths for all x, y > 0 and the count of all reflected paths.
This gives us the formula (n-m) Choose 1/2(n-m+y-x) - (n-m) Choose 1/2 (n-m-y-x)
For a special case where we look at the paths from {1,1} to (n,y) where any y > 0 and the path doesn't touch the horizontal axis. Here we can show that the number of such paths is y Choose n times the total number of paths between {0,0} and {n,y} by substituting m =1 x = 1 in the formula above.
Monday, August 4, 2014
In this post, we will describe path counting using simple symmetric random walk in dimension 1. In this random walk there is equal probability to go forward or backward in one dimension. When the walk starts from zero, we can describe it as sum of 1 to n i.i.d random variables each with a probability of 1/2. This is a vector with values likely between -1,1 taken n times and each are equally likely. Since there are 2^n elements in {0,1} ^ n, we have the probability distribution as P(E1 =e1, E2=e2, ... En=en) = 1/2 * 1/2 * 1/2 ... = as 1/(2^n)
We now say that the Events A that depend only on the first n i.i.ds are subsets of this space.
So if there are #A elements in this space, we have P(A) = #A/2^n.
Therefore, if we can count the number of elements of A, then we can compute its probability.
First, we assign to each initial position and to each sequence of n signs, a path of length n. We can construct a grid and trace this path as cartesian coordinates.
Now let us take an example where we have an Event on this graph/grid constituting of positions and we want to compute its probability.
Here is such an example : A = {S2 >= 0, S4 = -1, S6 < 0, S7 < 0}.
The paths comprising this event are shown below. We can count that there are six paths in A.
So P(A) = 6/2^6 = 6//128 = 3/64 which is approximately 0.047.
We have thus found probabilities by counting path.
Next we look at paths that start and end at specific points. The number of paths that start at one specific point (x,y) and end at another specific point (m,n) is given by (m - x) Choose ((m -x + n - y)/2).
Additionally, If we take the start as (0,0) and finish at (n,i) then if (n+i) is not an even number, then there is no path that starts from (0,0) and ends at (n, i). Hence the totat number of paths = n Choose (n+i)/2 which is equal to zero.
We now say that the Events A that depend only on the first n i.i.ds are subsets of this space.
So if there are #A elements in this space, we have P(A) = #A/2^n.
Therefore, if we can count the number of elements of A, then we can compute its probability.
First, we assign to each initial position and to each sequence of n signs, a path of length n. We can construct a grid and trace this path as cartesian coordinates.
Now let us take an example where we have an Event on this graph/grid constituting of positions and we want to compute its probability.
Here is such an example : A = {S2 >= 0, S4 = -1, S6 < 0, S7 < 0}.
The paths comprising this event are shown below. We can count that there are six paths in A.
So P(A) = 6/2^6 = 6//128 = 3/64 which is approximately 0.047.
We have thus found probabilities by counting path.
Next we look at paths that start and end at specific points. The number of paths that start at one specific point (x,y) and end at another specific point (m,n) is given by (m - x) Choose ((m -x + n - y)/2).
Additionally, If we take the start as (0,0) and finish at (n,i) then if (n+i) is not an even number, then there is no path that starts from (0,0) and ends at (n, i). Hence the totat number of paths = n Choose (n+i)/2 which is equal to zero.
Subscribe to:
Comments (Atom)