Expected value of a milion dollar (equal?) division

I've heard this riddle a while ago and it is quite interesting.

Say I've got two sons and one million dollars to spare. Each boy gets one dollar as a start and from there I give them dollar by dollar with a chance of:

First son: $\frac{A}{A+B}$.
Second son: $\frac{B}{A+B}$.

Where A represents that amount of dollars the first son has at the current stage, and B represents the amount of dollars the second son has at the current stage.

At the first stage since they both have $1$ dollar it mean that the next dollar has $\frac{1}{2}$ chance to go each of the sons. Say it goes to the first son then at the next stage the first son has $\frac{2}{3}$ of getting the next dollar while his brother has only $\frac{1}{3}$ of getting the dollar.

What is the expected value of the losing son?

• More of a mathematics question than a puzzle – jaydm26 May 30 '16 at 16:35
• Possible duplicate of Shooting Free Throws – f'' May 30 '16 at 17:39
• @f'' it is not an exact duplicate : in this puzzle there are two players and we only consider the looser (very similar but not exact duplicate) – Fabich May 30 '16 at 19:50
• This one is phrased and dressed up differently, but they are the same mathematics. $\rm A$ and $\rm B$ correspond to the win column and the loss column. The other question is about the probably distribution of the numbers of balls in the loss column. They require exactly the same computations. – Peregrine Rook May 31 '16 at 19:46

The expected amount of money earned by the son who gets less money is very close to $\$250,\!000$. We can show this by calculating the probability that son A has$n$dollars after$k$dollars (including the first two) have been handed out. Denote this probability by$P_k(n)$. We can find the following recurrence: $$P_{k+1}(n)=\frac{(n-1)P_k(n-1)}k+\frac{(k-n)P_k(n)}k$$ which is obtained by noting that, for the son to have$n$dollars at the step$k+1$, he must have either had$n-1$dollars in the previous step and earned another dollar, or have had$n$dollars in the previous step and not earned another. If we calculate a few values of this, the pattern quickly becomes apparent: For any$n$between$1$and$k-1$, we have $$P_k(n)=\frac{1}{k-1}.$$ One may show this inductively on$k$by using the above formula and computing. Then, the expected value of the losing son is just $$\sum \min(n,k-n)P_k(n)=\sum_{n=1}^{k-1}\frac{\min(n,k-n)}{k-1}$$ where$k=10^6$. However, the sum over$\min(n,k-n)$for even$k$is just$\frac{k^2}4$. Thus, the expected value is $$\frac{k^2}{4(k-1)}=\frac{\250,\!000,\!000,\!000}{999,\!999}=\250,\!000.\overline{250000}\approx \250,\!000$$ • There's probably some combinatorial interpretation to this fact, or some way to see it without the "guess and induct" strategy. I don't know what it is. – Milo Brandt May 30 '16 at 17:05 • I haven’t made the “one giant leap” of intuition; but I can contribute my$2¢$“small step”: we know that if each decision is made on a$50 / 50$basis, the probability distribution will be a normal distribution — a bell curve. Obviously the$\frac{A}{A+B} ~/~ \frac{B}{A+B}$division makes the extreme outcomes more likely and the mean outcome less likely — and it provides exactly the right bias to flatten the bell curve into a uniform distribution, with every possible outcome equally likely. It strikes me as rather elegant, and I’d like to see an accessible explanation of why this works. – Peregrine Rook May 31 '16 at 19:35 • @MiloBrandt Take one million + 1 cards, numbered 0 to one million. Initially, there is a deck containing only card #0. At step n, card #n is added to a random place in the deck. If there are currently A-1 cards above #0, and B-1 below, then the probability that the next card is above #0 is A/(A+B). Thus, the number of cards above #0 at the end is equal in distribution to one of the brother's winnings. But the number of cards above #0 is uniform, since #0 is equally likely to be anywhere in the deck. The whole process is just a fancy way of uniformly shuffling the deck. – Mike Earnest Oct 10 '16 at 20:03 One functional answer is$\frac{1 000 000 - |A-B|}{2}$This is the amount the brother with the least cash wins without needing to know specifically which brother won. given, |A-B| is the difference = (winner - loser), we know that 1 000 000 = winner + loser it follows that 1 000 000 - (winner - loser) = winner + loser - (winner - loser) so 1 000 000 - (winner - loser) = 2(loser) which boils down to$\frac{1 000 000 - (winner-loser)}{2}$= loser =$\frac{1 000 000 - |A-B|}{2}$• Answers without explanation are usually deleted. Can you please edit your answer and explain how you have found this result ? – Fabich May 30 '16 at 19:46 • Okay, I added an explanation/proof. Thanks. – Chris McCowan May 30 '16 at 20:05 • It seems to me that all you've done is found a clever way to express$\min(A,B)$without using the$\min$function, using absolute value instead. OK, that's a neat trick, but it's not what the question is asking for. What you've done is like saying that, if I flip a fair coin$10$times, the number of heads will be$10-T$, where$T$is the number of tails. But the question is asking for the expected value, which, in my little coin-tossing example, is$5\$. – Peregrine Rook May 31 '16 at 7:00