[an error occurred while processing this directive] [an error occurred while processing this directive]


The Excess of Heads over Tails, Long Leads, and the Arcsine Law


Key Concepts

Key Concepts

  1. The probability that the number of heads exceeds the number of tails in a sequence of coin-flips by some amount can be estimated with the Central Limit Theorem and the probability gets close to 1 as the number of tosses grows large.
  2. The law of long leads, more properly known as the arcsine law, says that in a coin-tossing games, a surprisingly large fraction of sample paths leave one player in the lead almost all the time, and in very few cases will the lead change sides and fluctuate in the manner that is naively expected of a well-behaved coin.
  3. Interpreted geometrically in terms of random walks, the path crosses the x-axis rarely, and with increasing duration of the walk, the frequency of crossings decreases, and the lengths of the “waves” on one side of the axis increase in length.


Vocabulary

Vocabulary

  1. The law of long leads, more properly known as the arcsine law, says that in a coin-tossing games, a surprisingly large fraction of sample paths leave one player in the lead almost all the time.


Mathematical Ideas

Mathematical Ideas

There are generally two classes of theorems about the results of coin-tossing games (and therefore random walks):

  1. Those theorems that tell how well-behaved and natural are the outcomes of typical coin-tossing games (and random walks). The Weak Law of Large Numbers, the Strong Law of Large Numbers and the Central Limit Theorem fall into this category.
  2. Those theorems that tell how strange and unnatural are the outcomes of typical coin-tossing games (and random walks). The Arcsine Law and the Law of the Iterated Logarithm are good examples in this category.

In this section we will ask three related questions about the net fortune in a coin-tossing game:

  1. What is the probability of an excess of heads over tails at some fixed time in the game? That is, should we expect a high probability that the number of heads is about the same as the number of tails at a fixed termination time of the game? We can also ask the complementary question about the probability that the number of heads exceeds the number of tails by some fixed fraction of the number of tosses.
  2. We can ask about the amount of time that the number of heads exceeds the number of tails in a coin-flipping game of a fixed duration. Equivalently, we can ask about the proportion of time that the coin-flipping gambler was ahead in the game.
  3. Finally, in a coin-flipping game of some fixed duration, we can ask how many times the lead changed from an excess of heads to an excess of tails. This is equivalent to asking how many times the random walk crossed the origin in its ramblings.

The excess of heads over tails in a typical sequence

This section is adapted from: the article “Tossing a Fair Coin” by Leonard Lipkin, in The College Mathematics Journal, Vol. 34, No. 2, March 2003, pages 128-133.

Consider the sequence of independent random variables Xi which take values 1 with probability 1/2 and -1 with probability 1/2. This is a mathematical model of a gambler’s fortune from a fair coin flip game where a gain of 1 results from “heads” on the ith coin toss and a loss -1 results from “tails”. Then  sum n Sn = i=1Xi counts the difference between the number of heads and tails, an excess of heads if positive, and a “negative excess”, i.e. a deficit, if negative. It also represents the net winnings of our gambler so far in his gambling game.

Theorem 1 Under assumption that Xi = +1 with probability 1/2 and Xi = -1 with probability 1/2, and Sn =  sum i=1nXi, then for an integer s,

Pr[|Sn| > s] ~~ Pr[| Z |> (s + 1/2)/ V~ n]

where Z is a standard normal random variable with mean 0 and variance 1.

Proof: Note that m = E[X ] = 0 i and s2 = Var[X ] = 1 i .

Pr[|S | > s] = 1 - Pr[- s < S < s] n n = 1 - Pr[- s- 1/2 < Sn < s + 1/2] = 1 - Pr[(- s- 1/2)/ V~ n-< Sn/V ~ n-< (s + 1/2)/ V~ n] V~ -- V~ -- ~~ 1 - Pr[(- s- 1/2)/ V~ n-< Z < (s + 1/2)/ n] = Pr[|Z| > (s + 1/2)/ n]
Q.E.D.

The crucial step occurs at the approximation, and uses the Central Limit Theorem. More precise statements of the Central Limit Theorem such as the Berry-Esseen inequality can turn the approximation into a inequality.

This theorem can be used to provide an alternative proof of the Weak Law of Large Numbers for the specific case of the binomial random variable Sn. In fact,

 [||S || ] V~ -- Pr ||-n-||> e ~~ Pr[|Z |> (en + 1/2)/ n] n V~ -- V~ -- = Pr[|Z |> e n + (1/2)/ n] --> 0
as n --> oo .

Corollary 1

 V~ -- Pr[Sn = 0] ~~ Pr[| Z |< (1/2)/ n]-- > 0
as n --> oo .

We can estimate this further

 V ~ -- integral 1/(2 V~ n) Pr[| Z |< (1/2)/ n] = V~ -1- e- u2/2 du 2p -1/(2 V~ n) integral 1/(2 V~ n) = V~ -1- 1 - u2/2 + u4/8 + ...du 2p -1/(2 V~ n) 1 1 1 1 1 1 = V~ --- V~ --- -- V~ ----3/2 + --- V~ ----5/2 + .... 2p n 24 2p n 640 2p n
So we see that Pr[Sn = 0] goes to zero at the rate of 1/ V~ - n.
Illustration 1
What is the probability that the number of heads exceeds the number of tails by more than 20 or the number of tails exceeds the number of heads by more than 20 after 500 tosses of a fair coin? By the theorem, this is:
 V~ ---- Pr[| Sn |> 20] ~~ Pr[|Z |> 20.5/ 500] = 0.3477

This is a reasonably large probability, and is larger than many people would expect.

Here is a graph of the probability of at least s excess heads in 500 tosses of a fair coin:

