(p + q ’ 1)! 11

’

=

(p ’ 1)!(q ’ 1)! q p

p ’ q (p + q)!

—

=

p+q p!q!

x

= Nn,x QED

n

The reason that this lemma is called the Ballot Theorem is that it asserts that if

candidate P gets p votes, and candidate Q gets q votes in an election where the

probability of each vote is independently 1 , then the probability that throughout

2

the counting there are more votes for P than for Q is given by

p’q

.

p+q

Here is our last lemma:

Lemma 4.4.3 The probability that from time 1 to time 2n the particle stays

strictly positive is given by 1 u2n . In symbols,

2

1

Prob {S1 > 0, . . . , S2n > 0} = u2n . (4.14)

2

So

Prob {S1 = 0, . . . , S2n = 0} = u2n . (4.15)

Also

Prob {S1 ≥ 0, . . . , S2n ≥ 0} = u2n . (4.16)

Proof. By considering the possible positive values of S2n which can range from

98 CHAPTER 4. SPACE AND TIME AVERAGES

2 to 2n we have

n

Prob {S1 > 0, . . . , S2n > 0} = Prob {S1 > 0, . . . , S2n = 2r}

r=1

n

’2n

(N2n’1,2r’1 ’ N2n’1,2r+1 )

=2

r=1

’2n

(N2n’1,1 ’ N2n’1,3 + N2n’1,3 ’ N2n’1,5 + · · · )

=2

= 2’2n N2n’1,1

1

= p2n’1,1

2

1

= u2n .

2

The passage from the ¬rst line to the second is the re¬‚ection principle,as in our

proof of the Ballot Theorem, from the third to the fourth is because the sum

telescopes. The p2n’1,1 on the next to the last line is the probability of ending

up at (2n ’ 1, 1) starting from (0, 0). The last equality is simply the assertion

that to reach zero at time 2n we must be at ±1 at time 2n ’ 1 (each of these has

equal probability, p2n’1,1 ) and for each alternative there is a 50 percent chance

of getting to zero on the next step. This proves (4.14). Since a path which

never touches the t’axis must be always above or always below the t’axis,

(4.15) follows immediately from (4.14). As for (4.16), observe that a path which

is strictly above the axis from time 1 on, must pass through the point (1, 1) and

then stay above the horizontal line s = 1. The probability of going to the point

(1, 1) at the ¬rst step is 1 , and then the probability of remaining above the new

2

horizontal axis is Prob {S1 ≥ 0, . . . , S2n’1 ≥ 0}. But since 2n ’ 1 is odd, if

S2n’1 ≥ 0 then S2n ≥ 0. So, by (4.14) we have

1

= Prob {S1 > 0, . . . , S2n > 0}

u2n

2

1

Prob {S1 ≥ 0, . . . , S2n’1 ≥ 0}

=

2

1

Prob {S1 ≥ 0, . . . , S2n’1 ≥ 0, S2n ≥ 0},

=

2

completing the proof of the lemma.

We can now turn to the proofs of the propositions.

Proof of Prop.4.4.1 To say that the last visit to the origin occurred at time

2k means that

S2k = 0

and

Sj = 0, j = 2k + 1, . . . , 2n.

By de¬nition, the ¬rst 2k positions can be chosen in 22k u2k ways to satisfy the

¬rst of these conditions. Taking the point (2k, 0) as our new origin, (4.15) says

that there are 22n’2k u2n’2k ways of choosing the last 2n ’ 2k steps so as to

99

4.4. THE ARC SINE LAW

satisfy the second condition. Multiplying and then dividing the result by 22n

proves Prop.4.4.1.

Proof of Prop.4.4.2. We consider paths of 2n steps and let b2k,2n denote the

probability that exactly 2k sides lie above the t’axis. Prop. 4.4.2 asserts that

b2k,2n = ±2k,2n .

For the case k = n we have ±2n,2n = u0 u2n = u2n and b2n,2n is the probability

that the path lies entirely above the axis. So our assertion reduces to (4.16)

which we have already proved. By symmetry, the probability of the path lying

entirely below the the axis is the same as the probability of the path lying

entirely above it, so b0,2n = ±0,2n as well. So we need prove our assertion for

1 ¤ k ¤ n’1. In this situation, a return to the origin must occur. Suppose that

the ¬rst return to the origin occurs at time 2r. There are then two possibilities:

the entire path from the origin to (2r, 0) is either above the axis or below the

axis. If it is above the axis, then r ¤ k ¤ n ’ 1, and the section of path beyond

(2r, 0) has 2k ’ 2r edges above the t’axis. The number of such paths is

1 2r

2 f2r 22n’2r b2k’2r,2n’2r

2

where f2r denotes the probability of ¬rst return at time 2r:

f2r = Prob {S1 = 0, . . . , S2r’1 = 0, S2r = 0}.

If the ¬rst portion of the path up to 2r is spent below the axis, the the remaining

path has exactly 2k edges above the axis, so n ’ r ≥ k and the number of such

paths is

1 2r

2 f2r 22n’2r b2k,2n’2r .

2

So we get the recursion relation

k n’k

1 1

1 ¤ k ¤ n ’ 1.

b2k,2n = f2r b2k’2r,2n’2r + f2r b2k,2n’2r (4.17)

2 2

r=1 r=1

1

Now we proceed by induction on n. We know that b2k,2n = u2k u2n’2k = 2

when n = 1. Assuming the result up through n ’ 1, the recursion formula (4.17)

becomes

k n’k

1 1

b2k,2n = u2n’2k f2r u2k’2r + u2k f2r u2n’2k’2r . (4.18)

2 2

r=1 r=1

But we claim that the probabilities of return and the probabilities of ¬rst return

are related by

u2n = f2 u2n’2 + f4 u2n’4 + · · · + f2n u0 . (4.19)