Steven R. Dunbar
Department of Mathematics
203 Avery Hall
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

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

### Section Starter Question

In a coin-ﬂipping 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

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 ﬂuctuate 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

1. The Arcsine Law, (sometimes known as the law of long leads) says
$\underset{n\to \infty }{lim}ℙn\left[{V}_{n}

__________________________________________________________________________

### Mathematical Ideas

#### Heuristics for the Arcsine Law

Consider ${T}_{n}={Y}_{1}+\cdots +{Y}_{n}$ summing independent, identically distributed coin-toss random variables ${Y}_{i}$, each of which assumes the value $+1$ with probability $1∕2$, and value $-1$ with probability $1∕2$.

Recall that the stochastic process ${T}_{n}$ is a function of two variables: the time $n$ and the sample point $\omega$. The Central Limit Theorem and the Moderate Deviations Theorem, give asymptotic results in $n$ about the probability, that is, the proportion of $\omega$ values with an speciﬁc excess of heads over tails at that ﬁxed $n$. That event could be expressed in terms of the event $\left\{\omega :{T}_{n}\left(\omega \right)>s\left(n\right)\right\}$ 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 ${T}_{k-1}$ and ${T}_{k}$ 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 $\left(k-1,k\right)$.

For notation, let

${u}_{2n}=\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right){2}^{-2n}.$

Then ${u}_{2n}$ is the binomial probability for exactly $n$ heads and $n$ tails in $2n$ ﬂips of a fair coin.

Proposition 1. Let ${p}_{2k,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

${p}_{2k,2n}={u}_{2k}{u}_{2n-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 Proposition is exact, but not intuitively revealing. To make more sense, Stirling’s Formula. shows that

${u}_{2n}\sim \frac{\sqrt{2\pi \left(2n\right)}\phantom{\rule{0.3em}{0ex}}{\left(2n\right)}^{2n}\phantom{\rule{0.3em}{0ex}}{e}^{-2n}}{{\left(\sqrt{2\pi n}\phantom{\rule{0.3em}{0ex}}{n}^{n}{e}^{-n}\phantom{\rule{0.3em}{0ex}}\right)}^{2}}\frac{1}{{2}^{2n}}=\frac{1}{\sqrt{\pi n}}$

as $n\to \infty$. Note that this application of Stirling’s formula says the probability of $n$ heads and $n$ tails in $2n$ ﬂips of a fair coin goes to $0$ at the rate $1∕\sqrt{n}$ as $n$ gets large.

It then follows that

${p}_{2k,2n}\approx \frac{1}{\pi \sqrt{k\left(n-k\right)}}$

as $k\to \infty$ and $\left(n-k\right)\to \infty$. The fraction of time that the fortune spends on the positive side is then $k∕n$ and the probability the fortune is on this positive side this fraction of the time is ${p}_{2k,2n}$. We can look at the cumulative probability that the fraction of time spent on the positive side is less than $\alpha$ (with $\alpha \le 1$) namely,

$\sum _{k<\alpha n}{p}_{2k,2n}\approx \frac{1}{\pi }\sum _{k<\alpha n}\frac{1}{\sqrt{\left(k∕n\right)\left(1-k∕n\right)}}\phantom{\rule{0.3em}{0ex}}\frac{1}{n}$

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

$\frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx=\frac{2}{\pi }arcsin\left(\sqrt{\alpha }\right)\phantom{\rule{0.3em}{0ex}}dx.$

For reasons of symmetry, the probability that $k∕n\le 1∕2$ tends to $1∕2$ as $n\to \infty$. Adding this to the integral, we get:

Theorem 2 (Arcsine Law). For ﬁxed $\alpha$ with $0<\alpha <1$ and $n\to \infty$, the probability that the fortune ${T}_{n}$ spends a fraction of time $k∕n$ on the positive side is less than $\alpha$ tends to:

$\frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}=\frac{2}{\pi }arcsin\left(\sqrt{\alpha }\right)$

#### The Arcsine Law for Bernoulli Trials

Recall that ${Y}_{i}$ is a sequence of independent random variables that take values $1$ with probability $1∕2$ and $-1$ with probability $1∕2$. This is a mathematical model of a fair coin ﬂip game where a $1$ results from “heads” on the $i$th coin toss and a $-1$ results from “tails”. Deﬁne $T=\left({T}_{0},\dots ,{T}_{n}\right)$ by setting ${T}_{n}={\sum }_{i=0}^{n}{Y}_{i}$ with ${T}_{0}=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 ${T}_{0}$. The person takes a step to the right to ${T}_{0}+1$ with probability $p$ and takes a step to the left to ${T}_{0}-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 ﬁnite union of segments of the form $\left[\left(i,j\right),\left(i+1,j+1\right)\right]$ or $\left[\left(i,j\right),\left(i+1,j-1\right)\right]$ where $i,j$ are integers is called a path. A path has an origin $\left(a,b\right)$ and an endpoint $\left(c,d\right)$ that are points on the curve with integer coordinates satisfying $a\le i\le c$ for all $\left(i,j\right)$ on the curve. The length of the path is $c-a$. (Note that the Euclidean length of the path is $\left(c-a\right)\sqrt{2}$.) To each element $\omega \in {\Omega }_{n}$ (see Binomial Distribution.), we associate a path ${\bigcup }_{k=0}^{n-1}\left[\left(i,{T}_{i}\left(\omega \right)\right),\left(i+1,{T}_{i+1}\left(\omega \right)\right)\right]$ with origin $\left(0,0\right)$ and endpoint $\left(n,{T}_{n}\left(\omega \right)\right)$.

Deﬁnition. Set

${V}_{n}=\left|\left\{k:0\le k\le n,\phantom{\rule{0.3em}{0ex}}{T}_{k}>0\right\}\right|.$

This is the number of tosses in which the Heads player is ahead or winning. Let . This is the number of integers, or steps, between $1$ and $n$ inclusive such that there were more Heads than Tails in the ﬁrst $k$ or $k-1$ tosses of the coin.

Line segments of a path are in the upper half plane if and only if ${T}_{2k-1}>0$. Thus, we can say

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

$ℙ2n\left[{V}_{2n}^{\prime }=2k\right]={2}^{-2n}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(n-k\right)}{n-k}\right)$

