3
$\begingroup$

I have recently seen on social media a game that is quite amusing and addicting to watch. Here is a link to a guy playing it. Here is a description of the specific rendition I just shared.

Given a RNG that gives $20$ random numbers between $1$ and $1000$, sequentially order the numbers without knowing what is going to come next with the intention of having all $20$ numbers sorted at the end (i.e. if you draw $500$ rank it at ~$10$, then rank the next number, then the next, etc.) At the end of the game if all $20$ numbers are sorted properly in increasing order you win, if they are not you lose.

Let's assume for the purpose of this analysis that the set of numbers we are drawing from is sufficiently large that we do not have to worry about repeating numbers. We can just assume we are drawing random real numbers between $0$ and $1$ if you will. And also since we have no idea of the numbers that are going to come the only strategy that we can employ to win the game is basic statistical ranking, assuming a uniformly distributed RNG.

My question is: What are the odds of winning this game for $n$ randomly drawn numbers that are to be ordered?

The case for when $n=2$ is straight forward. If the numbers drawn are $a$ and $b$ respectively, if $a$ is greater than $0.5$ it will be ranked at $2$ and so we will win if $b$ is smaller than $a$, the opposite is true in the other case. In the first case we will win an average of $\frac{3}{4}$ of the time, and so too in the second case. So we can expect to win about $\frac{3}{4}$ of the time for $n=2$.

I have been working on some code to simulate the game and the ranking process to get some Monte Carlo results. But I would be interested in a closed form solution.

$\endgroup$
4
  • $\begingroup$ It would be a bit clearer if you replace "sequentially order" by "rank". This was asked here for the discrete case. No answer was given, and the continuous case wasn't considered. The question contains a rather unenlightening recurrence and an interesting graph for the discrete case. $\endgroup$
    – joriki
    Commented Apr 1, 2023 at 1:16
  • $\begingroup$ Are the numbers drawn between $1$ and $1000$ without replacement? The question I linked to assumes they are, and your requirement of ending with the numbers sorted in increasing order also seems to imply that they are. $\endgroup$
    – joriki
    Commented Apr 1, 2023 at 2:01
  • $\begingroup$ (See also the game "Rack-O".) $\endgroup$
    – aschepler
    Commented Apr 1, 2023 at 3:07
  • $\begingroup$ Should note that I provided a closed form formula here in this question: math.stackexchange.com/questions/4618370/… $\endgroup$
    – wjmccann
    Commented Jun 8, 2023 at 22:41

1 Answer 1

4
$\begingroup$

Let’s solve some small cases recursively. Denote the probability to win the game with $n$ numbers by $p_n$.

You’ve already found $p_2=\frac34$, and of course $p_1=1$. For $n=3$, say you draw $x$ first. If you rank it $3$, you’ll be right with probability $x^2$, and in that case your winning probability will be $p_2=\frac34$. If you rank it $2$, you’ll be right with probability $2x(1-x)$, and in that case your winning probability will be $p_1^2=1$. Thus, the boundary at which these two guesses have the same winning probability is $\frac34x^2=2x(1-x)$, with solution $x=\frac8{11}$. By symmetry, the boundary for the guesses $1$ and $2$ is at $\frac3{11}$. So you should guess $1$ if $x\le\frac3{11}$, $2$ if $\frac3{11}\lt x\le\frac8{11}$, and $3$ otherwise. Your overal winning probability is

$$ p_3=2\int_\frac8{11}^1\frac34x^2\mathrm dx+\int_\frac3{11}^\frac8{11}2x(1-x)\mathrm dx=\frac{377}{726}\approx52\%\;. $$

For $n=4$, with a first draw of $x$, if you rank it $4$ you’ll be right with probability $x^3$ and in that case your winning probability will be $p_3=\frac{377}{726}$, whereas if you rank it $3$, you’ll be right with probability $3x^2(1-x)$ and in that case your winning probability will be $p_1p_2=\frac34$. Thus, the boundary at which these guesses have the same winning probability is $\frac{377}{726}x^3=\frac34\cdot3x^2(1-x)$, with solution $x=\frac{3267}{4021}$. By symmetry, the other two boundaries are at $\frac12$ and $1-\frac{3267}{4021}=\frac{754}{4021}$. Your overall winning probability is

$$ p_4=2\int_\frac{3267}{4021}^1\frac{377}{726}x^3\mathrm dx+2\int_\frac12^\frac{3267}{4021}\frac34\cdot3x^2(1-x)\mathrm dx=\frac{1037891564126671}{3020778029791104}\approx34\%\;. $$

The boundaries are the solutions of linear equations with rational coefficients, so the boundaries and probabilities are rational numbers for all $n$. When I get around to it I’ll write some code to work them out for $n=20$. The same can of course also be done for the discrete case, as shown at Probability of winning a game guessing $k$ random numbers in sequence with optimal strategy.

$\endgroup$
1
  • $\begingroup$ Im having a little trouble understanding your leap in logic from "[T]he boundary at which these two guesses have the same winning probability..." and "So you should guess..." . You're telling me in the case of $n=3$ If I draw $0.28$ I should rank it at $2$? $\endgroup$ Commented Apr 4, 2023 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .