A game of plates and olives

Question

This question has its origin in Morse theory (see this paper) but it can be given an entirely elementary and amusing formulation.

The game of plates and olives starts with an empty table and ends with an empty table and it consists of a succession of the following elementary moves.

($P_+)$ Add an empty plate on the table.

($O_+$) Add an olive on an existing plate.

($P_-$) Move all the olives from a plate $p_0$ to a plate $p_1$ and then smash the plate $p_0$. (A degenerate case of this move is when $p_0$ is an empty plate and you simply smash it.)

($O_-$) Eat one olive from one of the plates.

Note that the $P_\pm$-move change the number of plates by $\pm 1$, while the $O_\pm$-move changes the number of olives by $\pm 1$.

As I mentioned early on, a game starts with an empty table and ends when we smash the last remaining plate on the table, which has to be free of olives. The olives are indistinguishable, and so are the plates. The length of a game is the number of elementary moves it consists of, from the beginning to the end.

During a complete game, the number of $P_+$-moves must equal the number of $P_-$-moves and the number of $O_+$-moves must equal the number of $O_-$ moves. Thus, the length of a game is a positive even integer. $\newcommand{\bZ}{\mathbb{Z}}$ For any $n\in\bZ_{\geq 0}$ we denote by $G_n$ the number of games of length $2n+2$. In the paper mentioned above I showed

$$ G_n \geq (2n+1) !! $$

It is my strong belief that this inequality is asymptotically sharp on a logarithmic scale, i.e.,

$$\lim_{n\to\infty} \frac{\log G_n}{\log (2n+1)!!}= 1, $$

or, in view of Stirling's formula

$$\log G_n \sim n\log n\;\;\mbox{as}\; n\to\infty.$$

This has resisted all my on and off attempts to prove it.

Question 1. Is my above belief justified?

One can also randomize this game. This means that, at every stage during the game, we choose the moves available to us uniformly at random.

For example , if during the game we reach a situation when there are $a$ plates and $b$ olives on the table, then the options available to us are

One possible $P_+$ move,

$a$ possible $O_+$ moves (there are $a$ plates where we can place a new olive),

$b$ possible $O_-$ moves and

$\binom{a}{2}$ possible $P_-$ moves.

Question 2. Is the expected duration of such a random game finite?

Thank you.

Comment 1. Let me expand, based on @michael answer. During a game the pair $(a,b)$ undergoes a random walk on the lattice

$$ (a,b)\in \bZ_{\geq 0}\times \bZ_{\geq 0}\setminus \big(\{0\}\times \bZ_{>0}\big),\;\;$$ with transition probabilities described above. (The horizontal axis is th plate axis, and the vertical axis is the olive axis.) This is easily seen to be irreducible, and $(0,0)$ is a reflecting state. A more refined version of Question 2 would be the following.

Question 2.1 Describe the dynamics of this Markov chain.

Answer 1

The answer to Question 1 is that yes, the belief is justified. By Stirling's approximation, $(2n+1)!!=n^n(2/e)^{n(1+o(1))}$ or $\log (2n+1)!! = n \log n +n(2/e)(1+o(1))$, so for an affirmative answer to Question 1 it is enough to get an upper bound on $G_n$ of the form $G_n \leq n^nC^n$ for some constant $C$.

Here's a sketch of such an upper bound. A game of length $2n$ involves $n$ "$+$'' moves (either $P_+$ or $O_+$) and $n$ "$-$'' moves, so the profile of a game, at the high level of where $+$ moves and $-$ moves are made, can be specified at a cost of $\binom{2n}{n}$ (but a bound of $4^n$ is fine here, too).

Now consider a game in which there are exactly $t$ $O_+$ moves. There are at most $\binom{n}{t}$ options for the location of these moves, and at most $\binom{n}{t}$ options for the location of the corresponding $O_-$ moves.

