I was playing with my son with a large marble run we built together—that's a series of tracks and splitters for the marbles to roll down into one of several possible exits. With three possible exits, each with a catcher (so the marbles don't roll across the floor), we played a game:
We called one catcher "his" and one catcher "mine." We each had a separate entry point to drop marbles into at the top of the run. We each tried to empty our catcher by dropping marbles from our catcher into our entry point, and kept on going until all the marbles were in the third catcher.
I started trying to figure out the expected value for how many marbles we would each have to drop in (in total) to empty our catchers, and found the math surprisingly tricky.
His entry point and my entry point each had the same probabilities involved, although following different paths: each had a 1/2 chance of landing in my catcher, a 1/4 chance of landing in his catcher, and a 1/4 chance of landing in the third catcher.
(For ideal calculations we could assume the splitters always send one marble each way in turn, even though in reality they occasionally send two in a row the same direction, and sometimes marbles fall off the track.)
Empirically, starting with about 50 marbles (maybe a little less) in his catcher and none in mine, we each put in almost exactly the same number of marbles (109 for him vs. 110 for me), not counting the ones that fell off the marble run partway through and which we restarted without counting again. (Those skewed the numbers from the mathematically ideal question.)
How to calculate this?
I tried to figure it out on this basis:
Start with a vector of five numbers, representing:
- How many marbles currently in his catcher;
- Running total of how many marbles he's dropped in;
- How many marbles currently in my catcher;
- Running total of how many marbles I've dropped in;
- How many marbles currently in the third catcher.
In the empirical case above, this would be $[50, 0, 0, 0, 0]$ but let's call the starting number S: $[S, 0, 0, 0, 0]$
Then each iteration, we both drop in all the marbles currently in our catchers.
So $f([A, B, C, D, E]) = [(A+C)/4, B+A, (A+C)/2, D+C, E + (A+C)/4]$.
Then iterate until at the limit (to infinity iterations since we're doing it over the real numbers), $A$ and $C$ are both $0$ and $E$ equals the original starting $S$.
Question is, what's the value for $B$ and $D$?
Iterating a couple times by hand, I got:
$$S, 0, 0, 0, 0$$ $$S/4, S, S/2, 0, S/4$$ $$3S/16, 5S/4, 3S/8, S/2, 7S/16$$ $$9S/64, 23S/16, 9S/32, 7S/8, 37S/64$$
No convergent pattern is immediately apparent to me here, though it's obvious that it IS convergent at least when executed over the integers as in the case of real marbles. Pretty sure that it's convergent over the reals also. (I'd be startled if it diverged.)
I'm certain there's a better and simpler way to calculate this. What is it?
Nice problem. I believe you can simplify the analysis a bit by considering just a single marble. The initial distribution can be arbitrary; we’ll just consider the expected time it will take one marble to go from each “initial” bin to the third bin (I’ll call this the discard bin for clarity as any marble that enters it never leaves). We can do this because, ignoring the complicating effects such as marbles colliding with each other, the transitions for each marble can be considered independent (and identically distributed).
If the marble is already in the discard bin, then it will obviously take $0$ moves to get to the discard bin.
Let the expected number of moves to get from your bin to the discard bin and your son’s bin to the discard bin be $n_A$ and $n_B,$ respectively. Suppose a marble starts in your bin. There’s a $\frac{1}{2}$ chance that it will return to your bin, where it is expected that another $n_A$ plays (in addition to the initial play) are required to land in the discard bin. There is a $\frac{1}{4}$ chance that it will go to your son’s bin, where it is expected that another $n_B$ plays (in addition to the initial play) are required before landing in the discard bin. Finally, with $\frac{1}{4}$ probability, the marble will land directly in the discard bin, with a total of $1$ move. Using the definition of expectation,
$$n_A = \frac{1}{2} (n_A + 1) + \frac{1}{4} (n_B + 1) + \frac{1}{4} (1).$$
The interesting thing is, we also have that $n_A = n_B;$ i.e., the expected number of moves from either of the bins in play to the discard bin is equal. The reason why isn’t too hard to see - because the entry points have the same probabilities of the destination, the marble run process is blind to the history of the marble. Making this substitution, we get $n_A = n_B = 4.$ That is, for each marble starting in either play bin, on the average it will take $4$ moves to sink it in the discard bin.
This agrees with your empirical result that starting with $50$ marbles in play, it took a total of $109 + 110 = 220,$ which is appreciably close to the $200$ average.
A similar approach can be used to find the expected number of times each player will pick up and play a marble - this is equal to the expected number of marbles that enter the bin in total. Although again, it is not too difficult to see that if we start all the marbles in bin B, each player should expect to play $2$ times the total number of initial marbles (i.e. they split the total number of plays in half).