Consider the following game: you have a box that contains one white ball and one black ball. You choose a ball at random and then return it to the box. If you chose a white ball then a white ball is added to the box, and if you chose a black ball then a black ball is added to the box. Played over time, what is the probability that more than 80 percents of the chosen balls are white?
This question is related to the fact that professional players can emerge in pure games of luck that was mentioned in the previous post.
Combinatorics and more 
I would say 50%.
I think each combination of white and black balls in the box is equally likely.
So it would be 20%.
“Played over time, what is the probability that more than 80 percents of the chosen balls are white?”
This sentence is not completely clear for me.. I give the answer for my interpretation, which has the easiest solution 🙂 i.e. you are asking for the limit probability as the number of extractions goes to infinity.
At step N all the possible combinations of B balck balls and W white balls such that N+1=B+W are equi-probable, and they encode the number of extractions that far. So the probability would be 20%.
May I ask why this is related to the previous topic?
OK, I spoke too fast …
I would say, w/probability close to 100% one of the two choices becomes the overwhelming majority. Then the answer would be (50-o(1))%, where the o(1)-factor decreases with the number of trials. Moreover, I would guess that the decrease is very fast, something like 1/2^{\Omega n}
The probability goes to zero as large number of balls are selected. This can be seen by observing that at any time the probability of choosing a white ball is 0.5.
So, intuitive this is the dominant fractions. For all the other fractions the probability will go to zero exponentially.
This can be proven rigorously by defining a Martingale. Let S_n be the number of white balls in the bag after n selections. Define
X_n = 2S_n/(n+2).
Then X_n is a martingale. Hence
E(X_0) = E(X_n).
Number of white balls selected is S_n-1. Thus as n goes to infinity, X_n is twice
the long term average. Now E(X_0) = 1. This gives
lim_{n \to \infty} E(S_n)/(n+2) = 0.5.
Now by using Azuma’s inequality we can show that probability of having more than 80% white balls gors to zero.
Interesting!
When worked out, one can see that P[#white balls = a, #black balls = b] = 1/(a+b). So the answer is 20%.
I second Zeno’s answer. One color will dominate
with very high probability. So the right answer does
indeed tend to 0.5.
I agree with the 50%, because in very high probability one of the colors will dominate.
Actually, this is a case which in physics is called spontaneously broken symmetry, because although the problem is completely symmetric between the colors, the answer breaks this symmetry, and indeed it happen in many more problems in physics.
Consider when there are n balls in the box. It is elementary to verify that the probability of having k white balls is *exactly* k/(n-1) for k=1,2,…,n-1.
By induction:
Pr[k white balls in round n+1]
= Pr[k-1 in round n]*(k-1)/n + Pr[k in round n]*(n-k)/n
= (k-1)/[n(n-1)] + (n-k)/[n(n-1)]
= 1/n
Thus the answer is, in fact, 20%.
Should have said probability of having exactly k white balls is exactly 1/(n-1) when there are n balls, not k/(n-1). Rest of the argument unchanged.
I guess, I should call back my earlier post 🙂
It is a martingale, and therefore there is no reason why the demographics should jump to one of the two edges with overwhelmingly high probability.
My own confusion was caused by the first impression that the only equilibrium points are the edges. But that is not true, simply because the process can be described by a martingale (i.e., having, say, 80% of white balls only results in 80% expectation of a white ball in the next round, and not 100% as my immediate intuition suggested).
The exact answer would, as people said above, require some calculations, but the distribution is certainly more flat than I originally thought. In other words, as the number of trials grows, the probability of 80% would remain 1/2-\Omega(1), in my (updated) opinion.
Btw, just to further challenge my intuition, I would predict that the expected number of “switches” between 99% of blacks and 99% of whites goes to infinity as the number of trials goes up (this one I would expect to grow as something like log(n)).
Am i right??
Zeno: since you already figured out that the percentage of white balls is a martingale, you immediately know that having infinitely many “switches” is impossible. In fact, as a bounded martingale, it must converge.
Ori: Of course, you are right! Probability of a “switch” happening after n trials would be something like 1/2^n, but that clearly doesn’t mean unbounded expected number of switches, as this is just a converging geometric series 🙂
Let f_n(r) = Prob(w_n > r.n), where w_n denotes the number of white balls in the box, b_n=n-w_n denotes the number of black balls in the box, and r is fixed real in the unit interval [0,1]. One could easily see that Prob(w_n > r.n) = Prob(b_n > r.n) = Prob(w_n = (1-r).n) = 1 – Prob(w_n > (1-r).n) – Prob(w_n = (1-r).n). In other terms, f_n(r) = 1 – f_n(1-r) – Prob(w_n = (1-r).n). In the limit case (i.e. n goes to infinity), one would expect (sorry for the lack of details!) Prob(w_n = (1-r).n) to go to 0, and f_n to ‘converge to a decent’ function f such that f(r) = 1 – f(1-r) for every r in [0,1] and f(0)=1. Assuming enough ‘good’ behavior in f, one could say that f(r)=1-r.
very nice and simple @ highschool.
its non-intuitive that all WB combinations @ step N are equiprobable.
given that, answer is 0.2
I would also say 50%, since one of them will dominate.
Suppose we take a movie of this process, and then watch it backwards. What to we see? We see Alice walk up to a bin of balls, count them, then add a ball whose color is chosen (randomly) to leave the color probabilities (over an ensemble of movies) invariant.
Nonetheless, it is easy to see that in any given movie, if the bin is predominantly black, then Alice’s added ball will make it more black (and similarly for white). Hence everyone who answers “50%” is correct — in the long run every movie shows a large bin filled almost completely with all-black and all-white balls.
Does this situation ever occur in real life? Absolutely! From a quantum mechanical point of view, all sensors (including biological sense organs like eyes, ears, and even touch) are mechanisms that are designed to work in precisely this way. That is, quantum measurement processes (generically) provide an unbiased estimate of (a property) of a quantum state, but in doing so, they (generically) create a Hilbert backaction that “drags” the (quantum) state to agree more closely with the (classical) measurement result.
Thus, the familiar emergence of a (low-dimension) classical world from a (high-dimension) quantum world is mathematically parallel to the emergence of (nearly) all-black and (nearly) all-white bins from a random starting state in Gil’s toy problem.
no one here used Random Walk theory?
My gut intuition was that the process would diverge to the ends, giving 50%. But I then noticed that the probablility of being precisely at either end was only 1/n, which made me suspect that my first guess was wrong. I then did the actual computation, and found that, for fixed b+w, all combinations of b black balls and w white were equiprobable. So the answer is 20%.
I am now trying to formulate an intuitive description of why my first answer was wrong. So far, I have “random walks tend to stay very centered (by the law of large numbers), so it requires a stronger than linear bias to make them diverge to the ends.”
That intuition isn’t very helpful though. Suppose that the probabilities were changed to
and 
(We draw twice, with replacement in between, and do nothing if we draw balls of different colors.) Is that a strong enough bias to make the process diverge to the ends? Without computations, I have no idea!
David Speyer is right! (counter to my first intuition).
And there is natural generalization of this problem whose answer is even more counter-intuitive.
Suppose that if Alice picks a white ball, she returns that ball and n more white balls to the bin, and otherwise adds n black balls.
Test your intuition: what is the asymptotic distribution of the number of white balls for n=2 ?
Is it flat, the same as for n=1?
Or is it peaked at all-black and all-white, as intuition would suggest?
Or is there a fascinating third alternative? 🙂
Using Random Walk theory as a ready-made result, as dodmoshe suggests, leads me to think that the probability is 50%. As v8r explains in their first post, I think the result is overwhelmingly dominated by the first choice. A Monte Carlo simulation supports my intuition, and I trust my computer more than I do my brain.
It seems I made a mistake in my simulation… David Speyer got it right, it seems.
Here’s my attempt:
Let us say at any point there are w white and b black balls. The probability of picking a white ball here is:
p_w = w/(w+b).
For the next pick,
p_w+ = p_w (w+1)/(w+b+1) + (1-p_w) w/(w+b+1),
where the two terms denote whether you have a white or black ball next round. If you expand that out,
p_w+ = w/(w+b)
So the probability is constant and since we started off with 1 w and 1 b, it remains at 0.5.
Thus the chances of having 80% white balls over time is the same as the probability of having 80% heads in coin tosses over time. As N tends to infinity the probability tends to 0.
The relation with the post on games of luck is this: if you have a pure game of luck, like the one in the present post, where the odds depends on your previous performences, a group of “professional players” can emerge.
Pingback: Test Your Intuition (10): How Does “Random Noise” Look « Combinatorics and more