We now have to consider how many options there are at each $P_+$, $P_-$, $O_+$ and $O_-$ move. That's easy for the $P_+$ moves --- these involve no choice.

For the other moves: given a configuration ${\mathcal C}$ of plates and olives, let $o({\mathcal C})$ be the total number of olives, and let $p({\mathcal C})$ be the size of $\{k:\mbox{in ${\mathcal C}$ there is a plate with $k$ olives}\}$. Then we have (basically) $p({\mathcal C}) \leq \sqrt{2o({\mathcal C})}$, because to have $p({\mathcal C})$ any larger we would need more than $0+1+\cdots + \sqrt{2o({\mathcal C})} \approx o({\mathcal C})$ olives.

We can now bound the number of options at $P_-$ moves by $(\sqrt{2t})^2$ (we have to choose a plate to remove, cost at most $\sqrt{2t}$, the largest possible value of $o({\mathcal C})$ when there are $t$ $O_+$ moves, and then choose a plate on which to deposit the olives from the removed plate, again cost at most $\sqrt{2t}$). So the maximum contribution from $P_-$ moves is $(2t)^{n-t}$. Here and in the next paragraph we are crucially using that all plates with the same numbers of olives on them are indistinguishable.

At the $\ell$th $O_+$ move, there are at most $\sqrt{2\ell}$ options (because there are at most $\ell$ olives on the table at that time), and at the $(t-\ell)$th $O_-$ move there are again at most $\sqrt{2\ell}$ options (with only $\ell$ $O_-$ moves remaining, there are again at most $\ell$ olives on the table at that time). The maximum contribution from $O_+$ and $O_-$ moves is then at most $$ \left(\prod_{\ell \leq t} \sqrt{2\ell}\right)^2 \approx 2^t t! \approx 2^t\left(\frac{t}{e}\right)^t. $$

Putting it all together we get an upper bound on $G_n$ of the form $$ \sum_{t \leq n} 4^n\binom{n}{t}^2 2^t \left(\frac{t}{e}\right)^t (2t)^{n-t} = 8^n\sum_{t \leq n} \binom{n}{t}^2 \frac{t^n}{e^t}. $$

Parameterizing $t=\alpha n$ the summand above is (basically) $$ n^n \exp_2\left\{n(2H(\alpha) +\log_2 \alpha -\alpha\log_2 e)\right\} $$ where $H(x)$ is the binary entropy function. So we have an upper bound of $$ G_n \leq n^n C^n $$ where $$ C=8 \times \exp_2\left\{\max_{\alpha \in (0,1)} (2H(\alpha) +\log_2 \alpha -\alpha\log_2 e)\right\}. $$

With Teena Carroll at Emory & Henry we have been working to optimize this argument (there's lots of room for improvement), and we can currently get $C$ down to about 1.87, off by a multiplicative factor of about 2.5 from the $(2/e)$ appearing in the lower bound.

Answer 2

As to the expected duration, if you look at the total number of plates plus olives there are a+1 moves which increase it and ${ a \choose 2 } + b$ which decrease it, therefore it increases with probability at least $\frac {a + 1} {{a \choose 2 } + b + a + 1}$. As long as a + b is at least 5 this number is always small, much less than .5 (full disclosure: haven't proven that, just plotted a few cases). This guarantees that you will return to N < 5 at least like a random walk with negative drift, which occurs in finite expected time.It is standard to show that since you have a positive probability of ending within 5 steps from there you will soon do it, also within finite expected time.

Answer 3

I believe Michael’s answer isn’t quite right. If we just consider a 1-dimensional random walk that tracks the olives(as long as we have at least one), this is a random walk with a slight positive bias(we can add an olive to any plate that we can remove an olive from, and we can add an olive to empty plates as well.), so this random walk has infinite expected time before it returns to zero olives. If we never get down to zero olives, we never get an empty table.

The issue with Michael’s answer is that it doesn’t consider what is happening when there is only a single plate.