# 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?

• Good point, thanks for spotting this @PierrePC . I have just edited the question accordingly and hope I didn't miss any $n$ that should have been replaced by $k$ – Dominic van der Zypen Feb 22 '19 at 12:00
• I think the $n$ vs $k$ error was introduced by me in my “helpful” editing. Sorry... – Anthony Quas Feb 23 '19 at 1:48

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$$.

• Also thanks for your excellent edit of my question above, it made it much more readable! Your solution is really nice – Dominic van der Zypen Feb 22 '19 at 7:33

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);

• At first sight, your formula looks good, so I don't see yet what is wrong with it, but I am pretty sure that $p_4 = \frac{1}{4}$. And I suspect that $p_5 = \frac{1}{6}$, and $p_6 = \frac{1}{10}$. – Mark Dettinger Feb 26 '19 at 15:31
• FYI, in my simulation of $10^9$ games, 333'319'160, 250'015'733, 166'656'001, and 100'010'566 games terminated after 3, 4, 5, and 6 rolls, respectively. – Mark Dettinger Feb 26 '19 at 15:40
• I computed the exact solutions for $p_3$ to $p_{10}$ now. Here they come: $p_3 = 2 / 3! = 1/3$, $p_4 = 6 / 4! = 1/4$, $p_5 = 20 / 5! = 1/6$, $p_6 = 72 / 6! = 1/10$, $p_7 = 302 / 7!$, $p_8 = 1446 / 8!$, $p_9 = 7834 / 9!$, $p_10 = 47146 / 10!$ – Mark Dettinger Feb 26 '19 at 16:03
• I wrote another program that generates all permutations of ${1,...,k}$, then checks for each permutation at which position the game would have terminated, and outputs the distribution of these positions. For example, for $k=4$ the output is [0, 0, 0, 8, 6], meaning that for 8 permutations the game would stop after 3 rolls and for 6 permutations it would stop after 4 rolls. The output for $k=10$ is [0, 0, 0, 1209600, 907200, 604800, 362880, 217440, 130140, 78340, 47146]. As all permutations are equally likely, this yields the exact solutions up to $p_{10}$. – Mark Dettinger Feb 26 '19 at 16:54
• The run-time complexity of this method is O(k!) though, so I cannot go much higher than $k=12$, which takes about 20 seconds to compute. – Mark Dettinger Feb 26 '19 at 16:59