Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
Probability Theory and Stochastic Processes
Steven R. Dunbar
Mathematicians Only: prolonged scenes of intense rigor.
How many random walks with steps are there? Among those walks, how many are positive for all steps? How many are non-negative for all steps?
Recall that is a sequence of independent random variables which take values with probability and with probability . This is a mathematical model of a fair coin ﬂip game where a results from “heads” on the th coin toss and a results from “tails”. Let and be the number of heads and tails respectively in ﬂips. Then counts the diﬀerence between the number of heads and tails, an excess of heads if positive.
A common interpretation of this probability game is to imagine it as a random walk. That is, we imagine an individual on a number line, starting at some position . The person takes a step to the right to with probability and takes a step to the left to with probability and continues this random process. Then instead of the total fortune at any time, we consider the geometric position on the line at any time.
Create a common graphical representation of the game. A continuous piecewise linear curve in consisting of a ﬁnite union of segments of the form or where are integers is called a path. A path has an origin and an endpoint which are points on the curve with integer coordinates satisfying for all on the curve. We will say the length of the path is . (Note that the Euclidean length of the path is .) To each element (see Binomial Distribution.), we associate a path with origin and endpoint .
If and are two integers such that then the number of paths with origin and endpoint is zero if is odd and if is even. More generally, if , , and are integers such that and is even, then the number of paths with origin and endpoint is .
Proof. The case is trivial, so suppose . The proof will establish a one-to-one correspondence between paths with origin and endpoint that cross the horizontal line with paths with origin and endpoint . Translating each path of the ﬁrst type up by units, this is equivalent to showing that the number of paths with origin and endpoint crossing the -axis (call these paths of the ﬁrst type) equals the number of paths with origin and endpoint (call these paths of the second type). If is a path of the ﬁrst type, set to be the smallest such that . The path is a union of a path with origin and endpoint and a path with origin and endpoint . Then to each , we associate the path that is the union of with the reﬂection of across the -axis. The path is a path of the second type and the correspondence is one-to-one between the two sets of paths of each of the two types. □
Remark. The probability the random walk will end at after steps is
This is also the probability that in a coin-tossing game, the players will be tied at the end of tosses. The next corollary shows that this is double the probability that the walk remains positive for all steps, or equivalently that the Heads player in the coin-tossing game is always ahead.
Proof. Count the paths with origin and length strictly contained in the upper half plane. To obtain this, sum the number of paths from to that do not touch the -axis. There is only one path that connects the point to the point and this path does not return to the -axis. If , the number of paths connecting to the point that do not return to the -axis equals the number of paths connecting to the point minus the number of paths that do return to the -axis. The number of paths connecting to the point is . By the reﬂection principle the number of paths connecting to the point that return to the -axis equals the number of paths connecting the point to the point , which is .
Therefore, the number of paths with origin and length that are contained in the upper half-plane is
This sum telescopes to and
Remark. The probability the random walk will end at after steps is
This is also the probability that in a coin-tossing game, the players will be tied at the end of tosses. The next corollary show that this also equals the probability that the walk remains nonnegative for all steps, or that the losing player in the coin-tossing game is never ahead. Notice the diﬀerence between the previous corollary and the next corollary, the ﬁrst is about positive walks and the second is about nonnegative walks.
Proof. The proof shows that
The claim is that the number of paths with origin and length that are contained in the upper half plane with no return to the -axis equals the number of paths with origin and length that are contained in the upper half-plane including the -axis. The claim is true because there is a bijection between the sets of these two types of paths: We associate a path of the second type to each path of the ﬁrst type by removing the initial segment and translating the path unit left and unit down.
Note that is never zero. Then to each path with origin and length that is contained in the upper half-plane including the -axis, we can associate exactly two paths with length and length that are contained in the upper half-plane. To do this, we add a segment of length and slope or to the end of the path of length . Therefore, the cardinality of the event is twice the cardinality of the event . □
Remark. The ﬁnal corollary calculates the probability that one player is ahead until the last coin toss in the game, which ties the two players.
Proof. Count the paths with origin and endpoint that are contained in the open upper half-plane which does not include the -axis. In other words, count the paths with origin and endpoint that are contained in the open upper half-plane. This number equals the number of paths with origin and endpoint that touch the -axis at some point. The number of paths with origin and endpoint equals . By the reﬂection principle, the number of paths with origin and endpoint that touch the -axis equals the number of paths with origin and endpoint . The number is . Finally, it is easy to check that□
Remark. The corollaries imply the following combinatorial identity.
Proof. Count the number of paths with origin and endpoint in two diﬀerent ways. On one hand, the number of such paths is . On the other hand, the number of paths equals the number of paths with origin and endpoint plus the number of paths with origin and endpoint . The number of paths with origin and endpoint is . Next, for every path with origin and endpoint , there exists a minimum integer such that the path passes through . The number of paths from to is therefore equal to the sum for from to of the product of the number of paths with origin and endpoint that are contained in the lower half-plane and the number of paths with origin and endpoint . By the previous corollary, this implies the number of paths with endpoint and endpoint is
Considering all of the information above, we see that this equals
The second form follows from setting and using the fact that
Remark. Note that:
This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 10.3. [?].
The scripts generate trials of -step random walks. Each random walk is the sequence of cumulative sums from a sequence of coin ﬂips, embedded in a matrix walks to set the initial condition. Each random walk is examined for positive steps, creating a Boolean matrix findposwalks. The rows of the Boolean matrix are summed and rows with sum correspond to positive walks. Another comparison ﬁnds a Boolean vector poswalks corresponding to the positive walks. The sum of the Boolean vector poswalks gives the number of positive walks in the trials. Dividing by the number of trials gives the empirical probability of positive walks. This empirical probability is compared to the probability from the Positive Walks Theorem which is computed directly from the binomial coeﬃcient.
R script for Positive Walks Theorem..
Octave script for Positive Walks Theorem..
Perl PDL script for Positive Walks Theorem..
Scientiﬁc Python script for Positive Walks Theorem..
I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.
I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.
Information on this website is subject to change without notice.
Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1
Email to Steve Dunbar, sdunbar1 at unl dot edu
Last modiﬁed: Processed from LATEX source on September 24, 2014