Expected value of length of interval game 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?
 A: 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$.
A: Some additional results
For $k=2$, the game ends after 3 throws in 75% of the cases and is guaranteed to end after 4 throws, so $E_2 = 3.25$.
$E_3$ is about 3.45. For $k=3$, the game is guaranteed to end after at most 6 rolls.
$E_4$ is about 3.61. $k=4$ is the smallest $k$, for which the length of the game has no upper bound. For example, the cycle 2, 1, 3, 4,... could go on forever.
I would be interested in the precise value of $E$, when $k$ goes to $\infty$. A simulation of $10^9$ games showed me that $E_{\infty}$ is about 4.7096. A roll in this game means drawing a uniformly distributed random number from the interval $[0,1]$. I include the program below, if anyone is interested.
Simulation for $k = \infty$ in Java
Random r = new Random();
double sum = 0.0;
long n = 1000000000;
for (int i=0; i<n; i++) {
    double a = r.nextDouble();
    double b = r.nextDouble();
    long count = 2;
    while (true) {
        double c = r.nextDouble();
        count++;
        if ((a<=c && c<=b) || (a>=c && c>=b)) {
            break;
        }
        a = b;
        b = c;
    }
    sum += count;
}
double avg = sum / n;
System.out.println("average = "+avg);

