Pregunta simple de combinación / probabilidad basada en la longitud de la cadena y los posibles caracteres

9

Suponiendo "aleatoriedad completa" y se le da una cadena con una longitud de 20 caracteres donde cada carácter puede ser uno de los 62 caracteres posibles:

  • ¿Cuál es el número total de combinaciones posibles? (Adivinando 20 al poder de 62.)
  • Además, si las nuevas cadenas se seleccionan aleatoriamente una tras otra y se agregan a una lista de cadenas seleccionadas hasta ahora, cuántas cadenas deben seleccionarse antes de que la posibilidad de seleccionar una cadena que ya se haya seleccionado sea inferior a 1 en 100000 ( )105

Nota: 62 proviene de: dígitos numéricos (0-9), letras mayúsculas (AZ) y letras minúsculas (az).

errores
fuente
2
Su segundo punto puede leerse (al menos) de dos maneras posibles. Me pregunto que le interesa. ( 1 ) La probabilidad de que el º cadena coincide con una de las cadenas anteriores o ( 2 ) La probabilidad de que en el momento en el n se selecciona ª cadena existe alguna duplicado dentro de la colección de cuerdas dibujadas hasta ahora. Las respuestas a estas dos preguntas serán muy diferentes. :)nn
cardenal
1
HTnnnTTTTHHHHHT2(n1)nn=3HT
1
La respuesta de Matt maneja ( 1 ), que esencialmente responde la pregunta sobre si "mi" cadena coincide con la de otra persona. Pero, si le preocupa que las cadenas de otras dos personas también coincidan, entonces le interesa ( 2 ). Se trata de si tiene una cadena particular de interés con la que está comparando a todos los demás o si está comparando todas las cadenas entre sí. Sin embargo, no estoy seguro de si lo estoy aclarando. (Su problema se reduce a una de las dos variantes del famoso "problema del cumpleaños")
Cardenal
1
Cardinal es, como siempre, correcto. Supuse que tenía una cadena "objetivo", para la cual estaba generando una lista de conjeturas. Si, en cambio, está generando cadenas al azar y desea saber el número que es seguro generar antes de que coincidan dos cadenas, entonces la respuesta es muy diferente. Enmendaré mi respuesta para abordar ese caso, si te parece bien.
Matt Krause
1
{H,T}HHHHTs1=Hs2=Hsn1=Hsn=T

Respuestas:

11

Número total de posibilidades.

62626262=6220

Colisión con una cadena "Target"

6220

x62201105

105x6220105x(6.210)20105x6.2201020x6.2201015

6.2207101571030

Esto es, por supuesto, por qué las contraseñas largas funcionan realmente bien :-) Para las contraseñas reales, por supuesto, debe preocuparse por cadenas de longitud menor o igual a veinte, lo que aumenta aún más el número de posibilidades.

Duplicados en la lista

Ahora, consideremos el otro escenario. Las cadenas se generan al azar y queremos determinar cuántas se pueden generar antes de que haya una probabilidad de 1: 100,000 de que coincidan dos cadenas. La versión clásica de este problema se llama el problema del cumpleaños (o 'paradoja') y pregunta cuál es la probabilidad de que dos de n personas tengan el mismo cumpleaños. El artículo de Wikipedia [1] parece decente y tiene algunas tablas que pueden resultarle útiles. Sin embargo, intentaré darle el sabor de la respuesta aquí también.

Algunas cosas para tener en mente:

P(match)=1P(no match)

ABP(A&B)=P(A)P(B)

kkN6220

kNPk=1(no match)=NN=1NPk=2(no match)=N1NN2Pk=3(no match)=N2Nk

Pk(no match)=Nk+1N

k

P(No Matches)=NNN1NN2NNk+1N
P(No Matches)=N(N1)(N2)(Nk+1)NkP(No Matches)=N!Nk(Nk)!P(No Matches)=k!(Nk)Nk
k!=(k)(k1)(k2)1Nk+1Nk1100,000k100!

k=0.5+0.252Nln(p)
N=48,0003.71015

Referencias

[1] http://en.wikipedia.org/wiki/Birthday_problem

[2] Mathis, Frank H. (junio de 1991). "Un problema generalizado de cumpleaños". Revista SIAM (Society for Industrial and Applied Mathematics) 33 (2): 265–270. Enlace JSTOR

Matt Krause
fuente
+1 Impresionante, dado que mis malas habilidades matemáticas resultaron en hacer la pregunta, así que dejaré la pregunta sin responder por un día, pero me parece bien y es una respuesta mucho más clara de lo que esperaba. ¡Gracias!
errores
1
¡Encantado de ayudar! Avísame si algo no está claro. Por patadas, corrí los números. Necesitará 7044234255469980229683302646164 conjeturas; como dije, ¡mucho!
Matt Krause
+1 @Matt Krause: +1 a su comentario debajo de la respuesta; ¡Su respuesta y compromiso para dar la mejor respuesta posible es ejemplar, digno de mención y gracias por todo su arduo trabajo!
errores