fun probability question from an old Putnam

[gumpzilla]

Saw this question yesterday, and I liked it quite a bit:

A basketball player sets out to shoot 100 free throws. He makes his first, and misses his second. From that point on, the probability that he makes free throw number N is equal to the percentage of his free throws that he's made already. So, on shot 3, he's 50/50 to hit. If he makes shot 3, then on shot 4 he will make his shot 2/3 of the time, etc.

After he's shot his 100 free throws, what is the probability that he made exactly 50?

[Silent A]

Initial guess: very very low.

Reason: the distribution will be bi-modal with lots of high and low totals because as soon as he gets above or below 50% (most noteably after the third shot) his precentage will steadily drift away from 50%.

[PairTheBoard]

[ QUOTE ]
Initial guess: very very low.

Reason: the distribution will be bi-modal with lots of high and low totals because as soon as he gets above or below 50% (most noteably after the third shot) his precentage will steadily drift away from 50%.

[/ QUOTE ]

I'd think the proportion would tend to remain at the level it has achieved and spread out above and below it. Like a bunch of waves interfering with each other. The (1,0,1...) wave interferes with the (1,0,0...) wave. And so on.

There's got to be some kind of breakthrough insight that lets you simplify this. The N-tuples of 0,1's are no longer equally likely. But you might make an inductive argument according to the probability for classes C(N,n). ie. the class of tuples of length N containing n 1's. See how that probability progresses for C(3,n), C(4,n), ... deduce a closed form for it, then prove it works by induction.

PairTheBoard

[Silent A]

Hmm, figured out the answer while I was away.

My argument above actually only shows that total = 50 is not a local maximum on the probability distribution. The actual probability distribution isn't really bi-modal at all.

Instead, the above argument can be extened to claim that the probability distribution of final totals doesn't have any local maxima. It goes like this ...

At a given point during the shooting, the player will have hit "i" baskets after "n" throws. The odds of him getting the next basket is therefore i/n. So after the (n+1)th shot he will have hit either i or i+1 baskets and his probability of getting the following basket will be either i/(n+1) or (i+1)/(n+1). Notice that the fraction of future successful shots will tend to diverge away from i/n. This is true so long as 0 < i < n (in the problem described, this is always true since he starts off with one miss and one hit).

Now note that if a local maxima exists in the probability distribution, then small movements away from a local maximum will tend to move back towards the local maximum (i.e. local maxima should be stable to a certain extent). However, from the above argument, no point can be stable and therefore no point can be a local maximum. We also know that because the problem is inherently symmetrical, the final probability distribution should also be symmetrical. This means that the distribution should be either perfectly flat, or shaped like a "U" (low in the middle and high on both ends).

Now if only I could come up with an argument to suggest that the ere are no local minima either, I could show that the final probability distribution is perfectly flat without making any calculations at all.

And if the probability distribution is perfectly flat then the answer is 1/99 since the final total must be at least 1 and no more than 99.

P.S. I have an analytical proof, but I'll leave it for someone else.

[Tom1975]

I ran a monte carlo simulation consisting of 65,536 trials (I used Excel). Results in white:

<font color="white">The distribution of the number of shots made is indeed perflectly flat. All numbers between 1 and 99 are equally likely. </font>

[bigpooch]

Interesting!

Simply prove by induction that if P(k; n) is the probability
of k free throws in the first n attempts, that

P(k; n) = 1/(n-1) for 1&lt;=k&lt;=(n-1) for any n&gt;=2.

The proof is simple: just note that

P(k; m+1) = P(k-1; m)[(k-1)/m] + P(k; m)[1-(k/m)] even
when k=1 (then the (k-1)/m term then is zero).

[Silent A]

I'll put my analytical solution in white ...<font color="white">

1) note that after 3 shots he will have either 1 or 2 baskets with equal probability. To generalize, after n=3 the probability of having "i" baskets is 1/(n-1), or:

p(i,n) = 1/(n-1), where 0 &lt; i &lt; n

2) the probability of the player hitting the next basket is:

p(b|i,n) = i/n

and the probability of missing the next basket is:

p(m|i,n) = 1 - i/n = (n-i)/n

3) after n+1 baskets, the probability of having hit exactly "i" baskets is:

p(i,n+1) = p(i,n)*P(m|i,n) + p(i-1,n)*P(h|i-1,n)
= 1/(n-1)*(n-i)/n + 1/(n-1)*(i-1)/n
= (n-i+i-1)/n/(n-1)
= (n-1)/m/(n-1) = 1/n

4) therefore if all possible totals are equally likely after n baskets, then all possible totals after n+1 baskets are also equally likely

5) all possible totals after 3 baskets are equally likely

6) by induction, all possible totals are equaly likely for n &gt; 3

7) after n=100 throws all totals have a probability of 1/(100-1) = 1/99.</font>

8) the probability of hitting exactly 50 baskets after 100 throws is 1/99.

[Justin A]

Without reading the other responses I'm going to guess (1/99) is the answer based on some possibly faulty calculations.

[gumpzilla]

[ QUOTE ]
Interesting!

Simply prove by induction that if P(k; n) is the probability
of k free throws in the first n attempts, that

P(k; n) = 1/(n-1) for 1&lt;=k&lt;=(n-1) for any n&gt;=2.

The proof is simple: just note that

P(k; m+1) = P(k-1; m)[(k-1)/m] + P(k; m)[1-(k/m)] even
when k=1 (then the (k-1)/m term then is zero).

[/ QUOTE ]

Yep; this was the approach I took.

[johnnyrocket]

u guys are way smarter than myself