I have a die that produces uniformly distributed values in $\{1,\ldots, k\}$ for some integer $k\geq 2$. Now I play the following game.


I start rolling the die and produce one integer in $\{1,\ldots,k\}$ after another, $X\_1,X\_2,\ldots$, and I stop when my most recent integer $x$ lies between the previous integer $b$, and the integer $a$ obtained before that. (More formally, the stopping time is the least $n\ge 3$ such that $X\_n\in [\,\min\{X\_{n-2},X\_{n-1}\}, \max\{X\_{n-2},X\_{n-1}\}\,]$.)


An example: $k=6$, and my dice rolling sequence is $2, 4, 5, 1, 4$ $\implies$ there I stop, since $4$ is in the interval $[1,5]$ of the last two dice rolls $5$ and $1$.


Let $E\_k$ be the expected value of the length of one game with a dice of $k$ sides. It may be difficult to give an explicit value for $E\_k$, but:


**Question.** Is $\{E\_k:k\in\mathbb{N}, k\geq 2\}$ bounded?



Expected value of length of interval game
Yes: Given that no stop has been achieved up to time $n$, the probability that a stop is achieved at time $n+3$ is at least $\frac 13$. To see this, notice that given $X\_1,\ldots,X\_n$, and the values of the (unordered) multiset $\{\{X\_{n+1},X\_{n+2},X\_{n+3}\}\}$, each ordering of the three terms is equally likely, so that there is at least a $\frac 13$ probability that $X\_{n+3}$ lies between $X\_{n+1}$ and $X\_{n+2}$ (slightly above this because there is a positive probability of repetition). It follows that the expected stopping time is at most $\sum\_{n=1}^\infty (3n)(\frac 23)^{n-1}\frac 13<\infty$.


