Probabilidad de que aparezca una cadena de 3 caracteres en una contraseña generada aleatoriamente

Question

Si tiene una contraseña generada aleatoriamente, que consta de solo caracteres alfanuméricos, de longitud 12, y la comparación no distingue entre mayúsculas y minúsculas (es decir, 'A' == 'a') , ¿cuál es la probabilidad de que una cadena específica de longitud 3 (por ejemplo, 'ABC') aparezca en esa contraseña?

Sé que el número total de combinaciones posibles es (26 + 10)^12, pero más allá de eso, estoy un poco perdido. Una explicación de las matemáticas también sería de gran ayuda.

Answer 1

La cadena "abc" puede aparecer en la primera posición, por lo que la cadena se parece a esto:

abcXXXXXXXXX 

... donde las X puede ser cualquier letra o número. Hay (26 + 10)^9 tales cadenas.

Puede aparecer en la segunda posición, por lo que la cadena se parece a:

XabcXXXXXXXX 

y hay (26 + 10)^9 estas cadenas también.

Dado que "abc" puede aparecer en cualquier lugar desde la primera hasta la décima posición, hay 10 * 36^9 de estas cadenas.

Pero esto overcounts, cuerdas, ya que cuenta (por ejemplo) como éste en dos ocasiones:

abcXXXabcXXX 

así que tenemos que contar con todas las cadenas de este tipo y restar a retirarse de nuestra total.

Dado que hay 6 X en este patrón, hay 36^6 cadenas que coinciden con este patrón.

Obtengo 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 patrones como este. (Si el primer "abc" está al principio, el segundo puede estar en cualquiera de los 7 lugares. Si el primer "abc" está en el segundo lugar, el segundo puede estar en cualquiera de 6 lugares. Y así sucesivamente)

Reste de 28 * 36^6.

... pero que resta fuera demasiado, ya que resta de cadenas como esto tres veces en lugar de una sola vez:

abcXabcXabcX 

así que tenemos que añadir de nuevo en las cadenas de este tipo, dos veces.Obtengo 4 + 3 + 2 + 1 + 3 + 2 + 1 + 2 + 1 + 1 = 20 de estos patrones, lo que significa que debemos agregar nuevamente en 2 * 20 * (36^3).

Pero eso matemáticas contado esta cadena de cuatro tiempos:

abcabcabcabc 

... así que tienen que restar fuera 3.

Respuesta final:

10*36^9 - 28*36^6 + 2*20*(36^3) - 3 

divisoria que por 36^12 para obtener tu probabilidad.

Véase también el Inclusion-Exclusion Principle. Y avíseme si cometí un error en mi conteo.

Answer 2

Para ampliar la respuesta de Paul R. Probabilidad (para resultados igualmente probables) es la cantidad de resultados posibles de su evento dividido por la cantidad total de resultados posibles.

Hay 10 lugares posibles donde una cuerda de longitud 3 se puede encontrar en una cadena de longitud 12. Y hay 9 puntos más que se pueden rellenar con cualquier otro carácter alfanumérico, lo que conduce a 36^9 posibilidades. Entonces, la cantidad de resultados posibles de su evento es 10 * 36^9.

Divida eso por su número total de resultados 36^12. Y su respuesta es 10 * 36^-3 = 0.000214

EDITAR: Esto no es completamente correcto. En esta solución, algunos casos se cuentan por partida doble. Sin embargo, solo contribuyen muy poco a la probabilidad, por lo que esta respuesta sigue siendo correcta hasta 11 decimales. Si quiere la respuesta completa, vea la respuesta de Nemo.

Answer 3

Si A no es igual a C, la probabilidad P(n) de ABC que ocurren en una cadena de longitud n (suponiendo que cada símbolo alfanumérico es igualmente probable) es

P(n)=P(n-1)+P(3)[1-P(n-3)] 

donde

P(0)=P(1)=P(2)=0 and P(3)=1/(36)^3