8
$\begingroup$

There're two cornucopias of infinite volume, each with one gold coin in them. Right now $t=0$. A new coin will be born at $t=\frac{2^n-1}{2^n}$ for every positive integer $n$. Each new born coin will appear in the first cornucopia with probability $\frac{x}{x+y}$ and in the second with probability $\frac{y}{x+y}$, where $x$ and $y$ are the current number of coins in the two cornucopias respectively.

At $t=1$, infinitely many gold coins have been born, so we know at least one cornucopia contains infinite coins.

Question: What is the probability that both of them contain infinitely many gold coins?

$\endgroup$
8
  • $\begingroup$ If you add a drop of water to something that is not an ocean, will it become an ocean? $\endgroup$
    – Bass
    Commented Jul 31, 2022 at 15:04
  • 4
    $\begingroup$ I think I know the answer, but I voted to close this question, so I'm not posting it. I voted to close because in my opinion this is a math problem rather than math puzzle. $\endgroup$
    – melfnt
    Commented Jul 31, 2022 at 16:15
  • 1
    $\begingroup$ Since there's no "vote to keep open" button, I'll just have to put my opinion here: if there's a straightforward mathematical way to solve this, you probably need at least a maths major to see it, and those of us lacking one would be delighted to be shown the approach. (Apart from that, surely this must count as a puzzle because of the seeming paradox with the infinities and the order (if any) in which they arise.) $\endgroup$
    – Bass
    Commented Jul 31, 2022 at 21:41
  • 1
    $\begingroup$ I’m voting to close this question because it's a math problem rather than a puzzle $\endgroup$
    – JLee
    Commented Aug 2, 2022 at 10:59
  • 2
    $\begingroup$ @JLee Why not just leave it open, and let people who think it IS a math puzzle have their fun? I had a great answer, but now I cannot share it :( $\endgroup$ Commented Aug 5, 2022 at 20:12

2 Answers 2

5
$\begingroup$

The probability that both of them contain infinitely many coins is

1

Let us label the two cornucopias A and B and let us look at an example of a finite sequence:

n    2    3    4    5    6    7    8    9   10   11   12   13   14   15
A    1              2    3    4         5    6         7         8    9
B    1    2    3                   4              5         6
P        1/2  2/3  1/4  2/5  3/6  3/7  4/8  5/9  4/10 6/11 5/12 7/13 8/14

Now,

We can get the probability of this particular sequence by multiplying the probabilities of each step. However, we should notice here that the product of the probabilities only depends on the final numbers of coins in the cornucopias and doesn't actually depend on the order in which the coins appeared! If we denote the final numbers of coins by a and b, the denominators will always take every value between 2 and a+b-1 and the numerators will take the values [1,a-1] and [1,b-1] so the final product will be

$\frac{(a-1)!(b-1)!}{(a+b-1)!}=\frac{1}{(a+b-1)\binom{a+b-2}{a-1}}$

To get the total probability that the final number of coins ends up as a and b, we should multiply this probability with the number of possible orderings $\binom{a+b-2}{a-1}$ so that the probability becomes

$P(n_A=a, n_B=b)=\frac{1}{a+b-1}=\frac{1}{n_{tot}-1}$,

which doesn't depend on the actual values of a and b, only the number of total coins! This means that every end result is actually equiprobable!

Now, the probability that either one of the cornucopias will have no more than m<n/2 coins is clearly

$P(n_A\leq m \text{ OR } n_B\leq m)=\frac{2m}{n-1}$.

If we now look at the infinite case, then the probability that one of the cornucopias will have at most some finite m number of coins is

$P(n_A\leq m \text{ OR } n_B\leq m)=\lim_{n\rightarrow\infty}\frac{2m}{n-1}=0$

$\endgroup$
7
  • $\begingroup$ I like the result in the middle here. The one bit I think still needs expanding is the last step. It looks like you've proved it by taking the limit for a fixed $m$ but shouldn't we have to consider the limit over all possible values of $m$ and how does this limit then make sense? $\endgroup$
    – hexomino
    Commented Aug 2, 2022 at 10:47
  • $\begingroup$ @hexomino The limit is for any value below any fixed finite m, so this should show that no matter how high (finite) m we choose, the probability that one of the cornucopias has less coins than m is 0. $\endgroup$
    – user39583
    Commented Aug 2, 2022 at 10:52
  • $\begingroup$ I still think there is a little subtlety needed to finish the argument. As you say, the limit holds for values below "fixed finite m". That means, if I fix $m$ then the probability of seeing a number of coins below $m$ is 0. But this is slightly different to the question being asked which does not fix $m$ - in essence we must look at the limit as $m \rightarrow \infty$ also. I know it looks like I'm being pedantic but I think there will be some element of measure theory involved to finish the argument. $\endgroup$
    – hexomino
    Commented Aug 2, 2022 at 11:23
  • 1
    $\begingroup$ @hexomino Another way of stating the final result is that no matter the m, the probability that both cornucopias exceed m coins is 1. If we know that the cornucopias have a larger number of coins than any arbitrary finite number, then they must contain an infinite number of coins. $\endgroup$
    – user39583
    Commented Aug 2, 2022 at 11:27
  • $\begingroup$ Let me put it to you this way, suppose I pick a specific infinite sequence of 1s and 2s, what is the probability that my sequence will match the cornucopia sequence? Now suppose I have a number of friends $n$ who can pick different sequences to me, what is the probability that one of us will match the cornucopia sequence? What if I have an infinite number of friends? $\endgroup$
    – hexomino
    Commented Aug 2, 2022 at 11:53
3
$\begingroup$

I will use the term "urn" instead of "cornucopia," in line with Pólya's urns.

In order to show there are infinitely many coins in both urns, we just need to show that if there are currently $x$ coins in the left urn, then with probability one, there will eventually be $x+1$ coins in the left urn. So, suppose there are currently $x$ and $y$ coins in the left and right urns, respectively. Let us find the complimentary probability that every subsequent coin will be added to the right urn. This is given by the following infinite product: $$ \frac{y}{x+y}\cdot\frac{y+1}{x+y+1}\cdot\frac{y+2}{x+y+2}\cdot\frac{y+3}{x+y+3}\cdots $$ An infinite product is an infinite limit, so at this point, we need a little calculus. It can be shown that an infinite product of the form $\prod_{i=1}^\infty (1-r_i)$, where $r_i$ are real numbers between $0$ and $1$, converges to a nonzero number if and only if $\sum_{i=1}^\infty r_i<\infty$. So, we should add up one minus all of the fractions being multiplied above, which is $$ \frac{x}{x+y}+\frac{x}{x+y+1}+\frac{x}{x+y+2}+\dots $$ This sum indeed diverges, because it is $x$ times a tail sum of the Harmonic series. Therefore, the original product is zero, so the left urn will get infinitely many coins.

$\endgroup$
2
  • $\begingroup$ “In order to show there are infinitely many coins in both urns, we just need to show that if there are currently x coins in the left urn, then with probability one, there will eventually be x+1 coins in the left urn.” Why does this suffice? I think this only shows with probability 1 there will be at least x+1 coins in the left urn at $t=1$. $\endgroup$
    – Eric
    Commented Aug 10, 2022 at 7:29
  • $\begingroup$ @eric coin x+1 is added to the left urn at a time $t<1$ at which point there are still a finite number of coins in each urn. Substitute the current number of coins in each urn into the same formulae, and you've proved that there will eventually be at least x+2 coins in each urn, and so on ad infinitum. $\endgroup$
    – Steve
    Commented Aug 10, 2022 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.