Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

The Arcsine Law

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

In a coin-flipping game, do you expect the lead to change often? Graphically, how would you recognize a change in lead? What does the Weak Law of Large Numbers have to say about the lead changing often? What does the Central Limit Theorem have to say about the lead changing often?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. The Arcsine Law, (sometimes known as the law of long leads), 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.
  2. Interpreted geometrically as 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 “leads” on one side of the axis increase in length.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. The Arcsine Law, (sometimes known as the law of long leads) says
    lim nn V n < nα = 1 π0α 1 x(1 x)dx = 2 π arcsin α.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Heuristics for the Arcsine Law

Consider Tn = Y 1 + + Y n summing independent, identically distributed coin-toss random variables Y i, each of which assumes the value +1 with probability 12, and value 1 with probability 12.

Recall that the stochastic process Tn is a function of two variables: the time n and the sample point ω. The Central Limit Theorem and the Moderate Deviations Theorem, give asymptotic results in n about the probability, that is, the proportion of ω values with an specific excess of heads over tails at that fixed n. That event could be expressed in terms of the event {ω : Tn(ω) > s(n)} for some s. Now we are going to take a somewhat complementary point of view, asking about an event that counts the amount of time that the net fortune or walk is positive.

We say that the fortune spends the time from k 1 to k on the positive side if at least one of the two values Tk1 and Tk is positive (in which case the other is positive or at worst, 0). Geometrically, the broken line path of the fortune lies above the horizontal axis over the interval (k 1,k).

For notation, let

u2n = 2n n 22n.

Then u2n is the binomial probability for exactly n heads and n tails in 2n flips of a fair coin.

Proposition 1. 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 = u2ku2n2k

We feel intuitively that the fraction kn of the total time spent on the positive side is most likely to be 12. However, the opposite is true! The middle values of kn are least probable and the extreme values kn = 0 and kn = 1 are most probable in terms of frequency measured by the probability distribution!

The formula of the Proposition is exact, but not intuitively revealing. To make more sense, Stirling’s Formula. shows that

u2n 2π(2n)(2n)2ne2n 2πnnnen 2 1 22n = 1 πn

as n . Note that this application of Stirling’s formula says the probability of n heads and n tails in 2n flips of a fair coin goes to 0 at the rate 1n as n gets large.

It then follows that

p2k,2n 1 πk(n k)

as k and (n k) . The fraction of time that the fortune spends on the positive side is then kn and the probability 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 α (with α 1) namely,

k<αnp2k,2n 1 π k<αn 1 (kn)(1 kn)1 n

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

1 π0α 1 x(1 x)dx = 2 π arcsin(α)dx.

For reasons of symmetry, the probability that kn 12 tends to 12 as n . Adding this to the integral, we get:

Theorem 2 (Arcsine Law). For fixed α with 0 < α < 1 and n , the probability that the fortune Tn spends a fraction of time kn on the positive side is less than α tends to:

1 π0α 1 x(1 x) = 2 π arcsin(α)

The Arcsine Law for Bernoulli Trials

Recall that Y i is a sequence of independent random variables that take values 1 with probability 12 and 1 with probability 12. This is a mathematical model of a fair coin flip game where a 1 results from “heads” on the ith coin toss and a 1 results from “tails”. Define T = (T0,,Tn) by setting Tn = i=0nY i with T0 = 0.

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 T0. The person takes a step to the right to T0 + 1 with probability p and takes a step to the left to T0 1 with probability q 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 2 consisting of a finite union of segments of the form [(i,j), (i + 1,j + 1)] or [(i,j), (i + 1,j 1)] where i,j are integers is called a path. A path has an origin (a,b) and an endpoint (c,d) that are points on the curve with integer coordinates satisfying a i c for all (i,j) on the curve. The length of the path is c a. (Note that the Euclidean length of the path is (c a)2.) To each element ω Ωn (see Binomial Distribution.), we associate a path k=0n1[(i,T i(ω)), (i + 1,Ti+1(ω))] with origin (0, 0) and endpoint (n,Tn(ω)).

Definition. Set

V n = {k : 0 k n,Tk > 0}.

This is the number of tosses in which the Heads player is ahead or winning. Let V n = {k : 1 k n,T k > 0 or Tk1 > 0}. This is the number of integers, or steps, between 1 and n inclusive such that there were more Heads than Tails in the first k or k 1 tosses of the coin.

Line segments of a path are in the upper half plane if and only if T2k1 > 0. Thus, we can say

V 2n = 2 {k : 1 k n and T 2k1 > 0}.

Proposition 1. For each n > 0 and 0 k n, then

2n V 2n = 2k = 22n2k k 2(n k) n k

Proof. Note that

2n V 2n = 2n = 2n Tk 0,k {1,, 2n} = 22n2n n .

