[an error occurred while processing this directive] [an error occurred while processing this directive]
There are generally two classes of theorems about the results of coin-tossing games (and therefore random walks):
In this section we will ask three related questions about the net fortune in a coin-tossing game:
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 X_{i} 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 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 X_{i} = +1 with probability 1/2 and X_{i} = -1 with probability 1/2, and S_{n} = _{i=1}^{n}X_{i}, then for an integer s,
where Z is a standard normal random variable with mean 0 and variance 1.
Proof: Note that and .
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 S_{n}. In fact,
Corollary 1
We can estimate this further
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:
In this subsection we continue to consider net gains of fortune in the simple, fair, coin-tossing game (or symmetric random walk) S_{n} = X_{1} + + X_{n} composed of independent, identically distributed coin-toss random variables X_{i}, 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 S_{k-1} and S_{k} 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
Theorem 2 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
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)
a_{n} is asymptotic to b_{n} means the relative error between a_{n} and b_{n} goes to zero, although if a_{n} and b_{n} are large, the absolute error may be large. See the problems for an illustration.
An easy application of Stirling’s formula shows that
It then follows that
On the right side we recognize the Riemann sum approximating the integral:
For reasons of symmetry, the probability that k/n < 1/2 tends to 1/2 as n . Adding this to the integral, we get:
Theorem 3 (The Arcsine Law) For fixed with 0 < < 1 and n , the probability that the fortune spends a fraction of time k/n on the positive side is less than tends to:
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.
In practice, the formula provides a good approximation even for values of n as small as 20. The table below illustrates the approximation.
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:
[an error occurred while processing this directive] [an error occurred while processing this directive]
Last modified: [an error occurred while processing this directive]