A Game of Chance

Throughout human history, randomness has been a bane to everyday life. Imagine the vicissitude a farmer endures managing the randomness of meteorological processes. Were it not for the predictable and seemingly deterministic structure of large-scale systems and the resultant diurnal and seasonal patterns, a farmer's way of life would not be feasible. The same reasoning can be applied to many other professions vital to the advancement of human civilization.

The word random connotes unsettling notions of uncertainty and disorder. These ideas seem on the surface to be contrary to the methodical, systematic, and definite nature of mathematics. Paradoxically, it is through mathematics – via the study of probability theory – that randomness is best understood.

The inception of probability theory is often attributed to the mathematicians Pierre de Fermat and Blaise Pascal. But, Gerolamo Cardano seems to have been the first to rigorously analyze randomness from a mathematical perspective. Cardano made large contributions to algebra, being the first to publish solutions to cubic and quartic equations. He was also an accomplished gambler. In 1526, he wrote a book about games of chance, in which he discussed decision making when faced with randomness.

The pioneering work of Cardano and subsequent developments in probability theory marked the beginning of a new perspective on randomness. What was previously intractable became a science. And, with the advent of quantum mechanics, we have learned that randomness is not the result of a lack of understanding but a necessary and fundamental component of our universe.

In the past few decades, the story on randomness has taken an even more alarming turn. Randomized algorithms have demonstrated that randomness is not only something we can reason about but something we can leverage to solve problems. If you want to test if a number is prime, it helps to flip coins. In this vein, we discuss a game in which randomness is not only relevant but vital to any effective strategy.

Consider the following variant of the popular game show Deal or No Deal:

You are presented with n briefcases. Each briefcase contains an unknown quantity of money. The rules are as follows. You are allowed to select one briefcase at a time. Upon selecting a briefcase, its contents are revealed to you. You can then choose whether to keep the contents of this briefcase or reject it in favor of a future briefcase. Once you reject a briefcase, you cannot claim its contents anymore. Your goal is to choose the briefcase with the biggest payout. 

If we employ any deterministic strategy, an adversary (aware of our strategy) could arrange the briefcases in such a way that we would always choose the briefcase with the lowest payout. On the other hand, by employing randomness, a trivial strategy yields a success rate of at least $1/4$. That is, with probability $1/4$, we will choose the briefcase with the biggest payout.

Consider the following approach. First, permute the briefcases into a uniformly random order $b_1, b_2, \dots, b_n$. Then, select the first $n/2$ briefcases, rejecting them outright. Proceed through the remaining briefcases until we uncover one that yields a larger payout than any previously seen. If we uncover such a briefcase, keep it (otherwise, we can just "try out luck" with $b_n$).

Observe that this strategy will always win if the briefcase with the second largest payout was in the first half and the briefcase with the best payout was in the second half. Since the briefcases were arranged into a uniformly random permutation, this winning scenario happens at least $1/4$ of the time.

As we uncover a briefcase, say $b_i$, we can compute the probability that this briefcase is the best. This probability is

• $i/n$ if $b_i > b_j$, for all $j < i$, and
• $0$ otherwise.

Thus, the previously mentioned strategy can be restated as follows: Stop at the first briefcase with probability at least $1/2$ of being the best.

This raises the following questions:

1. What is the actual success rate of this strategy?
2.  Does there exist a similar strategy with a better success rate if we replace $1/2$ with some other threshold probability, say $p$? 

The answer to (2) is a definitive yes, and the optimal value of $p$ may seem surprising. It turns out that for large enough $n$, your best bet is to set $p = 1/e$, where $e = 2.71828...$  is Euler's number. The analysis is as follows.

As stated above, if $b_i$ is larger than all previously seen briefcases, it is the largest with probability $i/n$. Indeed, the largest briefcase had an $i/n$ chance of being in this range. Thus, for a given threshold probability $p$, our algorithm will stop at the first such $b_i$ encountered after position $k=\lfloor pn \rfloor$. Thus, the probability of success can be reduced to the probability that the first such $b_i$ encountered after position $k$ is also the largest briefcase. For $i  \geq k$, define

• $A_i$ to be the event that $b_i$ is the largest briefcase, and
• $B_i$ to be the event that the largest $b_j$ in $b_1,b_2,\dots,b_i$ satisfies $j \leq k$.

Then the desired probability can be calculated as
\[ \sum_{i=k+1}^n P(A_i) P(B_{i-1}) = \sum_{i=k+1}^n \frac{1}{n}\frac{k}{i-1} \] which can be simplified to
\[ \frac{k}{n}\sum_{i=k}^{n-1} \frac{1}{i} = \frac{k}{n}(H_{n-1} - H_{k-1}) \] where $H_j$ denotes the sum of the harmonic series from $1$ to $j$. Thus, for fixed threshold probability $p$ and $n \to \infty$, the success rate converges to
\[ \frac{k}{n}\ln{\left(\frac{n}{k}\right)} \sim -p\ln{p} \]
by using the approximation $H_j \sim \ln{j} + \gamma$, where $\gamma$ is the Euler–Mascheroni constant. To answer question (1) from above, we substitute $p = 1/2$ into this equation, giving a success rate of $1/2\ln{2} = 0.346573...$. By applying elementary calculus, the success rate can be shown to be largest when $p=1/e$; that is, the optimal threshold probability is $1/e$, which gives a success rate of $1/e = 0.367879...$.

We conclude with the following question: Can you do better?