Probability of s excess heads in 500 tosses

Illustration 2
What is the probability that there is “about the same number of heads as tails” in 500 tosses? Here we interpret “about the same” as within 5, that is, a difference of 1% or less of the number of tosses. Note that since 500 is even, so the difference in the number of heads and tails cannot be an odd number, so must be either 0, 2 or 4.
 V~ ---- Pr[| Sn |< 5] ~~ Pr[|Z |< 5.5/ 500] = 0.1943
so it would be somewhat unusual (in that it occurs in less than 20% of games) to have the number of heads and tails so close.

The Arcsine Law

In this subsection we continue to consider net gains of fortune in the simple, fair, coin-tossing game (or symmetric random walk) Sn = X1 + ... + Xn composed of independent, identically distributed coin-toss random variables Xi, each of which assumes the value +1 with probability 1/2, and value -1 with probability 1/2. We shall say that the fortune spends the time from k - 1 to k on the positive side if at least one of the two values Sk-1 and Sk is positive (in which case the other is positive or at worst, 0). In this case, geometrically, the broken line path of the fortune lies above the horizontal axis over the interval (k - 1,k).

For notation, let

 ( ) u2n = 2n 2-2n. n

Theorem 2 Let p2k,2n be the probability that in the time interval from 0 to 2n, the particle spends 2k time units on the positive side, and therefore 2n - 2k on the negative side. Then

p2k,2n = u2ku2n-2k

We feel intuitively that the fraction k/n of the total time spent on the positive side is most likely to be 1/2. However, the opposite is true! The middle values of k/n are least probable and the extreme values k/n = 0 and k/n = 1 are most probable in terms of frequency measured by the probability distribution! The formula of the theorem is exact, but not intuitively revealing. To make more sense, we need the following:

Lemma 1 (Stirling’s Approximation)

 V~ ---- n -n n! ~ 2pnn e
where the relation an ~ bn, “an is asymptotic to bn’, means lim n--> oo an/bn = 1.

an is asymptotic to bn means the relative error between an and bn goes to zero, although if an and bn are large, the absolute error may be large. See the problems for an illustration.

An easy application of Stirling’s formula shows that

 V~ ------- 2n - 2n ---2p(2n)-(2n)--e--- -1-- V~ --- u2n ~ ( V~ ---- n - n)2 22n = 1/ pn 2pn n e
as n --> oo . Note that this says the probability of n heads and n tails becomes small as n gets large.

It then follows that

 1 p2k,2n =_ - V~ ---------- p k(n - k)
as k --> oo and (n - k) --> oo . The fraction of time that the fortune spends on the positive side is then k/n and the probability that the fortune is on this positive side this fraction of the time is p2k,2n. We can look at the cumulative probability that the fraction of time spent on the positive side is less than a (with a < 1) namely,
 sum -1 sum --------1---------1- p2k,2n ~ p V~ (k/n)(1----k/n) n k<an k<an

Riemann sum for arcsine law

On the right side we recognize the Riemann sum approximating the integral:

 integral a 1- V~ ---1-----dx = 2-arcsin( V~ a) dx. p x=0 x(1 - x) p

For reasons of symmetry, the probability that k/n < 1/2 tends to 1/2 as n --> oo . Adding this to the integral, we get:

Theorem 3 (The Arcsine Law) For fixed a with 0 < a < 1 and n --> oo , the probability that the fortune spends a fraction of time k/n on the positive side is less than a tends to:

 integral 1 a 1 2 V~ -- p- V~ ---------= p-arcsin( a) 0 x(1 - x)

The arcsine law was first established by P. Levy in 1939. Erdos and Kac generalized the arcsine law to the case of sums of independent random variables in 1947. E. Sparre Anderson later simplified the proofs and also generalized the results. There are several different proofs of the arcsine law.

Illustration 1

In practice, the formula provides a good approximation even for values of n as small as 20. The table below illustrates the approximation.

Illustration 2

An investment firm sends you an advertisement for their new investment plan. The ad claims that their investment plan, while subject to the “random fluctuations of the market”, yields a net fortune which is on the positive side at least 75% The company provides a graph of the plan’s outcome to “prove” their claim.

However, you should be suspicious. Even under the simple null hypothesis that their investment plan will yield a gain of 1 unit with probability 1/2 and will lose a unit with probability 1/2, the arcsine law tells us that the resulting fortune would spend 75% to 100% of its time on the positive side with probability:

2- V~ -- 2- V ~ ---- p arcsin( 1) - p arcsin( 0.75) = 0.33333
That is, “just by chance” the seemingly impressive result could occur about 1/3 of the time. Not enough evidence has been provided to convince us of the claim!

Problems to Work for Understanding

  1. Evaluate p2k,2n and graph the probability mass function for 2n = 30 and all admissible values. (Some computer software will make this easy and pleasant, but is not necessary.) of k.
  2. By actually evaluating the integral, show that
    1 integral a 1 2 V~ -- -- V~ ----------= --arcsin( a) p 0 x(1- x) p
    Use this to show that 1/(p V~ --------- x(1 - x)) is a probability density function for 0 < x < 1.
  3. Show that, with the notation above,
     e-k2/n Pr[S2n = 2k] ~ - V~ ---. pn


Reading Suggestion:

  1. Section XIV., Introduction to Probability Theory and Its Applications by W. Feller, J. Wiley and Sons, pages.
  2. “Tossing a Fair Coin” by Leonard Lipkin, in The College Mathematics Journal, Vol. 34, No. 2, March 2003, pages 128-133.


Outside Readings and Links:


[an error occurred while processing this directive] [an error occurred while processing this directive]

Last modified: [an error occurred while processing this directive]