Die and matchsticks game from 'The Goal'

Arrangements, combinations and permutations, probability, ...
Post Reply
MuthuVeerappanR
Posts: 324
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Die and matchsticks game from 'The Goal'

Post by MuthuVeerappanR » Tue Jun 12, 2018 11:00 am

Hi All, This post is about an analysis of a game described in Goldratt's best seller 'The Goal'. The game is as follows:

Consider $b$ bins of infinite capacity in a row with an imaginary Source of infinite matchsticks. Matchsticks are transferred to the bins in the following manner:
For every bin, matchsticks are transferred from the previous bin according to the number determined by the roll of a fair 6-sided die (the Source bin becomes the 'previous bin' for the first bin). After we are done for the $b$ bins, the die is rolled one more time and matchsticks from the last bin is taken and thrown away. This marks the end of first round.

However, sticks can be taken from the previous bin only if it is available there. For example, for the 4th bin if we have 5 from the roll, whereas the 3rd bin has only 1 matchstick, then we can transfer only one to the fourth bin.

Let $Y_n$ be the random variable denoting the total number of matchsticks in all the bins combined after the $n$th round.

I became curious about this game because nowhere can I find a proper mathematical analysis of the game. Almost every material (including the book itself) uses simulation to emphasis the point that $Y_n$ varies wildly. For example, this. Now the question is, is that because the game is hard to deal mathematically or impossible to handle except for brute force simulation?

I did some ground work on my part. Let $B_{n,k}$ be the number of matchsticks in the $k$th bin after the $n$th round and $\displaystyle C_{n,k}=\sum_{j=1}^k B_{n,j}$

We have the recurrence, $C_{n,k}-U_{0,n}=\text{max}(C_{n,k-1}-U_{0,n},C_{n-1,k}-U_{n,k})$ with $C_{0,k}=C_{n,0}=0$ and all the $U$s are discrete uniform random variables.

Now is there an easy way to calculate $\mathbb{E}(Y_n)=\mathbb{E}(C_{n,b})$?

Unfortunately, I'm not sure how to handle this into a work-able code except for a lot of conditioning which eventually becomes brute-force. Any suggestions/ideas anyone?
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Post Reply