by the Nonnegative Walks Theorem (Theorem 3 in Positive Walks Theorem.). Prove the general statement of the current Proposition by induction. The base case where n = 1 is that

2 V 2 = 0 = 22(1)2(0) 0 2(1 0) 1 = 1 2

which is clearly true since 2 V 2 = 2 T2 > 0 or T1 > 0.

Fix N > 1, our inductive hypothesis is that the proposition is true for all n N 1 and for all 0 k n. Note that if k = 0, we have

2n V 2n = 0 = 2n Tk 0,1 k N = 22N2N N

again by the Nonnegative Walks Theorem (Theorem 3 in Positive Walks Theorem.). If 0 < V 2N < 2N, then there exists j with 1 j N so that T2j = 0. For each ω Ω2N such that 0 < V 2n(ω) < 2N, the first time back to 0 is given by

v(ω) = min{j > 0 : T2j(ω) = 0}.

Fix k {1,,N 1}. Then

2N V 2N = 2k = j=1N 2N V 2N = 2k,v(ω) = 2j,T 1 > 0 + j=1N 2N V 2N = 2k,v(ω) = 2j,T 1 < 0

If j > k, then note that

{V 2N = 2k,v(ω) = 2j,T 1 > 0} = .

Note that

{V 2N = 2k,v(ω) = 2j,T 1 > 0} = number of paths (0, 0) to (2j, 0) with Ti > 0 for i > 1 ×number of paths starting at (2j, 0) and length 2(N j)  with 2(k j) elementary segments in the upper half plane

The first term in the product is given by Corollary 1 in Positive Walks Theorem. and is 1 j 2j2 j1 and the second term is

22(Nj) 2N V 2(Nj) = 2(k j) = 2(k j) k j 2(N k) N k .

Thus, we see that

2N V 2N = 2k,t(ω) = 2j,T 1 > 0 = 1 j22N 2j 2 j 1 2(k j) k j 2(N k) N k .

Now combining the results we have

2N V 2N = 2k = j=1k 1 2j2N 2j 2 j 1 2(k j) k j 2(N k) N k + j=1Nk 1 2j2N 2j 2 j 1 2k k 2(N j k) N j k = 1 22N 2(N k) N k j=1k1 j 2j 2 j 1 2(k j) k j + 1 22N 2k k j=1k1 j 2j 2 j 1 2(N j k) N j k = 1 22N 2(N k) N k 1 2 2k k + 1 22N 2k k 1 2 2(N k) N k = 1 22N 2k k 2(N k) N k ,

which means that induction holds and so we have proven the Proposition □

Theorem 3 (Arcsine Law). For each α (0, 1),

lim nn V n < nα = 1 π0α 1 x(1 x)dx = 2 π arcsin α.



Figure 1: Illustration of the Arcsine Law using a simulation with 200 trials of random walks of length n = 100.

Proposition 4. For all a,b with 0 a b 1, then

lim n2n 2na V 2n 2nb = 1 πab 1 x(1 x)dx.

Proof.

  1. First, if we have 0 < a < b < 1, then by Proposition 1 and Stirling’s Approximation tell us 2n V 2n = 2k = 1 π 1 k(n k) 1 + 𝜖(k) 1 + 𝜖(n k) = 1 π 1 k(n k) 1 + 𝜖(n,k) .

    with lim n𝜖(n,k) = 0 uniformly in k for na k nb. Thus, we have

    2n 2na V 2n 2nb = naknb2n V 2n = 2k ak nb 1 π 1 k(n k) = ak nb 1 π 1 n2 k n 1 k n = k=0n χ [a,b] k n 1 π 1 n 1 k n 1 k n = 1 nπ k=0n χ [a,b] k n 1 k n 1 k n 1 π01χ [a,b] 1 x(1 x)dx = 1 πab 1 x(1 x)dx.

    Note that here we actually have a Riemann sum since we have a bounded function when we keep a0 and b1. The rest of this proof is to allow a = 0 and b = 1.

  2. Fix 𝜖 > 0. There exists an a so that 1 π0a 1 x(1x)dx < 𝜖 and 1 π1a1 1 x(1x)dx < 𝜖. From part 1 of the proof, we have
    1 πa1a 1 x(1 x)dx 2n 2na V 2n 2n(1 a) < 𝜖

    for n sufficiently large.

  3. Note that 2n V 2n < 2na + 2n 2na V 2n 2n(1 a) + 2n V 2n > 2n(1 a) = 1. Note also that 1 π01 1 x(1x)dx = 1. Together these imply that
    1 πa1a 1 x(1 x)dx = 1 0a 1 x(1 x)dx 1a1 1 x(1 x)dx,

    or in other words,

    2n 2na V 2n 2n(1 a) = 1 2n V 2n < 2na 2n V 2n > 2n(1 a) .

    From these facts and part 2 we have

    1 π0a 1 x(1 x)dx +1 π1a1 1 x(1 x)dx 1 + 1 2n V 2n < 2na 2n V 2n > 2n(1 a)

    for sufficiently large n. Thus, for sufficiently large n have

    P 2nV 2n < 2na + 2n V 2n > 2n(1 a) < 3𝜖.

    So there exists a > 0 so that 2n V 2n < 2na < 3𝜖 for sufficiently large n. Since 2n V 2n < 2na is increasing in a for fixed n, we get lim a2n V 2n < 2na = 0 uniformly in n.

  4. By parts 1 and2, we have
    lim nn V 2n 2nb = 1 π0b 1 x(1 x)dx

    for b (0, 1). By symmetry, the proposition holds.

