Actualmente estoy leyendo las notas del curso sobre la teoría de la probabilidad de Stanford CS109 . Para practicar un poco y acostumbrarme a los temas presentados, también estoy tratando de resolver los conjuntos de problemas, pero me encontré con uno que me parece un poco ambiguo. Es el problema 11a de Conjunto de problemas 1 :
Digamos que un hacker tiene una lista de n candidatas a contraseña distintas, sólo una de las cuales la conectará con éxito a un sistema seguro.
a. Si ella intenta contraseñas de la lista al azar, borrando las que no funcionan, ¿cuál es la probabilidad de que su primer acceso exitoso sea (exactamente) en su k-intento?
Suponemos que k está entre 1 y n (inclusive), de lo contrario el problema es trivial.
Una forma de pensar en el problema sería la siguiente: la probabilidad de tener éxito en el intento k-ésimo es el producto de las probabilidades de elegir una contraseña incorrecta en los primeros pasos k - 1 multiplicado por la probabilidad de tener éxito en el paso k-ésimo, que es:
$$ p = \frac {n - 1}{n} \frac {n - 2}{n - 1} \cdots \frac {n - k + 1}{n - k + 2} \frac {1}{n - k + 1} = \frac {1}{n} $$
Otra forma sería pensar en todas las n! permutaciones de las n contraseñas y ver cada permutación como el orden en que el hacker probará las contraseñas. Estamos interesados en encontrar el número de permutaciones que tienen, digamos, el elemento x (la contraseña correcta) en la posición k-th. Hay (n - 1)! tales permutaciones, por lo tanto la respuesta seguirá siendo $ \frac {1}{n} $ . Hay un problema con este enfoque: Supongamos que hay 3 contraseñas: $p_1$ , $p_2$ y $p_3$ . Hay 6 posibles permutaciones de estas 3 contraseñas:
$$ p_1, p_2, p_3, \\ p_1, p_3, p_2, \\ p_2, p_1, p_3, \\ p_2, p_3, p_1, \\ p_3, p_1, p_2, \\ p_3, p_2, p_1, $$ así que si queremos encontrar la probabilidad de adivinar la contraseña correcta desde el primer intento, usando la fórmula anterior diríamos que es $ \frac {1}{3}$ . Sin embargo, siempre y cuando el hacker haya encontrado la contraseña correcta desde el primer intento, las 2 primeras permutaciones son en realidad equivalentes (no nos interesa el orden en que el hacker debía probar las siguientes contraseñas - siempre y cuando haya encontrado la correcta, se detiene - o al menos así es como interpreto el problema), por lo que la probabilidad correcta sería en realidad $ \frac {1}{5}$ .
Por esta razón, la primera aproximación también es incorrecta. Mi explicación para esto sería la siguiente: si denotáramos por $T_i$ el i-ésimo juicio y $T_k=1$ cuando el hacker adivine la contraseña correcta en el k-intento, lo que queremos encontrar es $$ P(T_0 = 0 \wedge T_1 = 0 \wedge \cdots \wedge T_{k-1} = 0 \wedge T_k = 1) ,$$ (donde por $ \wedge $ denotan la probabilidad de que los eventos ocurran juntos) que sería igual al producto de las probabilidades de cada evento sólo en el caso de que todos los eventos sean independientes (y en nuestro caso no lo son, ya que dejamos de intentar las contraseñas una vez que adivinamos la correcta)
La perspectiva final (y supongo que correcta) es: la probabilidad de adivinar en el k-ésimo intento se representa por el número de formas en que el hacker puede adivinar en el k-ésimo intento dividido por el número total de formas en que el hacker puede adivinar la contraseña en general (que es la suma de formas en que el hacker puede adivinar la contraseña en el i-ésimo intento, con i de 1 a n). Hay: $$ (n-1)(n-2) \cdots (n-k+1) = \prod_ {i = 1}^{k - 1} (n-i), \text {if k > 1} $$ $$ 1, \text {if k = 1} $$ formas en las que puede adivinar la contraseña correcta en el k-intento, así que el resultado sería: $$ \frac { \prod_ {i = 1}^{k - 1} (n-i)}{1 + \sum_ {j=2}^{j=n} \prod_ {i = 1}^{i = j - 1} (n-i) } $$
Mi pregunta es: ¿es correcto mi razonamiento y si no, dónde está el error? Las diferentes perspectivas son el resultado de un debate con alguien, pero no pudimos ponernos de acuerdo en la respuesta correcta (aunque estoy bastante seguro de que la última es correcta, pero podría haber algo que me falta)
¡Gracias!
0 votos
El primer enfoque es correcto. El problema con el segundo enfoque es que estás cambiando de caballo a mitad de camino, por así decirlo. Primero haces que el hacker elija una permutación, y preguntas cuál es la probabilidad de que $k$ La contraseña es correcta, y luego se sustituye por una pregunta diferente en el medio. No entendí el tercer enfoque.