5
$\begingroup$

I just finished reading The Goal by Eliyahu M. Goldratt. It's a good book, and from my understanding, pretty well known. Goldratt is a a physicist who turned his scientific scrutiny to production line management, and his book is about how mathematical thinking can help your business.

In it, he describes a game used to illustrate the flow of a production line. It goes like this:

There are five people sitting in a line with a few boxes of matches at one end. The goal is to move as many matches as possible to the end of the line. In one turn, the first first person in the line rolls a six sided die and moves that number of matches down the line. The next person then rolls the die and moves that number of matches down the line, and so on. That's one turn. You repeat that process a given number of times and then count the number of matches moved all the way through ("throughput") and count the matches that are still sitting in between the people waiting to be moved ("inventory"). You want to maximize throughput and minimize inventory build up.

To be explicit, if on the first turn the first player rolls a 4 and the second player rolls a 6, they can only move 4 because there's only 4 available to move. But if there are more matches waiting in the inventory (perhaps because the person before them is getting high rolls while they've been getting low rolls), then they take from that pile. So if there are 2 already in inventory, player 1 rolls a 4 and player 2 rolls a 6, there are 6 available matches, so they can move all 6 down the line.

Hopefully that's clear. Here is the question, or rather questions:

  • What is the expected value for throughput after $n$ turns?
  • What about the expected inventory waiting for each person after $n$ turns?
  • How does the number of people affect these values?
  • What if the dice are more abstract, like a 17 sided die with four 6s, three 12s, etc. Just an abstract probability distribution?
  • What about an expected value for the amount of rolls that were "wasted"? So if there was 2 in inventory and you rolled a 5, that would be 3 units "wasted"
  • Can we find more details about the distribution, rather than just the expected value?
$\endgroup$
1
$\begingroup$

I do not see an easy way of simplifying this for later rounds, so what follows is based on calculations

In the first round

  • the expected number the $n$th person passes are $\frac{1^n+2^n+3^n+4^n+5^n+6^n}{6^n}$, which for the first five are about $3.5$, $2.53$, $2.04$, $1.76$ and $1.57$ respectively, tending towards $1$ as $n$ increases. The difference between the first and last of about $1.93$ is the expected wastage

  • the expected amounts left between the $n-1$th and $n$th people is the difference between these, namely $\frac{1\times 5^n + 2\times 4^n + 3\times 3^n + 4\times 2^n + 5\times 1^n}{6^n}$ which for the initial gaps are about $0.97$, $0.49$, $0.29$, $0.19$, tending towards $0$ as $n$ increases. As you might expect, these add up to about $1.93$ as the total wastage so far

  • the probabilities of $n$th person passing $k$ are $\frac{(7-k)^n-(6-k)^n}{6^n}$ for $1 \le k \le 6$. So for the fifth person these are $1$ with probability about $0.60$, $2$ with probability about $0.27$, $3$ with probability about $0.10$, $4$ with probability about $0.03$, $5$ with probability about $0.004$ and $6$ with probability about $0.0001$, and increasing $n$ concentrates the probability on $1$ being passed

In the $r$th round (for large $r$)

  • the expected number the $n$th person passes gets closer to the dice mean of $3.5$. I suspect that the expected difference (i.e. the expected amount wasted by that person and their predecessors) might be roughly proportional to $\frac{1}{\sqrt{r}}$

  • the expected amounts left between people is in effect the expected cumulative wastage of all the preceding rounds, and so I suspect it might be roughly proportional to ${\sqrt{r}}$, i.e. increasing without limit

  • the distribution of the amounts passed by the $n$ person continues to have lower values more common than higher values, but tends to be closer to an equal distribution of $\frac16$ for each value

For example, in the $100$th round, my unchecked calculations suggest

  • the expected numbers the five people pass are about $3.5$, $3.40$, $3.28$, and $3.23$ respectively, giving a combined expected wastage of about $0.27$ on that round

  • the expected amounts left between people after that round are about $17.94$, $12.28$, $9.63$ and $8.04$, for a combined expected cumulative wastage of about $47.89$

  • the fifth person passes $1$ with probability about $0.20$, $2$ with probability about $0.19$, $3$ with probability about $0.18$, $4$ with probability about $0.17$, $5$ with probability about $0.14$ and $6$ with probability about $0.12$

You also asked about using different dice. Clearly this would change the numbers, but I doubt it changes the general patterns

$\endgroup$
3
  • $\begingroup$ Could you provide a little intuition for your first formula? The expected number the nth person passes being $\frac{1^n+2^n+3^n+4^n+5^n+6^n}{6^n}$ $\endgroup$ – Cordello Feb 20 '17 at 5:08
  • $\begingroup$ @Cordello: it can be derived from "the probabilities of $n$th person passing $k$ are $\frac{(7-k)^n-(6-k)^n}{6^n}$ for $1 \le k \le 6$" so simplifying $\displaystyle \sum_{k=1}^6 k \dfrac{(7-k)^n-(6-k)^n}{6^n}$ to $\dfrac{1^n+2^n+3^n+4^n+5^n+6^n}{6^n}$ $\endgroup$ – Henry Feb 20 '17 at 8:25
  • $\begingroup$ And those probabilities come from saying that the $n$th person passes exactly $k$ if all of the first $n$ pass at least $k$ but do not all pass at least $k+1$ $\endgroup$ – Henry Feb 20 '17 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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