Limit Theorems

An archer is aiming at a circular target of radius 20 inches. Her arrows hit on average 5 inches away from the center, each shot being independent. Show that the next arrow will miss the target with probability at most $\frac{1}{4}$.

Show that $\frac{1}{4}$ is the best possible estimate of the probability of missing the target in Problem 12.1; that is, in certain circumstances, the probability can be equal to or be arbitrarily close to $\frac{1}{4}$.

Show that if a non-negative random variable has finite expectation $\mathbb {E}\left[X\right]$, then

for any $C>0$.

Prove the following theorem, known as the Chebyshev inequality. - Theorem 12.1 Let $X$ be a random variable with finite expectation $\mathbb {E}\left[X\right]$ and finite variance $\operatorname {Var}\left[X\right]$. Then,

for any $C>0$. The Chebyshev inequality provides a very rough estimate, whose strength comes from its universality. It allows us to estimate the likelihood of a deviation of a random variable $X$ from its mean value $\mathbb {E}\left[X\right]$ even if nothing is known about the distribution of $X$.

A fair coin is tossed independently $n$ times. Let $S_{n}$ be the number of heads obtained. Use the Chebyshev inequality to find a lower bound of the probability that $\frac{S_{n}}{n}$ differs from $\frac{1}{2}$ by less than 0.1 when a) $n=100$, b) $n=10,000$, and c) $n=100,000$.

Find Chebyshev's lower bound of the probability that $\frac{S_{n}}{n}$ in Problem 12.5 differs from $\frac{1}{2}$ by less than 0.01 when a) $n=100$, b) $n=$ 10,000 , and c) $n=100,000$.

In the same setting as in Problem 12.5, demonstrate that

for any $\varepsilon >0$.

Consider an unfair coin with probability $p$ of heads. Let $S_{n}$ be the number of heads obtained when the coin is tossed independently $n$ times. Write down a limit similar to that in Problem 12.7 and prove it.

We throw $n$ dice independently and add the points, denoting the sum by $S_{n}$. Extend the results in Problems 12.7 and 12.8 to this case.

Prove the following weak law of large numbers. - Theorem 12.2 Let $X_{1}, \ldots , X_{n}$ be independent identically distributed random variables with finite expectation and variance and let $S_{n}=X_{1}+\cdots + X_{n}$. We set $a=\mathbb {E}\left[X_{i}\right]$, which is the same for each $i$. Then,

for any $\varepsilon >0$.

Using the weak law of law of large numbers, prove that for every continuous function $f:[0,1] \rightarrow \mathbb {R}$,

uniformly in $x \in [0,1]$ as $n \rightarrow \infty$.

Let $S_{n}(x)$ denote the number of 1 's among the first $n$ digits of the binary expansion of $x \in [0,1]$. Show that

for all $x$ 's in a set of Lebesgue measure 1 in $[0,1]$.

Show that if $X$ has finite expectation, then $\mathbb {E}\left[a_{n}\right]=\mathbb {E}\left[X\right]$ and

with probability 1.

Show that

Show that if $X$ has finite expectation and variance, then $\mathbb {E}\left[\sigma_{n}^{2}\right]= \operatorname {Var}\left[X\right]$ and

with probability 1.

Let $(\Omega , \mathcal{F}, P)$ be a probability space, $\Omega$ being the set of all possible outcomes of a random experiment. Take two events $A, B \in \mathcal{F}$ with $\mathbb {P}\left(B\right) \neq 0$. If the random experiment is repeated independently $n$ times, let $S_{n}$ be the number of times the outcome is in $B$. Among these $S_{n}$ outcomes in $B$, there will be $R_{n}$ outcomes that are also in $A$. Show that

with probability 1.

Prove that if a sequence of random variables $X_{n}$ converges almost surely to $X$, then it converges to $X$ in probability.

Prove that if a sequence of random variables $X_{n}$ converges to $X$ in probability, then it converges to $X$ in distribution.

Demonstrate that for every real number $x$,

Estimate the probability that the number of heads in 10,000 independent tosses of a fair coin differs by less than $1 \%$ from 5000 .

What is the probability that the number of heads will be greater than 5100 ?

How many independent tosses of a fair coin are required for the probability that the average number of heads differs from 0.5 by less than $1 \%$ to be at least 0.99 ?

Three candidates $A, B$, and $C$ are running for President. In order to predict the outcome of the election, a number of people, each selected at random and independently of the others, are asked their choice. The predicted percentage $p_{X}$ of votes for a each candidate $X \in \{ A, B, C\}$ is worked out by dividing the number of people in the sample who are going to vote for $X$ by the total number of people in the sample. How many people need to be in the sample to substantiate the following claim: For each candidate $X$, the probability that the predicted percentage $p_{X}$ is correct to within $1 \%$ is at least 0.95?

What sample size will make it possible to make the same claim if there are just two candidates? And when there are $n$ candidates? (Exclude $n=1$, even though this case is not uncommon in certain political systems.)

Suppose that a sample consisting of $n$ men is used in the survey described in Problem 7.22 to establish the likelihood of being a bathroom singer. Each person is asked to toss a die and answer YES or NO. The probability $\mathbb {P}\left(Y\right)$ of answering YES is estimated by the average number $P_{n} Y$ of YES answers (that is, the number of YES answers divided by $n$ ). Because $\mathbb {P}\left(Y\right)$ is connected with the probability $\mathbb {P}\left(S\right)$ of being a bathroom singer by $\mathbb {P}\left(Y\right)=\frac{1}{6}+\frac{2}{3} \mathbb {P}\left(S\right)$ (see Solution 7.22), the estimate $P_{n} S$ of $\mathbb {P}\left(S\right)$ is then computed from the formula

Estimate the probability that $P_{n} S$ differs from $\mathbb {P}\left(S\right)$ by more than $\varepsilon >0$. Then, find how large a sample is needed to make sure that $P_{n} S$ differs from $\mathbb {P}\left(S\right)$ by no more than 0.01 with probability at least 0.95 ? Compare this to the sample size needed when the survey question is answered directly without tossing a die.