Today we will continue our discussion with Ballot theorem. In the previous post we mentioned the theorem. In this post, we mention the conditional probabilities. Out of an urn with n balls the sampling followed a random walk. The probability that given S0 = 0 and Sn = y  > 0, the random walk never becomes zero up to time n was given by
Po ( S1  > 0 , S2 > 0 , ... Sn > 0  | Sn  = y )  = y/n
Now we say that if n,y are both positive or zero, and are both even or both odd then,
then the same probability is (y + 1) / 1/2 ( n + y ) + 1
In particular, if n is even,
            P0 (S1 >= 0, ... Sn >= 0 )  = 1 / (n/2) + 1
We use the corollary we discussed earlier to prove this :
The number of paths from (0,0) to (n,y)  that remain above the horizontal axis is given by
n Choose (n+y) / 2 - n Choose ((n+y)/2 + 1)
The number of paths from (0,0) to (n,y) = n Choose (n+y)/2
so the probability we are interested can be expressed as a conditional P0 (Sn >= 0, ..., Sn >= 0, Sn = y) / P0 (Sn = y)  =   The number of paths from (0,0) to (n,y) that remain above the horizontal axis   /   The total number of paths from (0,0) to (n,y)
 and by substituting the expressions from above for the number of paths and eliminating the common terms we prove the probability above.

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

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)

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

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 :

(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)) 

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))

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.