Más generalmente, suponga que hay $n$ cartas en total en la baraja, donde $k$ de las cartas se consideran buenas, mientras que las $n-k$ cartas restantes son malas. El objetivo es el mismo; se baraja la baraja y, a medida que se voltean las cartas de la baraja, tiene la opción de llamar "¡alto!" en cualquier momento. Ganas siempre y cuando la próxima carta repartida sea buena. ¿Cuál es la estrategia óptima?
Además, modifiquemos las reglas para decir que, cuando queda solo una carta, debes llamar alto obligatoriamente. Un jugador que no llama alto antes de la última carta pierde automáticamente, por lo que esta modificación no hace ninguna diferencia para un jugador óptimo.
Resulta que cada estrategia es la estrategia óptima.
Teorema: Cada estrategia para este juego tiene una probabilidad de ganar de $k/n$.
Por lo tanto, para responder a tu pregunta, la probabilidad de ganar es el número de primos en $\{1,\dots,N\}$, dividido por $N$.
Prueba 1: Idea ingeniosa
Considera esta modificación del juego. Supongamos que, al llamar alto, en lugar de ganar cuando la siguiente carta repartida es buena, ganas si la carta inferior de la baraja es buena. Este es un juego tonto, porque no importa cuándo llames ¡alto! Siempre ganarás si y solo si la carta inferior es buena. Para el juego modificado, la probabilidad de ganar es $k/n$.
Sin embargo, este juego tiene la misma probabilidad de ganar que el original. El punto es que, después de llamar alto, tanto la siguiente carta como las últimas cartas tienen la misma probabilidad aleatoria de ser buenas, debido a la simetría de la baraja barajada. Por lo tanto, se sigue que el juego original tiene la misma probabilidad de ganar.
Prueba 2: Inducción
Demostramos, por inducción en $n$, que para todo $k\in \{0,1,\dots,n\}$, la probabilidad de ganar es $k/n$ para todas las estrategias en una baraja de $n$ cartas con $k$ cartas buenas.
El caso base de $n=1$ es obvio. Suponiendo que la afirmación es cierta para $n$, donde $n\ge 1$, lo demostramos para $n+1$ de la siguiente manera: $$ \begin{align} P(\text{ganar}) &=P(\text{ganar}\mid \text{la primera carta es buena})P(\text{primera carta buena}) \\&\quad +P(\text{ganar}\mid \text{la primera carta es mala})P(\text{primera carta mala}) \\&=\frac{k-1}{n-1}\cdot \frac{k}{n}+\frac{k}{n-1}\cdot \frac{n-k}{n}=\frac{k}n. \end{align}$$ Esto completa la prueba por inducción.
Prueba 3: Martingala
Para cada $k\in \{0,1,\dots,n-1\}$, sea $X_k$ la proporción de cartas buenas entre las cartas no vistas después de que se han visto $k$ cartas. Entonces, $X_0=k/n$, y $X_1$ es igual a $k/(n-1)$ o $(k-1)/(n-1)$.
Imagina que el jugador sigue una estrategia particular. Sea $T$ el número de turno en el que el jugador llama alto, bajo esa estrategia. La proporción de cartas buenas en el momento de la llamada de alto es $X_T$, por lo que $X_T$ es la probabilidad de que el jugador gane (condicionado a $T$). Solo necesitamos evaluar $\mathbb E[X_T]$, que es la probabilidad incondicional de que la estrategia gane.
La secuencia $X_0,X_1,\dots,X_{n-1}$ es una martingala, con respecto a la filtración natural. Para demostrar esto, debemos mostrar que $\mathbb E[X_{k+1}\mid X_k]=X_k$ para todo $k$. De hecho, dado $X_k$, hay dos posibilidades; o bien sacas una carta buena a continuación con probabilidad $X_k$, en cuyo caso $X_{k+1}$ disminuye a $\frac{(n-k)X_k-1}{n-k-1}$, o sacas una carta mala con probabilidad $(1-X_k)$, en cuyo caso $X_{k+1}$ aumenta a $\frac{(n-k)X_k}{n-k-1}$. Por lo tanto, $$ \mathbb E[X_{k+1}\mid X_k]= X_k\cdot \frac{(n-k)X_k-1}{n-k-1}+\left(1-{X_k}\right)\frac{(n-k)X_k}{n-k-1}={X_k}. $$ Dado que la secuencia es una martingala, y dado que $T$ está acotado, podemos usar el teorema de parada opcional para concluir que $\mathbb E[X_T]=\mathbb E[X_0]=k/n$. Por lo tanto, cada estrategia tiene una probabilidad de éxito de $k/n$.
