Expanding a randomized Two Envelope Problem

Question

There is a previous problem called the Envelope Paradox with a detailed explanation and solution given here. In short, the problem involves two envelopes with random (on some probability distribution $P$) amounts inside. You draw one and have to guess whether it contains more or less than the other. General intuition dictates you have at most a 50% chance of being right. However, by generating a random number on the same distribution, you may increase your chances to 66%.

My question is: What is the upper bound on the maximum accuracy when generating an infinite amount of random numbers when there are 3 envelopes?

Furthemore, a much harder one may be: what would the upper bound be for $k$ envlopes?

My investigation just for k=2 gave me the following

I've noticed that, by generating more numbers, $n$, you increase your chances of being right. Specifically, for $k = 2$ as $n\rightarrow\infty$ the probability you are correct approaches a maximum of $75\%$. We can see this graphically: MATLAB Simulation with 100,000 Monte Carlo Trials for each $n$

Or, we may just compute it. The number of arrangements of random numbers are equal to ${n+k\choose n}$. In the case of $k=2$, there simply are $\frac{(n+2)(n+1)}{2}$ arrangements. Making a guess based on these arrangements are dependent on where the majority of the numbers lie; let each number be $y_i \;\forall i = 1,2,\ldots,n$. For simplicity, lets work with just odd $n$'s. It is fairly intutive that the accuracy for $n+1$ is greater than $n$, while computationally, it can be seen that $\left(\Pr(n+1)-\Pr(n)\right)\approx0$ for large $n$'s. So we may assume that, for a large $n$'s, analyzing just odd $n$'s is enough.

When less than half the random numbers ($floor(n/2)$) are below those in the two envelopes $(a,b)$, there are an easily countable number of events where our prediction will have $100\%$ accuracy. We may then see that there exist $$\sum_{j=0}^{floor(n/2)}{n-ceil(n/2)+1\choose n-ceil(n/2)} = \left(floor(n/2)+1)\right)(n-ceil(n/2)+1) = x$$ of these situations. As shown in the previous link, all other events will only lead you to a correct guess $50\%$ of the time; you can work this out yourself just for odd $n$'s. Thus, the probability of you being correct having generated some odd $n$ random numbers is:

$$\left((100\%)x + (50\%)({n+2\choose n}-x)\right)/{n+2\choose n}$$

$$ = 1/2 + \frac{x}{(n+1)(n+2)}$$

When looking at just odd $n$'s,

$$ 1/2 + \frac{\left(\frac{n-1}{2}\right)\left(n-\frac{n+1}{2}+1\right)}{(n+1)(n+2)}$$

$$\lim_{n\to\infty} \left[ 1/2 + \frac{\left(\frac{n-1}{2}\right)\left(n-\frac{n+1}{2}+1\right)}{(n+1)(n+2)} \right] = 1/2 + 1/4 = 75\%$$

Running 1,000,000 Monte Carlo trials where $n=10000$ gave me $0.7446$, which is pretty close. The same for $k=3$ gave me $0.5143$, but how do we get there mathematically?

Answer 1

First, we can considerably simplify your analysis of the $k=2$ case. By comparing an arbitrary number of samples from the distribution with the given value $v$, you're effectively finding the cumulative distribution function $F(v)$ at that value. The strategy is to switch if this is less than $\frac12$, and the success probability is $1$ if the two values in the envelopes are on opposite sides of $F(v)=\frac12$ and $\frac12$ otherwise, for a total success probability of $\frac12\cdot1+\frac12\cdot\frac12=\frac34$. Since only $F(v)$ enters into the calculations, we may as well assume uniform distribution on $[0,1]$ and use $F(v)=v$.

Unfortunately you didn't specify how you want to generalise the problem to $k$ envelopes. There are a number of possible generalisations:

1. Maximise the probability of correctly guessing whether the first value is the highest
2. Maximise the probability of correctly guessing the rank of the first value
3. Maximise the probability of stopping at the highest value
4. Maximise the expected value

Variant $4$ depends on the distribution and is thus a different kind of problem.

For variant $1$, we should guess that the first value $v$ is the highest if it is above some threshold $t$. Then the probability that we guess right is

$$ \int_0^t\left(1-v^{k-1}\right)\mathrm dv+\int_t^1v^{k-1}\mathrm dv=t+\frac1k\left(1-2t^k\right)\;. $$

Setting the derivative with respect to $t$ to $0$ yields $1-2t^{k-1}=0$ and thus $t=2^{-1/(k-1)}$, with resulting success probability

$$ 2^{-1/(k+1)}+\frac1k\left(1-2\cdot2^{-k/(k-1)}\right)=\frac1k+2^{-1/(k-1)}\left(1-\frac1k\right)\;, $$

