3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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$ $\endgroup$ Feb 22 '19 at 12:00
  • $\begingroup$ I think the $n$ vs $k$ error was introduced by me in my “helpful” editing. Sorry... $\endgroup$ Feb 23 '19 at 1:48
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Also thanks for your excellent edit of my question above, it made it much more readable! Your solution is really nice $\endgroup$ Feb 22 '19 at 7:33
2
$\begingroup$

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);
$\endgroup$
6
  • $\begingroup$ 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}$. $\endgroup$ Feb 26 '19 at 15:31
  • $\begingroup$ 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. $\endgroup$ Feb 26 '19 at 15:40
  • $\begingroup$ 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!$ $\endgroup$ Feb 26 '19 at 16:03
  • 1
    $\begingroup$ 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}$. $\endgroup$ Feb 26 '19 at 16:54
  • $\begingroup$ 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. $\endgroup$ Feb 26 '19 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.