La clase de estrategias potencialmente óptimas para la versión estándar (encontrar el mejor, una selección) puede derivarse como sigue: Nunca tiene sentido elegir un candidato peor que el mejor visto hasta ahora. Por lo tanto, una estrategia sólo necesita especificar cuándo elegir un candidato que sea el mejor hasta el momento; llamemos a tal candidato un candidato plausible. Dado que el candidato actual es plausible, el orden relativo de los otros candidatos vistos hasta ahora no proporciona ninguna información sobre la probabilidad de que el candidato actual sea el mejor de todos. Por lo tanto, la decisión de aceptar o no un candidato plausible sólo puede depender de la hora de llegada. Está claro que la probabilidad de que un candidato plausible sea el mejor de todos aumenta con el tiempo, por lo que la solución debe ser no aceptar ningún candidato hasta un determinado momento y aceptar los candidatos plausibles a partir de entonces.
Un razonamiento análogo puede aplicarse al problema 1. Ahora un candidato plausible es alguien que es el mejor o el peor visto hasta el momento. El problema es simétrico con respecto al mejor y al peor, por lo que la estrategia óptima debe ser rechazar a todos los candidatos hasta un determinado momento $r$ y aceptar candidatos plausibles a partir de entonces. El cálculo del valor óptimo de $r$ procede como en la sección de Wikipedia en la versión estándar; la probabilidad de elegir el mejor o el peor candidato es
$$ \begin{align} P(r) &= \sum_{i=1}^{n} P\left(i \text{ is selected}\mid i \text{ is best or worst}\right) \cdot P\left(i \text{ is best or worst}\right) \\ &= 0 + \sum_{i=r}^{n} P\left( \text{best and worst of first } i-1 \text{ are among first } r-1 \mid i \text{ is best or worst} \right) \cdot\frac{2}{n} \\ &= \sum_{i=r}^{n} \frac{(r-1)(r-2)}{(i-1)(i-2)} \cdot \frac{2}{n} \\ &= \frac{(r-1)(r-2)}n\sum_{i=r}^{n} \frac{2}{(i-1)(i-2)}. \end{align} $$
En el límite $n\to\infty$ con $x=r/n$ y $t=i/n$ esto se convierte en
$$x^2\int_x^1\frac2{t^2}\mathrm dt=2x^2\left(\frac1x-1\right)=2x(1-x)\;.$$
El máximo está en $x=1/2$ y la probabilidad alcanzada es $1/2$ . Es decir, en el límite de grandes $n$ la estrategia óptima es rechazar la mitad de los candidatos y aceptar el siguiente candidato que sea el mejor o el peor visto hasta el momento; la probabilidad de elegir el mejor o el peor candidato mediante esta estrategia es $1/2$ .
Otro enfoque es escribir una relación de recurrencia para el valor $a_i$ del juego en el paso de tiempo $i$ bajo el supuesto de que siempre se eligen candidatos plausibles, resolver la recurrencia y elegir $r$ para maximizar $a_r$ . En la versión estándar, ya que el candidato $i$ ser el mejor candidato de todos y candidato $i$ que sean rechazados son eventos mutuamente excluyentes, la probabilidad $a_i$ de éxito es sólo la suma de la probabilidad $1/n$ del candidato $i$ siendo la mejor y la probabilidad $a_{i+1}(i-1)/i$ del candidato $i$ ser rechazado y luego el resto del proceso tiene éxito:
$$a_i=\frac1n+\frac{i-1}ia_{i+1}\;.$$
Dividiendo por $1/n$ y reordenando se obtiene
$$\frac{a_{i+1}-a_i}{1/n}=-1+\frac{a_{i+1}}i\;,$$
que en el límite $n\to\infty$ con $t=i/n$ y $a(i/n)=a_i$ se convierte en
$$a'(t)=-1+\frac{a(t)}t$$
con solución
$$a(t)=-t\log t$$
como se esperaba. La derivación correspondiente para el problema $1$ es
$$a_i=\frac2n+\frac{i-2}ia_{i+1}\;,$$
$$\frac{a_{i+1}-a_i}{1/n}=-2+2\frac{a_{i+1}}i\;,$$
$$a'(t)=-2+2\frac{a(t)}t$$
con solución
$$a(t)=2t(1-t)$$
como se esperaba.
Problema $3$ son sólo dos instancias independientes de la versión estándar, ya que el primer candidato nunca se elige y todos los candidatos restantes pueden ser un candidato plausible como máximo para uno de los objetivos. Por lo tanto, en este caso la estrategia óptima consiste en elegir a los candidatos que son los mejores o los peores hasta el momento, empezando por $x=1/\mathrm e$ y la probabilidad de éxito resultante es $(1/\mathrm e)^2$ .
Problema $2$ es más difícil, y la probabilidad de encontrar la mediana tiende a $0$ para $n\to\infty$ . Básicamente, esto se debe a que en los otros problemas el éxito es casi seguro al elegir candidatos plausibles cerca del final, mientras que en el Problema $2$ sólo el último candidato tiene probabilidad $1$ de ser la mediana si es un candidato plausible, y la penúltima ya sólo tiene una probabilidad aproximada de $1/2$ y así sucesivamente.
El problema puede resolverse numéricamente como sigue: Las decisiones sólo pueden depender del rango del candidato actual. Al principio del proceso, todos los candidatos deben ser rechazados; más tarde, deben aceptarse los candidatos que se encuentren en algún rango de los rangos centrales, donde el rango depende del tiempo. Para determinar el rango óptimo en cada paso de tiempo, podemos empezar por el final, y en cada paso de tiempo para cada rango comparar la probabilidad de éxito si elegimos el candidato, dado su rango, con la probabilidad de éxito si omitimos el candidato, y elegimos el mayor. Entonces, sumando estas probabilidades de éxito sobre todos los rangos, obtenemos la probabilidad de éxito global, que se convierte en la probabilidad de éxito al saltar para el paso de tiempo anterior.
Dado que el $i$ -el candidato tiene rango $j$ su probabilidad de ser la mediana es (suponiendo que impar $n$ )
$$P(i\text{ is the median}\mid i\text{ has rank } j)=\frac in\frac{\binom m{j-1}\binom m{i-j}}{\binom{2m}{i-1}}$$
(la probabilidad $1/n$ de ser la mediana sobre la probabilidad $1/i$ de tener rango $j$ veces la probabilidad de elegir $j-1$ de $m$ valores por encima de éste y $i-j$ de $m$ valores inferiores a éste, donde $m=(n-1)/2$ ). La aproximación mediante la fórmula de Stirling no conduce a una ecuación invariable en escala como en los otros problemas. La solución numérica muestra que la probabilidad de éxito disminuye con $n$ y la fracción de candidatos a partir de la cual hay que empezar a aceptar candidatos con rangos centrales aumenta con $n$ . Hasta $n=729$ La gama de rangos centrales en los que los candidatos deben ser aceptados nunca crece más allá de $5$ a ambos lados del centro. Estos son algunos resultados de la probabilidad de éxito $p$ y para el número $r$ y la fracción $x$ de los candidatos iniciales a ser ignorados:
$$ \begin{array}{c|c|c} n&p&r&x\\\hline 1&1\\ 3&0.333333\\ 9&0.256085&4&0.444444\\ 27&0.174775&16&0.592593\\ 81&0.122964&54&0.666667\\ 243&0.086665&180&0.740741\\ 729&0.060955&590&0.809328 \end{array} $$
(Las entradas de la parte superior derecha están vacías porque no hay elección en la primera línea y la elección no hace ninguna diferencia en la segunda línea). Este es el código que he utilizado para ello; también realiza una simulación al final para comprobar que la estrategia optimizada alcanza la probabilidad calculada.
Parece que la probabilidad de éxito puede seguir una ley de potencia en función de $n$ Si es así, el exponente es aproximadamente $-0.32$ .