which reduces to $t=\frac12$ and success probability $\frac34$ for $k=2$. For $k=3$, the success probability is

$$\frac13+2^{-1/2}\cdot\frac23\approx80\%\;,$$

so this is apparently not what you had in mind.

For variant $2$, we need $k-1$ thresholds $t_1,\ldots,t_{k-1}$, and each of them should be placed where the likelihood for two adjacent ranks is equal, so

$$ \binom{k-1}{i-1}t_i^{i-1}(1-t_i)^{k-i}=\binom{k-1}it_i^i(1-t_i)^{k-i-1}\;, $$

with solution $t_i=\frac ik$, so the thresholds are evenly spaced as one might expect. The success probability is

$$ \sum_{i=1}^k\int_{(i-1)/k}^{i/k}\binom{k-1}{i-1}v^{i-1}(1-v)^{k-i}\mathrm dv\;. $$

I don't know how to simplify that for general $k$. For $k=3$, the success probability is

\begin{align} &\int_0^\frac13\binom20(1-v)^2\mathrm dv+\int_\frac13^\frac23\binom21v(1-v)\mathrm dv\int_\frac23^1\binom22v^2\mathrm dv\\ ={}&\frac{19}{81}+\frac{13}{81}+\frac{19}{81}\\ ={}&\frac{51}{81}\\ \approx{}&63\%\;, \end{align}

so this is apparently also not what you had in mind.

Variant $3$ is known as the full-information best-choice problem; for references see e.g. Winning rate in the full-information best-choice problem by A. Gnedin and D. Miretskiy. Here the success probability tends to approximately $58\%$ for $k\to\infty$. For $k=3$, we can consider two thresholds $t_1$ and $t_2$ and optimise the resulting success probability. If we stop at the first value $v_1$ if it is above $t_1$, we will succeed on the first value with probability

$$ \int_{t_1}^1v_1^2\mathrm dv_1=\frac13\left(1-t_1^3\right)\;. $$

The second threshold $t_2$ should be lower than $t_1$ (since we have fewer chances afterwards). Then the probability to win on the second value is

\begin{align} &\int_0^{t_2}\mathrm dv_1\int_{t_2}^1v_2\mathrm dv_2+\int_{t_2}^{t_1}\mathrm dv_1\int_{v_1}^1v_2\mathrm dv_2 \\ ={}& \int_0^{t_2}\mathrm dv_1\frac12\left(1-t_2^2\right)+\int_{t_2}^{t_1}\mathrm dv_1\frac12\left(1-v_1^2\right)\\ ={}&\frac12t_1-\frac16t_1^3-\frac13t_2^3\;, \end{align}

and the probability to win on the third value is

\begin{align} &\int_0^{t_1}\mathrm dv_1\int_0^{v_1}(1-v_1)\mathrm dv_2+\int_0^{t_2}\mathrm dv_1\int_{v_1}^{t_2}(1-v_2)\mathrm dv_2 \\ ={}& \int_0^{t_1}\mathrm dv_1v_1(1-v_1)+\int_0^{t_2}\mathrm dv_1\left((t_2-v_1)-\frac12\left(t_2^2-v_1^2\right)\right) \\ ={}& \frac12t_1^2-\frac13t_1^3+t_2^2-\frac12t_2^2-\frac12t_2^3+\frac16t_2^3 \\ ={}& \frac12t_1^2-\frac13t_1^3+\frac12t_2^2-\frac13t_2^3\;. \end{align}

Thus the total success probability is

$$ \frac13-\frac13t_1^3+\frac12t_1-\frac16t_1^3-\frac13t_2^3+\frac12t_1^2-\frac13t_1^3+\frac12t_2^2-\frac13t_2^3 \\ =\frac13+\frac12t_1+\frac12t_1^2-\frac56t_1^3+\frac12t_2^2-\frac23t_2^3\;. $$

Optimising yields $t_2=\frac12$ (unsurprisingly) and $\frac12+t_1-\frac52t_1^2=0$, with positive solution $t_1=(1+\sqrt6)/5\approx0.6899$, and the optimal success probability is

$$ \frac13+\frac12\frac{1+\sqrt6}5+\frac12\left(\frac{1+\sqrt6}5\right)^2-\frac56\left(\frac{1+\sqrt6}5\right)^3+\frac12\left(\frac12\right)^2-\frac23\left(\frac12\right)^3\\=\frac{293+48\sqrt6}{600}\approx68\%\;, $$

so this is apparently also not what you had in mind.

Which raises the question: What did you have in mind?