Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
Probability Theory and Stochastic Processes
Steven R. Dunbar
The Arcsine Law
Mathematicians Only: prolonged scenes of intense rigor.
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?
Consider summing independent, identically distributed coin-toss random variables , each of which assumes the value with probability , and value with probability .
Recall that the stochastic process is a function of two variables: the time and the sample point . The Central Limit Theorem and the Moderate Deviations Theorem, give asymptotic results in about the probability, that is, the proportion of values with an speciﬁc excess of heads over tails at that ﬁxed . That event could be expressed in terms of the event for some . 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 to on the positive side if at least one of the two values and is positive (in which case the other is positive or at worst, ). Geometrically, the broken line path of the fortune lies above the horizontal axis over the interval .
For notation, let
Then is the binomial probability for exactly heads and tails in ﬂips of a fair coin.
We feel intuitively that the fraction of the total time spent on the positive side is most likely to be . However, the opposite is true! The middle values of are least probable and the extreme values and 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
as . Note that this application of Stirling’s formula says the probability of heads and tails in ﬂips of a fair coin goes to at the rate as gets large.
It then follows that
as and . The fraction of time that the fortune spends on the positive side is then and the probability the fortune is on this positive side this fraction of the time is . We can look at the cumulative probability that the fraction of time spent on the positive side is less than (with ) namely,
On the right side we recognize a Riemann sum approximating the integral:
For reasons of symmetry, the probability that tends to as . Adding this to the integral, we get:
Recall that is a sequence of independent random variables that take values with probability and with probability . This is a mathematical model of a fair coin ﬂip game where a results from “heads” on the th coin toss and a results from “tails”. Deﬁne by setting with .
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 . The person takes a step to the right to with probability and takes a step to the left to with probability 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 consisting of a ﬁnite union of segments of the form or where are integers is called a path. A path has an origin and an endpoint that are points on the curve with integer coordinates satisfying for all on the curve. The length of the path is . (Note that the Euclidean length of the path is .) To each element (see Binomial Distribution.), we associate a path with origin and endpoint .
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 and inclusive such that there were more Heads than Tails in the ﬁrst or tosses of the coin.
Line segments of a path are in the upper half plane if and only if . Thus, we can say
Proof. Note that
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 is that
which is clearly true since .
Fix , our inductive hypothesis is that the proposition is true for all and for all . Note that if , we have
again by the Nonnegative Walks Theorem (Theorem 3 in Positive Walks Theorem.). If , then there exists with so that . For each such that , the ﬁrst time back to is given by
Fix . Then
If , then note that
The ﬁrst term in the product is given by Corollary 1 in Positive Walks Theorem. and is and the second term is
Thus, we see that
Now combining the results we have
which means that induction holds and so we have proven the Proposition □
with uniformly in for . Thus, we have
Note that here we actually have a Riemann sum since we have a bounded function when we keep and . The rest of this proof is to allow and .
for suﬃciently large.
or in other words,
From these facts and part 2 we have
for suﬃciently large . Thus, for suﬃciently large have
So there exists so that for suﬃciently large . Since is increasing in for ﬁxed , we get uniformly in .
for . By symmetry, the proposition holds.
Proof of the Arcsine Law.
The proof uses the relationship between the random variables and . Since , it follows that
By Markov’s Inequality,
By Stirling’s Approximation, we have at the same rate as . Cesáro’s Principle gives
Now note that
Thus, we have
For the ﬁrst probability on the right
Therefore going back to the left hand side of equation (3), we have
Since , Proposition 4 says that
Thus . To complete, note that
Example. Consider the probability that Heads is in the lead at least of the time:
The probability is more than , surprisingly higher than most would anticipate.
In practice, the formula provides a good approximation even for values of as small as . The table below illustrates the approximation.
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 and will lose a unit with probability , the arcsine law tells us that the resulting fortune would spend 75% to 100% of its time on the positive side with probability:
That is, “just by chance” the seemingly impressive result could occur about 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.
This section is adapted from: This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, . Providence, 2005, Chapter 10.4. Some ideas are adapted from Chapter XIV of the classic text by Feller, .
|Comment Post: Empirical probability of random walks being positive at most .|
|Comment Post: Theoretical Arcsine Law probability|
|1 Set probability of success|
|2 Set length of random walk|
|3 Set number of trials|
|4 Set Arcsine Law parameter|
|5 Initialize and ﬁll matrix of random walks|
|6 Use vectorization to ﬁnd where each walk is positive|
|7 Use vectorization to sum the Boolean vector,|
|8 Count how many walks are positive on of the steps,|
|9 return Empirical probability|
|10 return Theoretical probability|
R script for the Arcsine Law.
Octave script for Arcsine Law.
Perl PDL script for the Arcsine Law..
Scientiﬁc Python script for the Arcsine Law..
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.
Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1
Email to Steve Dunbar, sdunbar1 at unl dot edu
Last modiﬁed: Processed from LATEX source on March 10, 2015