# Modelling randomized cup stacking, animal behaviour

This question has no scientific relevance for me whatsoever, but is a real life question which left me puzzled for a while. Even though I am not going anywere with this, maybe there is still somebody out there who shares my fascination with it.

So a friend send me this viral video of an otter stacking cups. Obviously my friend was merely interested in the cuteness, but I immediatedly asked myself whether the otter actually understands the concept of bigger and smaller or whether it just randomly stacks cups and breaks them up again if the don't fit.

Edit/Warning In the first version I compared the game with the towers of Hanoi. Although there are some similarities it's in fact different. Sorry for the confusion. In this game we have $n$ cups which are well-ordered in size and we try to stack them together while holding the biggest one fixed in our hand.

Unfortunately I can't conduct any experiments myself - I just don't own enough otters - but say we wanted to test the hypothesis that the otter uses a random resp. an "intelligent" strategy. We would give the otter a number of $n$ cups which are ordered in size and measure the time it needed to stack them. Then we would compare the performance time with a model which uses a random strategy.

The question is now, how would one model such a random strategy?

One option would be that after every step we choose a random cup and try to stack it on top. If it fits we go on, if it doesn't fit we break everything up and start all over again. Obviously the probability of ending up with a complete stack is $\frac{1}{n!}$, but even then the expected performance time isn't easy to compute since the time until we realise an error in our stack varies.

A more sophisticated model would assume that we still pick a random cup and try to stack it. Again if it fits we move on, if it doesn't fit we give our stack a good shake, thereby breaking it up into two clusters. Then we treat those cluster similar to single cups. This is, we are working with strings $x_1<x_2<\cdots<x_k$ rather than elements $x_i$. To compute anything here seems to be incredibly complicated.

A variation of the above model would be that we assume that correct connections are stronger (due to higher friction) and are less likely to break up than wrong connections (correct means here, that the cups are direct succesors, wrong means other cups belong in between). So whenever we give the stack a shake, with a probability of $p$ a correct link breaks up and with a probability of $q$ a wrong link breaks up. Obviously $p<q$ and $p+q\leq 1$.

Can you think of other/better models and is there any hope to actually be able to compute a distribution of performance time based on these models?

Right now I am not even sure whether the last two models are actually faster than the first one.

-
What about the simple strategy, where you just move pick one of the currently legal moves uniformly at random, and perform it. Then continue this until the towers are stacked correctly (which will take a long time). – utdiscant Aug 20 '12 at 13:08
@utdiscant Do you by legal mean possible or correct? In the first case you generally won't end up with a finished stack and for the latter case we need an a priori method to to tell which moves are correct. – Simon Markett Aug 20 '12 at 13:27
I was thinking about possible moves. Do you have a proof that the very simple strategy does not give you a solution in the limit? – utdiscant Aug 20 '12 at 13:49
@utdiscant Arg, now I get the confusion. It was pretty stupid of me to compare this game to the towers of Hanoi even though there are some similarities. Sorry for that. – Simon Markett Aug 20 '12 at 14:03
I should have watched the video, but I am on terribly slow 3g at the moment. I remember doing a reduction from cup-stacking to hamiltonian path once. In that setting, you were given a bunch of cups, and when stacking cup $i$ with cup $j$ their total height is the height of the smallest cup, plus some offset $h_{ij}$ since they don't stack perfectly. Now finding the lowest stack of all cups correspond to finding a hamiltonian path in the graph where each cup is a vertex, and the distance between vertices $i,j$ is $h_{ij}$. – utdiscant Aug 20 '12 at 14:24

In a given building cycle, a $(k+1)$-th cup is placed if and only if the first $k$ cups were all in the right order, with probability $\frac1{k!}$. Thus by linearity of expectation the expected time per cycle is
$$\sum_{k=0}^{n-1}\frac1{k!}\;.$$
As you noted, the probability for a successful cycle is $\frac1{n!}$, so we expect to take $n!$ cycles, for a total time of
P.S.: I just noticed I didn't include the biggest cup held fixed in the hand, so this is the result for doing it on a table; if the biggest cup is fixed you need to subtract $1$ from $n$. – joriki May 16 at 10:07