# Limit Theorem applicability

A basketball player throws 100 times. On the first throw the ball is always in, on the second - always out. For all consequent throws the probability of hitting is equal to percentage of all successful throws divided by total number of throws done.

What is the probability the he will score total 50 balls out of 100?

This is not a homework, I'm just anxious about the solution of this problem.

My ruminations:

There are random events $E_1, E_2, \dots, E_n$. $E_1$ always happens, $E_2$ never. For any $E_n$ with $n > 2$:

$p(E_n) = \frac{\sum_{k=1}^{i-1}{x_k}}{i-1}$

${x}$ a sequence of random variables, such that: $x_i = 1$ if event is happened, $0$ otherwise.

So, $P (\sum_{i=1}^{100}{x_i} = 50) = ?$

Is it true that this problem can be solved with Limit Theorem? Consequent events are dependent on outcomes of previous; can the Limit Theorem handle that? Could give me a pointer on how can I solve this problem?

-
You could've found the solution yourself, if you just tried calculating the probabilities for a small number of free throws. Trying small numbers is always a good idea. –  Yuval Filmus Nov 3 '10 at 23:30
Got it.Thank you. –  Dmitry Cherkassov Nov 3 '10 at 23:42

The probability is $1/99$.

Denote by $P(a,b)$ the probability that after $a+b$ shots, exactly $a$ were in and $b$ were out. Then $P(1,1)=1$ and

$P(a,b) = \frac{a-1}{a+b-1} P(a-1,b) + \frac{b-1}{a+b-1} P(a,b-1)$

We prove by induction on $a+b$ that $P(a,b) = 1/(a+b-1)$. When $a+b = 2$, this is true. Otherwise

$P(a,b) = \frac{a+b-2}{a+b-1} \cdot \frac{1}{a+b-2} = \frac{1}{a+b-1}$

-
Which is a really nice result, I think. The linear biasing exactly cancels with the Law of Averages, producing a uniform distribution. –  Oscar Cunningham Nov 3 '10 at 23:27

Some additional references may be of interest. This result is a well-known feature of Polya's urn model starting with one ball each of two different colours.

For instance, this problem is Exercise 5.9 in the first edition of Introduction to Stochastic Processes by Lawler.

There is also a detailed analysis in section 2.4 of Markov Chains and Mixing Times by Levin, Peres, and Wilmer.

I expect that it can be found in other books on probability and Markov chains.

-

This is problem B1 from the 2002 Putnam exam. It is useful to generalize and allow for any number of free throws. We can then prove the stronger result:

Theorem. For any number of free throws $n$, and any $i \in [n-1]$ the probability of hitting exactly $i$ free throws after $n$ attempts is $\frac{1}{n-1}$.

Proof. We proceed by induction on $n$. The base case $n=3$ is trivially trivial.

For the inductive step, assume the result for $n-1$, and let $i \in [n-1]$. There are two ways to make exactly $i$ shots after $n$ attempts:

1. make $i-1$ shots after $n-1$ attempts and clutch up on your final attempt, or

2. make $i$ shots after $n-1$ attempts and epic fail the final attempt.

By induction, the required probability is

$\frac{1}{n-2} \frac{i-1}{n-1} + \frac{1}{n-2} \frac{n-1-i}{n-1} = \frac{1}{n-1}$.

So the answer to your particular question is $\frac{1}{99}$.

-
Thank you. BTW, how strongly is incorrect my path to solution? –  Dmitry Cherkassov Nov 3 '10 at 23:45
I wouldn't be too hard on yourself, but I'd suggest getting your hands dirty a little before trying to kill a mosquito with a cannon. Also, knowing where the problem comes from can be a big help in finding the correct path to the solution. Since this is a Putnam problem, there is likely to be an elegant solution using elementary techniques (in this case induction). –  Tony Huynh Nov 4 '10 at 9:01

Here is an enumerative proof. We can think of the process as an urn with balls of two colors, say black and white. In the beginning, there is one ball of each color. In each round we pick one of the balls and duplicate it.

Let us count the number of ways to get $a+1,b+1$ balls after $a+b$ rounds. This involves adding $a$ black balls and $b$ white balls. The first time a black ball is added, there is no choice. The next time, we can choose any of the two existing balls, and so on. In total, there are $a!$ choices for black balls, and $b!$ choices for white balls. We also have to choose in which round we add which color - there are $\binom{a+b}{a} = (a+b)!/a!b!$ such choices. In total, we get $(a+b)!$ choices.

We've shown that the number of ways to get $a+1,b+1$ balls depends only on $a+b$. In fact, we can directly calculate the probability by calculating the total number of possible moves. In the first move we pick one of two balls, then one of three balls, and so on. So in $a+b$ rounds there are $(a+b+1)!$ possible moves. We conclude that each outcome has probability $1/(a+b+1)$.

-
For an intuitive symmetry-based argument why any number of successful throws between $0$ and $99$ is equally likely see this answer.