Proof of the Arcsine Law.

The proof uses the relationship between the random variables V 2n and V 2n. Since V 2n := V 2n{k : 1 k n,T 2k1 > 0,T2k = 0}, it follows that

V 2n V 2n {k : 1 k n,T 2k = 0} = U2n. (1)

Note that

𝔼2n U2n = 𝔼2n k=1nχ [T2k=0] = k=1n 2n T2k = 0 = k=1n22k2k k .

By Markov’s Inequality,

2n U2n > 2n𝜖 𝔼2n U2n 2n𝜖 = 1 2n𝜖 k=1n22k2k k .

By Stirling’s Approximation, we have lim k22k2k k = 0 at the same rate as 1 n. Cesáro’s Principle gives

lim n2n U2n > 2n𝜖 = 0. (2)

Now note that

[V 2n < 2nα] V 2n V 2n > 2n𝜖 V 2n 2n(α + 𝜖) .

Thus, we have

2n V 2n < 2nα 2n V 2n V 2n > 2n𝜖 + 2n V 2n 2n(α + 𝜖) . (3)

For the first probability on the right

2n V 2n V 2n > 2n𝜖 2n U2n > 2n𝜖 0.

as n . For the second probability on the right in Equation (3), note that Proposition 4 says that

lim n2n V 2n 2n(α + 𝜖) = lim n2n V 2n 2n(α + 𝜖) = 1 π0α+𝜖 1 x(1 x)dx,

and 𝜖 0 gives

lim 𝜖0 1 π0α+𝜖 1 x(1 x)dx = 1 π0α 1 x(1 x)dx.

Therefore going back to the left hand side of equation (3), we have

limsup n2n V 2n < 2nα 1 π0α 1 x(1 x)dx.

Since V 2n V 2n, Proposition 4 says that

liminf n2n V 2n < 2nα 1 π0α 1 x(1 x)dx.

Thus lim n2n V 2n < 2nα = 1 π0α 1 x(1x)dx. To complete, note that

2n V 2n+1 < (2n + 1)α 2n V 2n < (2n + 1)α

and similarly,

2n V 2n+2 < (2n + 2)α 2n V 2n+1 < (2n + 2) .

Examples and Illustration

Illustration 1

Example. Consider the probability that Heads is in the lead at least 85% of the time:

lim nn V n 0.85n = lim n1 n V n < 0.85n = 12 π arcsin 0.85 = 0.25318.

The probability is more than 25%, surprisingly higher than most would anticipate.

Illustration 2

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


2n = 20kp2k,2n cdf kn(2π) arcsin(α)






0 0.1762 0.1762 0 0.0000
2 0.0927 0.2689 0.1 0.2048
4 0.0736 0.3426 0.2 0.2952
6 0.0655 0.4080 0.3 0.3690
8 0.0617 0.4697 0.4 0.4359
10 0.0606 0.5303 0.5 0.5000
12 0.0617 0.5920 0.6 0.5641
14 0.0655 0.6574 0.7 0.6310
16 0.0736 0.7311 0.8 0.7048
18 0.0927 0.8238 0.9 0.7952
20 0.1762 1.0000 1 1.0000
2n = 40 2k
0 0.1254 0.1254 0 0.0000
2 0.0643 0.1897 0.05 0.1436
4 0.0495 0.2392 0.1 0.2048
6 0.0424 0.2816 0.15 0.2532
8 0.0383 0.3199 0.2 0.2952
10 0.0356 0.3555 0.25 0.3333

Figure 2: A comparison of exact and arcsine probability distributions

Illustration 3

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% of the time. 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 12 and will lose a unit with probability 12, the arcsine law tells us that the resulting fortune would spend 75% to 100% of its time on the positive side with probability:

2 π arcsin(1) 2 π arcsin(0.75) = 0.33333

That is, “just by chance” the seemingly impressive result could occur about 13 of the time. Not enough evidence has been provided to convince us of the claim!

History and Comments

