2 jars of candy

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

2 jars of candy

1) There are two indistinguishable opaque jars that each contain 100 pieces of candy. People randomly choose one of the jars and reach in to pull out a piece of candy. When someone first discovers the jar they reached into is empty, how many pieces of candy would you expect to be in the other jar?

2) What is the relationship between the number of pieces of candy originally in each jar and the expectation?

The reason this problem actually came to mind is because I have two identical canisters of salt in my kitchen and I'm wondering if by serendipity it's a brilliant early-warning system that I need to go buy another two canisters. It's not a precisely accurate model, since the amount of salt I use varies from instance to instance, but it should be close enough for government work.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: 2 jars of candy

Spoiler:
1) I get about 11.2 pieces left: 2*(1/2)*2^(-99)*sum((100-k)*binomial(99+k,k)*2^(-k),k=0..99) and by simulation.

Edit:
2) Looks like if both jars have equal pieces of candy then as N grows large the expectation of the remaining pieces is approximately sqrt(N).

Edit: spoiler'd
Last edited by GreedyAlgorithm on Tue Oct 25, 2011 7:31 pm UTC, edited 1 time in total.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: 2 jars of candy

Spoiler:
If 0=X0, X1, X2, ... is a random walk on Z, then the expected number of pieces of candy remaining is exactly equal to E(|X2n|), where n is the number of pieces initially in each jar.

Proof: In each step, the difference between the numbers of candies in the two jars either increases or decreases by 1 with equal probability, so it can be modeled by a random walk. At step m, there are a total of 2n-m candies remaining in the two jars. The process stops when one of the jars is empty, i.e., |Xm|=2n-m, and the result is k=2n-m. Now, if we extend this random walk to step 2n, we have E(X2n=Xm). Furthermore, X2n >= Xm-k = 0 if Xm>0, and similarly X2n<=0 if Xm<0. Hence E(|X2n| given Xm) = |Xm| = k.

Thus E(k) = E(E(|X2n| given Xm)) = E(|X2n|)

It is well known that E(|X2n|) = O(n1/2), so this agrees with what GreedyAlgorithm posted.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: 2 jars of candy

Since neither solution so far includes a nice formula for the general case, I'll post mine:
Spoiler:
The number of ways to get the kth heads on the nth flip of a coin is C(n-1,k-1), writing C(i,j) for the number of ways to chose j elements from an i-element set. When flipping a fair coin repeatedly, the probability that the kth head occurs on the nth flip is therefore p(kth head on nth flip) = C(n-1,k-1)/2n. The probability the kth head or tails occurs on the nth flip is clearly twice that, and of course the kth head comes before the kth tails if and only if it comes on the nth flip for some n<2k. Since this has probability 1/2, we have $\sum_{n=k}^{2k-1} \frac{C(n-1,k-1)}{2^n} = \frac12.$
(*)

Supposing people choose the jar based on the flip of a coin, the first time someone finds a jar empty when they reach in will be on the 101st head or the 101st tails, whichever comes first. We are interested in the expected number of flips before the 101st head or 101st tails, which is
$$E(flips) = \sum_{n=101}^{201} \frac{2nC(n-1,100)}{2^n}$$
$$E(flips) = 202\sum_{n=101}^{201} \frac{C(n,101)}{2^n}$$
From * above, $$\sum_{n=k}^{2k} \frac{C(n,k)}{2^n} = 1.$$
$$E(flips) = 202\left(\sum_{n=101}^{202} \frac{C(n,101)}{2^n} \right)- \frac{202C(202,101)}{2^{202}}$$
$$E(flips) = 202\left(1-\frac{C(202,101)}{2^{202}}\right).$$
These numbers are too big for Google to handle, so using Stirling's approximation:
$$\frac{C(202,101)}{2^{202}} = \frac{202!}{101!^2 \cdot 2^202}$$
$${} \approx \frac{\sqrt{404\pi}202^{202}}{e^{202}} \cdot \left( \frac{e^{101}}{\sqrt{202\pi}101^{101}} \right)^2 \cdot \frac{1}{2^{202}}$$
$${} = \frac{\sqrt{404\pi}}{202 \pi} = \frac{1}{\sqrt{101\pi}}$$
which gives
$$E(flips) = 202*(1-\frac{1}{\sqrt{101\pi}}).$$
After E flips, E-1 coins are removed from one of the two jars, so 201-E coins remain in the other jar. Thus the expected remaining number of coins is approximately [imath]2\sqrt{\frac{101}{\pi}}-1 \approx 10.34[/imath]. (This disagrees slightly from what GreedyAlgorithm posted; I think the difference is that I'm considering the experiment to end when someone tries to take a candy from an empty jar, rather than when a jar is emptied.) In the general case with jars of k coins, it would be approximately [imath]2\sqrt{\frac{k+1}{\pi}}-1[/imath].
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: 2 jars of candy

Wolfram Alpha can do it even if Google can't! And you're right, the difference is exactly in whether we stop when emptying a salt shaker or when first trying to use a previously emptied salt shaker.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Dr.Buck
Posts: 22
Joined: Wed Oct 26, 2011 2:57 pm UTC
Location: "Sunny" Lancashire, UK

Re: 2 jars of candy

I decided to take a simpler, almost "fag-packet calculation" approach to this one, giving me a very different result to those above!

Spoiler:
I did take the liberty of making a couple of assumptions for this, namely that the jars are placed next to each other on the counter, and aren't swapped around regarding their position (ie, the left jar is always on the left).

So, quick searches tell me that 10% of people are left-handed, and life tells me that 100% of people are lazy so will always go for the jar on the side of their 'handed-ness'.

For every 10 people that take a candy (or a sweet here in the UK!), 10% will take from the left-hand jar. By the time the jars have had 110 visitors, there will be one sweet left in the right-hand jar, but 89 remaining in the left-hand jar.

Again, thinking that 10% of people are left-handed, Person 111 stands 90% chance of taking the final sweet from the right-hand jar, leaving (in my mad-hat solution!) 88.9 sweets remaining in the left-hand jar, but 0.1 sweets in the right.

Person 111 needs to be right-handed....

Actually, thinking of it, my solution isn't "People randomly choosing", but rather "randomly chosen people"....

I know my first post here is basically a load of nonsense, but it was fun!