Proof. Note that

$ℙ2n\left[{V}_{2n}^{\prime }=2n\right]=ℙ2n\left[{T}_{k}\ge 0,k\in \left\{1,\dots ,2n\right\}\right]={2}^{-2n}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right).$

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

$\begin{array}{llll}\hfill ℙ2\left[{V}_{2}^{\prime }=0\right]& ={2}^{-2\left(1\right)}\left(\genfrac{}{}{0.0pt}{}{2\left(0\right)}{0}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(1-0\right)}{1}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{2}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

which is clearly true since .

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

$ℙ2n\left[{V}_{2n}^{\prime }=0\right]=ℙ2n\left[{T}_{k}\le 0,\phantom{\rule{0.3em}{0ex}}1\le k\le N\right]={2}^{-2N}\left(\genfrac{}{}{0.0pt}{}{2N}{N}\right)$

again by the Nonnegative Walks Theorem (Theorem 3 in Positive Walks Theorem.). If $0<{V}_{2N}^{\prime }<2N$, then there exists $j$ with $1\le j\le N$ so that ${T}_{2j}=0$. For each $\omega \in {\Omega }_{2N}$ such that $0<{V}_{2n}^{\prime }\left(\omega \right)<2N$, the ﬁrst time back to $0$ is given by

$v\left(\omega \right)=min\left\{j>0:{T}_{2j}\left(\omega \right)=0\right\}.$

Fix $k\in \left\{1,\dots ,N-1\right\}$. Then

