# Oz’ Balls Problem: The Solution

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep doing it until left only with balls of the same color. How many balls will be left (as a function of n)?

Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get $cn$, but it intuitively seems far too much bias to still be $c \sqrt{n}$. I want to say $n^c$. At a wild guess, it’s either $c = \frac{2}{3}$or $c = \frac{3}{4}$, since those are the simplest exponents between $\frac{1}{2}$ and $1$.”  The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer $n^{3/4}$.

# Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun

Yeshu Kolodni and Lord Kelvin

### The question

In 1862, the physicist William Thomson (who later became Lord Kelvin) of Glasgow published calculations that fixed the age of Earth at between 20 million and 400 million years. Later in the 1890s Kelvin calculated the age of Earth by using thermal gradients, and arrived at an estimate of 100 million years old which he later reduced to 20 million years. (For much more interesting details see this Wikipedia article.)

The question was: what was the main reason for Lord Kelvin’s wrong estimation

a) Radioactivity – Heat produced by radioactive decay; this was a process unknown to science for decades to come.

b) Convection – The transfer of heat not through radiation or heat-conduction but through the movement of hot parts to the surface; this is a process familiar in home cooking.

Here is the answer and some discussion mainly based on what Yeshu Kolodny have told me.

# Test your Intuition/Knowledge: What was Lord Kelvin’s Main Mistake?

### The age of the earth

(Thanks to Yeshu Kolodny) We now know that the age of the earth is 4.54±1% Billion years.

From Wikipedea: In 1862, the physicist William Thomson (who later became Lord Kelvin) of Glasgow published calculations that fixed the age of Earth at between 20 million and 400 million years. He assumed that Earth had formed as a completely molten object, and determined the amount of time it would take for the near-surface to cool to its present temperature. His calculations did not account for heat produced via radioactive decay (a process then unknown to science) or convection inside the Earth, which allows more heat to escape from the interior to warm rocks near the surface.

What was the main reason for Lord Kelvin’s wrong estimation

a) Radioactivity – Heat produced by radioactive decay; this was a process unknown to science for decades to come.

b) Convection – The transfer of heat not through radiation or heat-conduction but through the movement of hot parts to the surface; this is a process familiar in home cooking.

# Taking balls away: Oz’ Version

This post is based on a comment by Oz to our question about balls with two colors:

“There is an interesting (and more difficult) variation I once heard but can’t recall where:

You have a box with n red balls and n blue balls. You take out each time a ball at random as before. But, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep as before until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

5) Some other behavior

You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

Here is the collective intuition regarding this problem

# Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes?

We are considering the stable marriage theorem. Suppose that there are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives?

Boris Pittel proved that on average a man will be matched to the woman in place log n on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked n/log n on her list.

We asked in the post “Test your intuition (19)”  what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno. Continue reading

# Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

### Stable mariage

The Gale-Shapley stable matching theorem and the algorithm.

GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most $n^2+n$ days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

### Random independent preferences

Question 1:  There are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.