The theory of probability

  Introduction
  Foundation
  Calculating
  Presize definition
  Binomial distribution
  Hypergeometric distribution
  Combined events
  Inseparable events
  'Ion Saliu's Paradox'
  Combinatorics
  Markov Chains
  Random Walks
  Contacts

In the last several chapters, we have studied sums of random variables with the goal being to describe the distribution and density functions of the sum. In this chapter, we shall look at sums of discrete random variables from a different perspective. We shall be concerned with properties which can be associated with the sequence of partial sums, such as the number of sign changes of this sequence, the number of terms in the sequence which equal 0, and the expected size of the maximum term in the sequence.

We view the sequence of Xk's as being the outcomes of independent experiments. Since the Xk's are independent, the probability of any particular (finite) sequence of outcomes can be obtained by multiplying the probabilities that each Xk takes on the specified value in the sequence. Of course, these individual probabilities are given by the common distribution of the Xk's. We will typically be interested in probabilities for events involving the related sequence of Sn's. Such events can be described in terms of the Xk's, so their probabilities can be calculated using the above idea. There are several ways to visualize a random walk. One can imagine that a particle is placed at the origin in Rm at time n = 0. The sum Sn represents the position of the particle at the end of n seconds. Thus, in the time interval [n¡1; n], the particle moves (or jumps) from position Sn¡1 to Sn. The vector representing this motion is just Sn¡Sn¡1, which equals Xn. This means that in a random walk, the jumps are independent and identically distributed. If m = 1, for example, then one can imagine a particle on the real line that starts at the origin, and at the end of each second, jumps one unit to the right or the left, with probabilities given by the distribution of the Xk's. If m = 2, one can visualize the process as taking place in a city in which the streets form square city blocks. A person starts at one corner (i.e., at an intersection of two streets) and goes in one of the four possible directions according to the distribution of the Xk's. If m = 3, one might imagine being in a jungle gym, where one is free to move in any one of six directions (left, right, forward, backward, up, and down). Once again, the probabilities of these movements are given by the distribution of the Xk's. Another model of a random walk (used mostly in the case where the range is R1) is a game, involving two people, which consists of a sequence of independent, identically distributed moves. The sum Sn represents the score of the first person, say, after n moves, with the assumption that the score of the second person is ¡Sn. For example, two people might be °ipping coins, with a match or non-match representing +1 or ¡1, respectively, for the first player. Or, perhaps one coin is being ripped, with a head or tail representing +1 or ¡1, respectively, for the first player.

We shall first consider the simplest non-trivial case of a random walk in R1, namely the case where the common distribution function of the random variables Xn is given by

This situation corresponds to a fair coin being flipped, with Sn representing the number of heads minus the number of tails which occur in the first n tips. We note that in this situation, all paths of length n have the same probability, namely 2¡n. It is sometimes instructive to represent a random walk as a polygonal line, or path, in the plane, where the horizontal axis represents time and the vertical axis represents the value of Sn. Given a sequence f(Sng) of partial sums, we first plot the points (n; Sn), and then for each k < n, we connect (k; Sk) and (k+1; Sk+1) with a straight line segment. The length of a path is just the difference in the time values of the beginning and ending points on the path. The reader is referred to Figure. This figure, and the process it illustrates, are identical with the example, given in Chapter 1, of two people playing heads or tails.

We say that an equalization has occurred, or there is a return to the origin at time n, if Sn = 0. We note that this can only occur if n is an even integer. To calculate the probability of an equalization at time 2m, we need only count the number of paths of length 2m which begin and end at the origin. The number of such paths is clearly

Since each path has probability 2¡2m, we have the following theorem.

Theorem. The probability of a return to the origin at time 2m is given by

The probability of a return to the origin at an odd time is 0. 2 A random walk is said to have a first return to the origin at time 2m if m > 0, and S2k 6= 0 for all k <m. In Figure 12.1, the first return occurs at time 2. We define f2m to be the probability of this event. (We also define f0 = 0.) One can think of the expression f2m22m as the number of paths of length 2m between the points (0; 0) and (2m; 0) that do not touch the horizontal axis except at the endpoints. Using this idea, it is easy to prove the following theorem.

Theorem. For n > 1, the probabilities fu2kg and ff2kg are related by the equation