$\begin{array}{llll}\hfill ℙ2N\left[{V}_{2N}^{\prime }=2k\right]& =\sum _{j=1}^{N}ℙ2N\left[{V}_{2N}^{\prime }=2k,\phantom{\rule{0.3em}{0ex}}v\left(\omega \right)=2j,\phantom{\rule{0.3em}{0ex}}{T}_{1}>0\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & +\sum _{j=1}^{N}ℙ2N\left[{V}_{2N}^{\prime }=2k,\phantom{\rule{0.3em}{0ex}}v\left(\omega \right)=2j,\phantom{\rule{0.3em}{0ex}}{T}_{1}<0\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

If $j>k$, then note that

$\left\{{V}_{2N}^{\prime }=2k,\phantom{\rule{0.3em}{0ex}}v\left(\omega \right)=2j,\phantom{\rule{0.3em}{0ex}}{T}_{1}>0\right\}=\varnothing .$

Note that

The ﬁrst term in the product is given by Corollary 1 in Positive Walks Theorem. and is $\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)$ and the second term is

${2}^{2\left(N-j\right)}ℙ2N\left[{V}_{2\left(N-j\right)}^{\prime }=2\left(k-j\right)\right]=\left(\genfrac{}{}{0.0pt}{}{2\left(k-j\right)}{k-j}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right).$

Thus, we see that

$ℙ2N\left[{V}_{2N}^{\prime }=2k,t\left(\omega \right)=2j,{T}_{1}>0\right]=\frac{1}{j{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(k-j\right)}{k-j}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right).$

Now combining the results we have

$\begin{array}{llll}\hfill & ℙ2N\left[{V}_{2N}^{\prime }=2k\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}=\sum _{j=1}^{k}\frac{1}{2{j}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(k-j\right)}{k-j}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}+\sum _{j=1}^{N-k}\frac{1}{2{j}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-j-k\right)}{N-j-k}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}=\left[\frac{1}{{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right)\right]\sum _{j=1}^{k}\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(k-j\right)}{k-j}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}+\left[\frac{1}{{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\right]\sum _{j=1}^{k}\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-j-k\right)}{N-j-k}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}=\left[\frac{1}{{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right)\right]\left(\frac{1}{2}\right)\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}+\left[\frac{1}{{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\right]\left(\frac{1}{2}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}=\frac{1}{{2}^{2N}}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(N-k\right)}{N-k}\right),\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

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

Theorem 3 (Arcsine Law). For each $\alpha \in \left(0,1\right)$,

