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
No comments:
Post a Comment