Waiting for the gravy at a dinner table

Question

You are sitting at a round dinner table with $N$ other people (i.e. $N+1$ people all together). One of the other guests is the first to pick up the gravy boat and pour some on their potatoes. It then gets passed at random to either of the adjacent people ($50\%$ each way). This person, after pouring themselves some gravy, also passes it to a neighbour, and as they are so engrossed in conversation it is again equally likely to be either neighbour. This continues, with the gravy boat being passed from person to person in a random direction each time.

You don't want to be the last person to get any gravy. For you to have the smallest probability of being last, which other guest should be the first to use the gravy? And what is that probability?

I don't know the original source of this puzzle, but it has been doing the rounds for a few years and in my opinion it is destined to become a classic. See for example this Math SE question.

Answer 1

Fascinating.

The probability of being last is $1/N$ regardless of which guest starts with the gravy.

I had to do the calculation with Markov chains to get the answer. But after getting it I thought about it.

It is a certainty that one of your neighbors will get it before you. You can choose that neighbor by sitting next to the first person, or you can wait patiently until one of your neighbors gets it.

From there, to be the last person the gravy needs to go all the way around to your other neighbor without first getting to you. There is some probability that it does this.
But, actually, everyone has the same situation. One of their neighbors will get it and then there is some probability that it goes all the way around from there to your other neighbor without coming back to you through your first neighbor.

Since everyone is in the same situation, the probability of being the last is the same for everyone and so everyone has a $1/n$ chance to be the last person getting the gravy.

Out of interest, here's how I did the calculation beforehand. First I envisaged a state diagram (Markov) something like this:

Here we start on the middle ring ($1-n$). If we get to the $1$ we move onto the inner ring, which I call $1'-n'$. As you can see, $1'=1$.

Similarly, if we get to $n$, then we move onto the outer ring, labeled $1''-n''$. Again $n''=n$.

This ends well if we get to 0 (gree), and it ends badly if we get to $n'$ or $1''$ (red). In fact, we may as well have $n'=1''$.

So now this leads to the following transition matrix when $n=5$. Here the columns and rows are $(1=1'),2,3,4,(5=5''),2',3',4',2'',3'',4'',0,(1''=n')$.

\begin{equation} M=\left( \begin{array}{ccccc|ccc|ccc|cc} 0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} &0 \\ \frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &\frac{1}{2} &0 \\ \frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &0 &\frac{1}{2} \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &0 &\frac{1}{2} \\ 0 &0 &0 &0 &0 &0 &0 &0 &\frac{1}{2} &0 &\frac{1}{2} &0 &0 \\ 0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 &0 &\frac{1}{2} &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{array} \right) \end{equation}

where the vertical lines are a guide to the eye separating the $1-5$ from the $2'-4'$ from the $2''-4''$ from the two endings.

Then we can either run $M=M^2$ hundred times to calculate $M^\inf\approx M^{2^{100}}$ or do an inversion following the formula here. Either way, we get an absorbing probability of:

\begin{equation} B=\left( \begin{array}{cc} \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{4}{5} &\frac{1}{5} \\ \frac{3}{5} &\frac{2}{5} \\ \frac{2}{5} &\frac{3}{5} \\ \frac{1}{5} &\frac{4}{5} \\ \frac{1}{5} &\frac{4}{5} \\ \frac{2}{5} &\frac{3}{5} \\ \frac{3}{5} &\frac{2}{5} \end{array} \right) \end{equation}

The only relevant numbers here are the first 5 rows (corresponding to states $1-5$). The remaining rows are if you start in states $2'-4'$ or $2''-4''$. The left column gives the probability of not being last to get the gravy and the right column gives the probability of being the last to get the gravy.

I ran this for a few different $n$ values and realized that it was a constant. I should have realized there would be something up with the reference to this becoming a classic puzzle.

Very neat puzzle.

Answer 2

Suppose that your neighbour starts, and call the probability of you being last "x".

Then, suppose that some other person starts.

There is exactly one way for you to be the last one:
* first, the gravy comes to your neighbour
* next, it goes all around the table to your other neighbour.

As we very well know, the first happens

with probability 1

and the second happens

with probability x.

Therefore,

it doesn't matter who starts, and the probability is always the same.

By symmetry

the same applies for all the guests who didn't pick up the gravy

so the probability of it being exactly you who is last is

$\frac{1}{\text N}$

Answer 3

I agree this is a lovely surprising puzzle, deserving of an elegant solution.

Let $p_k$ be the probability that the $k^{th}$ guest, counted clockwise from the gravy's start point, is the last to have the gravy. There is a 50/50 chance of passing either left or right, after which we are left with a shifted version of the same problem. With a little thought, this implies $$p_k=\frac12p_{k-1}+\frac12p_{k+1}$$holds for all $2\le k\le n-1$. We therefore have a list of numbers $p_1,p_2,\dots,p_n$ where each number is halfway between its neighbors. This implies that the list grows linearly; that is, $p_k=ak+b$ is some linear function of $k$. But by the symmetry of the problem, you must have $p_1=p_n$, so the slope of this line must be zero, so in fact all $p_k$ are equal!