Repetir algo con (1/n)ª probabilidad de éxito n veces

Question

¿Hay algo que se pueda decir sobre cuántos intentos serán necesarios para adivinar correctamente un número aleatorio de entre 1000 números? Si el número no cambiara, la probabilidad aumentaría con cada intento, dando al final una probabilidad de 1.

Si el número cambia cada vez que adivinas, tienes una probabilidad de 1/1000 cada vez. Se puede calcular cuántos intentos probablemente tomaría, en promedio?

(Lo siento, no soy muy ducho en matemáticas probabilísticas)

Answer 1

Este concepto es la base del Ley de los grandes números que está detrás de la mayoría de los conceptos de probabilidad. Por definición, si dados 1000 ensayos aleatorios únicos, un suceso concreto (resultado) ocurre una vez, entonces la probabilidad observada de que ocurra ese suceso es de 1/1000. La inversa es básicamente la aplicación de la probabilidad calculada; si un suceso tiene una probabilidad de 1/1000, entonces si realizas 1000 ensayos, deberías esperar que el suceso ocurriera una vez. Para un suceso independiente (los resultados de los ensayos anteriores no influyen en la probabilidad de los futuros), no es garantizado ocurra exactamente una vez cada 1000 ensayos, pero a medida que el número de ensayos t aumenta, el número de veces que un suceso con probabilidad $1/n$ ocurre se acercará $t/n$ .

Ahora bien, si empezamos con el primer ensayo y seguimos realizando ensayos hasta que se produzca el suceso, y luego contamos cuántos ensayos tardó, la probabilidad de que ocurra por primera vez exactamente en el ensayo X es igual a la probabilidad de que ocurra no ocurrir en cualquiera de los ensayos X-1, y que hace ocurren el día X. La probabilidad de que no ocurra es $\dfrac{n-1}{n}$ (o equivalentemente $1-\dfrac{1}{n})$ y debe ocurrir X-1 veces, seguido del suceso que ocurre la Xª vez ( $1/n$ probabilidad), por lo que la fórmula para la probabilidad de que ocurra exactamente en el Xº ensayo es

$$P(X)=(1-\dfrac{1}{n})^{X-1}(\dfrac{1}{n})$$

Introduciendo nuestro valor específico conocido para N, obtenemos:

$$P(X)=(\dfrac{999}{1000})^{X-1}(\dfrac{1}{1000})$$

Se trata de una función exponencial que se reduce asintóticamente; se aproxima a cero a medida que X crece infinitamente. Como tal, no hay un punto en el que empiece a ser más probable que ocurra, sino que cada vez menos probable que no suceder. Sin embargo, si consideramos sólo la probabilidad de que no ocurra en X-1 ensayos ( $(\dfrac{999}{1000})^{X-1}$ ), podemos hallar un "exceso-menos", en el que es igual de probable que se necesiten más ensayos que menos. Este es nuestro "valor esperado" para el número de intentos que debería hacer (similar al "valor esperado" de una tirada de dados; la probabilidad de que sea mayor o igual que un determinado valor nominal es 1 en 1, pero sólo 1/6 en 6, y en el valor esperado de 3,5, las probabilidades son 50-50 en cualquier caso). Con un poco de magia gráfica, vemos que el número de intentos tras los cuales la probabilidad de que tu número no haya salido hasta ahora cae por debajo de 0,5 es 674.

Por lo tanto, antes de que empiece a elegir los números, puede esperar que pasen, de media, unos 674 intentos hasta que el número que desea aparezca por primera vez. Sin embargo, sigue habiendo un 36% de probabilidades de que no aparezca en 1.000 intentos, y un 13% de probabilidades de que no aparezca ni una sola vez en 2.000 intentos, y dado que no ha aparecido en 674 intentos (ni en 1.000 ni en 100.000), la probabilidad de que el siguiente número sea el que usted desea sigue siendo de 1 entre 1.000.

Answer 2

Sea $K$ sea el número de intentos necesarios. Se desea calcular el valor esperado de $K$ es decir $E[K]$ . Como se trata de una distribución discreta, tenemos $E[K] = \sum_{k=1}^\infty k p_k$ donde $p_k$ es la probabilidad de que se tarde exactamente $k$ intentos de adivinar el número correcto.

Número fijo : Si el número es fijo, entonces el número esperado es fácil de calcular. Obsérvese que $p_k = 0$ para $k > 1000$ ya que para entonces habrás averiguado el número (¡supongo que las suposiciones no se repiten!). Para calcular $p_k$ para $k \leq 1000$ necesitamos la probabilidad de hacer $k-1$ conjeturas incorrectas (sin "reemplazo"), multiplicado por la probabilidad de que el $k$ la suposición es correcta, es decir, $p_k = \frac{1000 - 1}{1000 - 0} \frac{1000 - 2}{1000 - 1} \cdots \frac{1000-(k-1)}{1000-(k-2)} \frac{1}{1000-(k-1)} = \frac{999}{1000} \frac{998}{999} \cdots \frac{1000-k+1}{1000-k+2} \frac{1}{1000-k+1} = \frac{1}{1000}$ . En consecuencia, $E[K] = \frac{1}{1000} \sum_{k=1}^{1000} k = \frac{1001}{2}$ . Es decir, por término medio se esperan 500,5 intentos.

Cambio de número : Si el número se selecciona aleatoriamente entre 1.000 números cada vez, el número esperado de intentos es fácil de calcular.

En este caso $p_k = (1-\theta)^{k-1}\theta$ donde $\theta = \frac{1}{1000}$ . Así que la respuesta es $E[K] = \sum_{k=1}^\infty k (1-\theta)^{k-1}\theta$ .

Desde $\sum_{k=1}^\infty k (1-\theta)^{k-1} = \frac{1}{\theta^2}$ esto da $E[K] = \frac{1}{\theta} = 1000$ . Es decir, por término medio se esperan 1000 intentos.

Answer 3

Como usted dijo, si el número no cambia mientras que usted está adivinando, y siempre adivinar un número que no lo ha adivinado aún, entonces su probabilidad de obtener el número de la derecha dentro de la $m \le n$ conjeturas es sólo $m/n$. Para hacer que la probabilidad de acertar llegar a $p$, usted necesita $m(p)=pn$ conjeturas.

Por otro lado, si el número de cambios después de cada adivinar, entonces su probabilidad de equivocarse es $1-1/n$ por cada adivinar (independiente de cómo muchas conjeturas se han hecho ya), y su probabilidad de equivocarse $m$ veces consecutivas es $$\left(1-\frac{1}{n}\right)^{m} \sim \exp\left(-\frac{m}{n}\right),$$ donde la aproximación es asintóticamente válidos como $n\rightarrow\infty$. Aquí, para hacer que la probabilidad de acertar llegar a $p$, usted necesita $$ m(p)=-n\log(1-p)=pn+\frac{1}{2}p^2n+\frac{1}{3}p^3n + \ldots $$ conjeturas. Tenga en cuenta que esto es aproximadamente igual a $pn$ pequeña $p$, pero para $p$ aproxima $1$ (es decir, para lograr la certeza), se necesita una divergentes número de conjeturas.