The Arcsine Law was first proved by P. Lévy in 1939 for Brownian motion. Then Erdös and Kac proved the Arcsine Law in 1947 for sums of independent random variables using an Invariance Principle. In 1954 Sparre Andersen proved the Arcsine Law with a combinatorial argument. There are several other ways to prove the Arcsine Law, which means that the Arcsine Law has a surprising variety of proofs.

Sources

This section is adapted from: This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, [2]. Providence, 2005, Chapter 10.4. Some ideas are adapted from Chapter XIV of the classic text by Feller, [1].

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

ArcsineLaw-Simulation
 
Comment Post: Empirical probability of random walks being positive at most 100α%.

Comment Post: Theoretical Arcsine Law probability 2 π arcsin(α)

1 Set probability of success p

2 Set length of random walk n

3 Set number of trials k

4 Set Arcsine Law parameter α

5 Initialize and fill k × n matrix of random walks

6 Use vectorization to find where each walk is positive

7 Use vectorization to sum the Boolean vector, ndposwalks

8 Count how many walks are positive on < nα of the steps, longleads

9 return Empirical probability longleadsk

10 return Theoretical probability 2 π arcsin(α)

Scripts

Scripts

R

R script for the Arcsine Law.

< 0.5 
< 100 
< 200 
 
alpha < 0.85 
 
walks < matrix(0, nrow = k, ncol = n + 1) 
rw < t(apply(2  matrix((runif(n  k) <= p), k, n)  1, 1, cumsum)) 
walks[, 1:n + 1] < rw 
 
findposwalks < apply(0 + (walks[, 1:n + 1] > 0), 1, sum
longleads < sum(0 + (findposwalks < n  alpha)) 
 
prob < longleads/
theoretical < (2/pi)  asin(sqrt(alpha)) 
 
cat(sprintf(”Empirical_probability:_%fn”, prob)) 
cat(sprintf(”Positive_Walks_Theorem_probability:_%fn”, theoretical))
Octave

Octave script for Arcsine Law.

p = 0.5; 
n = 100; 
k = 200; 
 
alpha = 0.85; 
 
walks = zeros(k, n+1); 
walks(:,2:n+1) = cumsum((2  (rand(k,n) <= p)  1), 2); 
 
findposwalks = sum( walks(:, 2:n+1) > 0, 2); 
longleads = sum( findposwalks < nalpha ); 
 
prob = longleads/k; 
theoretical = (2/pi)asin(sqrt(alpha)); 
 
disp(”Empirical_probability:”), disp( prob ) 
disp(”Arcsine_Law_probability:”), disp( theoretical )
Perl

Perl PDL script for the Arcsine Law..

use PDL::NiceSlice; 
 
$p = 0.5; 
$n = 100; 
$k = 200; 
 
$alpha = 0.85; 
 
$walks = zeros( $n + 1, $k ); 
$rw = cumusumover( 2  ( random( $n, $k ) <= $p )  1 ); 
$walks ( 1 : $n, 0 : $k  1 ) .= $rw; 
 
$findposwalks = sumover( $walks ( 1 : $n, 0 : $k  1 ) > 0 ); 
$poswalks = sum( $findposwalks < $n  $alpha ); 
 
$prob = $poswalks / $k; 
 
use PDL::Constants qw(PI); 
use PDL::Math; 
$theoretical = ( 2. / PI )  asin( sqrt($alpha) ); 
 
print ”Empirical_probability”,              $prob,        ”n”; 
print ”Positive_Walks_Theorem_probability”, $theoretical, ”n”;
SciPy

Scientific Python script for the Arcsine Law..

import scipy 
 
p = 0.5 
n = 100 
k = 200 
 
alpha = 0.85 
 
walks = scipy.zeros((k, n + 1), dtype=int
rw = scipy.cumsum(2  (scipy.random.random((k, n)) <= p)  1, axis=1) 
walks[:, 1:n + 1] = rw 
 
findposwalks = 0 + (walks[:, 1:n + 1] > 0) 
poswalks = scipy.sum(scipy.sum(findposwalks, axis=1) < n  alpha) 
 
prob = float(poswalks) / float(k) 
theoretical = 2.0 / scipy.pi  scipy.arcsin(scipy.sqrt(alpha)) 
 
print ’Empirical_probability:’, prob 
print ’Positive_Walks_Theorem_probability:’, theoretical

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Show that
    1 π0α 1 x(1 x)dx = 2 π arcsin α.

  2. Adapt the scripts with a larger number of trials and longer walks to create an empirical histogram of the Arcsine Law, comparing it with the theoretical density as in Figure 1. Use an increased number of histogram intervals to create a finer representation.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   William Feller. An Introduction to Probability Theory and Its Applications, Volume I, volume I. John Wiley and Sons, third edition, 1973. QA 273 F3712.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

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 effort 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 reflects the thoughts, interests and opinions of its author. They do not explicitly represent official 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 modified: Processed from LATEX source on March 10, 2015