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