where the ∼ signi¬es that the ratio of the two sides tends to one as n tends to

in¬nity. For a proof of Stirling™s formula cf. [?]. Then

(2ν)!

= 2’2ν

u2ν

(ν!)2

√ 1

2ν+ 2 ’2ν

’2ν 2π(2ν) e

∼2 2ν+1 e’2ν

2πν

1

=√.

πν

The results we wish to prove in this section are

95

4.4. THE ARC SINE LAW

Proposition 4.4.1 We have

±2k,2n = u2k u2n’2k , (4.9)

so we have the asymptotic approximation

1

±2k,2n ∼ . (4.10)

k(n ’ k)

π

If we set

k

xk =

n

then we can write

1

±2k,2n ∼

σ(xk ). (4.11)

n

Thus, for ¬xed 0 < x < 1 and n su¬ciently large

√

.2

±2k,2n = arcsin x. (4.12)

π

k<xn

Proposition 4.4.2 The probability that in the time interval from 0 to 2n the

particle spends 2k time units on the positive side and 2n ’ 2k time units on

the negative side equals ±2k,2n . In particular, if 0 < x < 1 the probability

that the √

fraction k/n of time units spent on the positive be less than x tends to

2

π arcsin x as n ’ ∞.

Let us call the value of S2n for any given realization of the random walk, the

terminal point. Of course, the particle may well have visited this terminal point

earlier in the walk, and we can ask when it ¬rst reaches its terminal point.

Proposition 4.4.3 The probability that the ¬rst visit to the terminal point oc-

curs at time 2k is given by ±2k,2n .

We can also ask for the ¬rst time that the particle reaches its maximum

value: We say that the ¬rst maximum occurs at time l if

Sl+1 ¤ Sl , Sl+2 ¤ Sl , . . . S2n ¤ Sl . (4.13)

S0 < Sl , S1 < Sl , . . . Sl’1 < Sl ,

Proposition 4.4.4 If 0 < l < 2n the probability that the ¬rst maximum occurs

at l = 2k or l = 2k + 1 is given by 1 ±2k,2n . For l = 0 this probability is given

2

by u2n and if l = 2n it is given by 1 u2n .

2

Before proving these four propositions, let us discuss a few of their impli-

cations which some people ¬nd counterintuitive. For example, because of the

shape of the density, σ, the last proposition implies that the maximal accumu-

lated gain is much more likely to occur very near to the beginning or to the

end of a coin tossing game rather than somewhere in the middle. The third

proposition implies that the probability that the ¬rst visit to the terminal point

occurs at time 2k is that same as the probability that it occurs at time 2n ’ 2k

96 CHAPTER 4. SPACE AND TIME AVERAGES

and that very early ¬rst visits and very late ¬rst visits are much more probable

than ¬rst visits some time in the middle.

In order to get a better feeling for√ assertion of the ¬rst two propositions

the

2 1

let us tabulate the values of π arcsin x for 0 ¤ x ¤ 2 .

√ √

2 2

x π arcsin x x π arcsin x

0.05 0.144 0.30 0.369

0.10 0.205 0.35 0.403

0.15 0.253 0.40 0.236

0.20 0.295 0.45 0.468

0.25 0.333 0.50 0.500

This table, in conjunction with Prop. 4.4.1 says that if a great many coin tossing

games are conducted every second, day and night for a hundred days, then in

about 14.4 percent of the cases,the lead will not change after day ¬ve.

The proof of all four propositions hinges on three lemmas. Let us graph (by

a polygonal path) the walk of a particle. So a “path” is a broken line segment

made up of segments of slope ±1 joining integral points to integral points in the

plane (with the time or t’axis horizontal and the s’axis vertical). If A = (a, ±)

is a point, we let A = (a, ’±) denote its image under re¬‚ection in the t’axis.

Lemma 4.4.1 The re¬‚ection principle. Let A = (a, ±), B = (b, β) be points

in the ¬rst quadrant with b > a ≥ 0, ± > 0, β > 0. The number of paths from A

to B which touch or cross the t’ axis equals the number of all paths from A to

B.

Proof. For any path from A to B which touches the horizontal axis, let t be

the abscissa of the ¬rst point of contact. Re¬‚ect the portion of the path from

A to T = (t, 0) relative to the horizontal axis. This re¬‚ected portion is a path

from A to T , and continues to give a path from A to B. This procedure assigns

to each path from A to B which touches the axis, a path from A to B. This

assignment is bijective: Any path from A to B must cross the t’axis. Re¬‚ect

the portion up to the ¬rst crossing to get a touching path from A to B. This is

the inverse assignment. QED

A path with n steps will join (0, 0) to (n, x) if an only if it has p steps of

slope +1 and q steps of slope ’1 where

p ’ q = x.

p + q = n,

The number of such paths is the number of ways of picking the positions of the

p steps of positive slope and so the number of paths joining (0, 0) to (n, x) is

p+q n

Nn,x = = .

n+x

p 2

It is understood that this formula means that Nn,x = 0 when there are no paths

joining the origin to (n, x).

97

4.4. THE ARC SINE LAW

Lemma 4.4.2 The ballot theorem. Let n and x be positive integers. There

are exactly

x

Nn,x

n

paths which lie strictly above the t axis for t > 0 and join (0, 0) to (n, x).

Proof. There are as many such paths as there are paths joining (1, 1) to (n, x)

which do not touch or cross the t’axis. This is the same as the total number

of paths which join (1, 1) to (n, x) less the number of paths which do touch or

cross. By the preceding lemma, the number of paths which do cross is the same

as the number of paths joining 1. ’ 1) to (n, x) which is Nn’1,x+1 . Thus, with p

and q as above, the number of paths which lie strictly above the t axis for t > 0

and which joint (0, 0) to (n, x) is

p+q’1 p+q’1

Nn’1,x’1 ’ Nn’1,x+1 ’

=