$\underset{n\to \infty }{lim}ℙn\left[{V}_{n}

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\le a\le b\le 1$, then

$\underset{n\to \infty }{lim}ℙ2n\left[2na\le {V}_{2n}^{\prime }\le 2nb\right]=\frac{1}{\pi }{\int }_{a}^{b}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx.$

Proof.

1. First, if we have $0, then by Proposition 1 and Stirling’s Approximation tell us $\begin{array}{llll}\hfill ℙ2n\left[{V}_{2n}^{\prime }=2k\right]& =\frac{1}{\pi }\frac{1}{\sqrt{k\left(n-k\right)}}\left(1+𝜖\left(k\right)\right)\left(1+𝜖\left(n-k\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{\pi }\frac{1}{\sqrt{k\left(n-k\right)}}\left(1+𝜖\left(n,k\right)\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

with $\underset{n\to \infty }{lim}𝜖\left(n,k\right)=0$ uniformly in $k\in ℤ$ for $na\le k\le nb$. Thus, we have

$\begin{array}{llll}\hfill ℙ2n\left[2na\le {V}_{2n}^{\prime }\le 2nb\right]& =\sum _{na\le k\le nb}ℙ2n\left[{V}_{2n}^{\prime }=2k\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \sim \sum _{a\le \frac{k}{n}\le b}\frac{1}{\pi }\frac{1}{\sqrt{k\left(n-k\right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sum _{a\le \frac{k}{n}\le b}\frac{1}{\pi }\frac{1}{\sqrt{{n}^{2}\left(\frac{k}{n}\right)\left(1-\frac{k}{n}\right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sum _{k=0}^{n}\left({\chi }_{\left[a,b\right]}\left(\frac{k}{n}\right)\right)\frac{1}{\pi }\frac{1}{n}\frac{1}{\sqrt{\left(\frac{k}{n}\right)\left(1-\frac{k}{n}\right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{n\pi }\sum _{k=0}^{n}\left({\chi }_{\left[a,b\right]}\left(\frac{k}{n}\right)\right)\frac{1}{\sqrt{\left(\frac{k}{n}\right)\left(1-\frac{k}{n}\right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \to \frac{1}{\pi }{\int }_{0}^{1}{\chi }_{\left[a,b\right]}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{\pi }{\int }_{a}^{b}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

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

2. Fix $𝜖>0$. There exists an $a$ so that $\frac{1}{\pi }{\int }_{0}^{a}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx<𝜖$ and $\frac{1}{\pi }{\int }_{1-a}^{1}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx<𝜖$. From part 1 of the proof, we have
$\left|\frac{1}{\pi }{\int }_{a}^{1-a}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx-ℙ2n\left[2na\le {V}_{2n}^{\prime }\le 2n\left(1-a\right)\right]\right|<𝜖$

for $n$ suﬃciently large.

3. Note that $ℙ2n\left[{V}_{2n}^{\prime }<2na\right]+ℙ2n\left[2na\le {V}_{2n}^{\prime }\le 2n\left(1-a\right)\right]+ℙ2n\left[{V}_{2n}^{\prime }>2n\left(1-a\right)\right]=1$. Note also that $\frac{1}{\pi }{\int }_{0}^{1}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx=1$. Together these imply that
$\frac{1}{\pi }{\int }_{a}^{1-a}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx=1-{\int }_{0}^{a}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx-{\int }_{1-a}^{1}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx,$

or in other words,

$ℙ2n\left[2na\le {V}_{2n}^{\prime }\le 2n\left(1-a\right)\right]=1-ℙ2n\left[{V}_{2n}^{\prime }<2na\right]-ℙ2n\left[{V}_{2n}^{\prime }>2n\left(1-a\right)\right].$

From these facts and part 2 we have

$\begin{array}{lll}\hfill \left|\left(\frac{1}{\pi }{\int }_{0}^{a}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx\right\right& \phantom{\rule{2em}{0ex}}& \hfill \\ \hfill & +\frac{1}{\pi }{\int }_{1-a}^{1}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx-1)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & +\left(1-ℙ2n\left[{V}_{2n}^{\prime }<2na\right]-ℙ2n\left[{V}_{2n}^{\prime }>2n\left(1-a\right)\right]\right)|\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

for suﬃciently large $n$. Thus, for suﬃciently large $n$ have

$\left|ℙP\left[2n\right]{V}_{2n}^{\prime }<2na+ℙ2n\left[{V}_{2n}^{\prime }>2n\left(1-a\right)\right]\right|<3𝜖.$

So there exists $a>0$ so that $ℙ2n\left[{V}_{2n}^{\prime }<2na\right]<3𝜖$ for suﬃciently large $n$. Since $ℙ2n\left[{V}_{2n}^{\prime }<2na\right]$ is increasing in $a$ for ﬁxed $n$, we get $\underset{a\to \infty }{lim}ℙ2n\left[{V}_{2n}^{\prime }<2na\right]=0$ uniformly in $n$.

4. By parts 1 and2, we have
$\underset{n\to \infty }{lim}ℙn\left[{V}_{2n}^{\prime }\le 2nb\right]=\frac{1}{\pi }{\int }_{0}^{b}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx$

for $b\in \left(0,1\right)$. By symmetry, the proposition holds.

Proof of the Arcsine Law.

The proof uses the relationship between the random variables ${V}_{2n}$ and ${V}_{2n}^{\prime }$. Since ${V}_{2n}:={V}_{2n}^{\prime }-\left|\left\{k:1\le k\le n,\phantom{\rule{0.3em}{0ex}}{T}_{2k-1}>0,\phantom{\rule{0.3em}{0ex}}{T}_{2k}=0\right\}\right|$, it follows that

 $\left|{V}_{2n}-{V}_{2n}^{\prime }\right|\le \left|\left\{k:1\le k\le n,\phantom{\rule{0.3em}{0ex}}{T}_{2k}=0\right\}\right|={U}_{2n}.$ (1)

Note that

$\begin{array}{llll}\hfill 𝔼2n\left[{U}_{2n}\right]& =𝔼2n\left[\sum _{k=1}^{n}{\chi }_{\left[{T}_{2k}=0\right]}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sum _{k=1}^{n}ℙ2n\left[{T}_{2k}=0\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sum _{k=1}^{n}{2}^{-2k}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

By Markov’s Inequality,

$\begin{array}{llll}\hfill ℙ2n\left[{U}_{2n}>2n𝜖\right]& \le \frac{𝔼2n\left[{U}_{2n}\right]}{2n𝜖}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{2n𝜖}\sum _{k=1}^{n}{2}^{-2k}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

By Stirling’s Approximation, we have $\underset{k\to \infty }{lim}{2}^{-2k}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)=0$ at the same rate as $\frac{1}{\sqrt{n}}$. Cesáro’s Principle gives

 $\underset{n\to \infty }{lim}ℙ2n\left[{U}_{2n}>2n𝜖\right]=0.$ (2)

Now note that

$\left[{V}_{2n}<2n\alpha \right]\subset \left[\left|{V}_{2n}-{V}_{2n}^{\prime }\right|>2n𝜖\right]\cup \left[{V}_{2n}^{\prime }\le 2n\left(\alpha +𝜖\right)\right].$

Thus, we have

 $ℙ2n\left[{V}_{2n}<2n\alpha \right]\le ℙ2n\left[\left|{V}_{2n}-{V}_{2n}^{\prime }\right|>2n𝜖\right]+ℙ2n\left[{V}_{2n}^{\prime }\le 2n\left(\alpha +𝜖\right)\right].$ (3)

For the ﬁrst probability on the right

$ℙ2n\left[\left|{V}_{2n}-{V}_{2n}^{\prime }\right|>2n𝜖\right]\le ℙ2n\left[{U}_{2n}>2n𝜖\right]\to 0.$

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

$\begin{array}{llll}\hfill \underset{n\to \infty }{lim}ℙ2n\left[{V}_{2n}^{\prime }\le 2n\left(\alpha +𝜖\right)\right]& =\underset{n\to \infty }{lim}ℙ2n\left[{V}_{2n}^{\prime }\le 2n\left(\alpha +𝜖\right)\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{\pi }{\int }_{0}^{\alpha +𝜖}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx,\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

and $𝜖\to 0$ gives

$\underset{𝜖\to 0}{lim}\frac{1}{\pi }{\int }_{0}^{\alpha +𝜖}\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx=\frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}dx.$

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

$\underset{n\to \infty }{limsup}ℙ2n\left[{V}_{2n}<2n\alpha \right]\le \frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx.$

Since ${V}_{2n}\le {V}_{2n}^{\prime }$, Proposition 4 says that

$\underset{n\to \infty }{liminf}ℙ2n\left[{V}_{2n}<2n\alpha \right]\ge \frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx.$

Thus $\underset{n\to \infty }{lim}ℙ2n\left[{V}_{2n}<2n\alpha \right]=\frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx$. To complete, note that

$ℙ2n\left[{V}_{2n+1}<\left(2n+1\right)\alpha \right]\le ℙ2n\left[{V}_{2n}<\left(2n+1\right)\alpha \right]$

and similarly,

$ℙ2n\left[{V}_{2n+2}<\left(2n+2\right)\alpha \right]\ge ℙ2n\left[{V}_{2n+1}<\left(2n+2\right)\right].$

#### Examples and Illustration

##### Illustration 1

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

$\underset{n\to \infty }{lim}ℙn\left[{V}_{n}\ge 0.85n\right]=\underset{n\to \infty }{lim}\left(1-ℙn\left[{V}_{n}<0.85n\right]\right)=1-\frac{2}{\pi }arcsin\sqrt{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=20$ $k$ ${p}_{2k,2n}$ cdf $k∕n$ $\left(2∕\pi \right)arcsin\left(\sqrt{\alpha }\right)$ 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 ﬁrm sends you an advertisement for their new investment plan. The ad claims that their investment plan, while subject to the “random ﬂuctuations 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 $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:

$\frac{2}{\pi }arcsin\left(\sqrt{1}\right)-\frac{2}{\pi }arcsin\left(\sqrt{0.75}\right)=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!

The Arcsine Law was ﬁrst 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

#### Algorithm

ArcsineLaw-Simulation

 Comment Post: Empirical probability of random walks being positive at most $100\alpha %$.

 Comment Post: Theoretical Arcsine Law probability $\frac{2}{\pi }arcsin\left(\sqrt{\alpha }\right)$

 1 Set probability of success $p$

 2 Set length of random walk $n$

 3 Set number of trials $k$

 4 Set Arcsine Law parameter $\alpha$

 5 Initialize and ﬁll $k×n$ matrix of random walks

 6 Use vectorization to ﬁnd where each walk is positive

 7 Use vectorization to sum the Boolean vector, $ﬁndposwalks$

 8 Count how many walks are positive on $ of the steps, $longleads$

 9 return Empirical probability $longleads∕k$

 10 return Theoretical probability $\frac{2}{\pi }arcsin\left(\sqrt{\alpha }\right)$

#### Scripts

R
< 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))

theoretical < (2/pi)  asin(sqrt(alpha))

cat(sprintf(”Empirical_probability:_%fn”, prob))
cat(sprintf(”Positive_Walks_Theorem_probability:_%fn”, theoretical))
Octave
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 );

theoretical = (2/pi)asin(sqrt(alpha));

disp(”Empirical_probability:”), disp( prob )
disp(”Arcsine_Law_probability:”), disp( theoretical )
Perl
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
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 for Understanding

1. Show that
$\frac{1}{\pi }{\int }_{0}^{\alpha }\frac{1}{\sqrt{x\left(1-x\right)}}\phantom{\rule{0.3em}{0ex}}dx=\frac{2}{\pi }arcsin\sqrt{\alpha }.$

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 ﬁner representation.

__________________________________________________________________________

### 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.

__________________________________________________________________________

__________________________________________________________________________

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 eﬀort 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 reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.