Pergunta simples de combinação / probabilidade com base no comprimento da string e nos caracteres possíveis

9

Supondo "aleatoriedade completa" e com uma sequência de 20 caracteres, em que cada caractere pode ser um dos 62 caracteres possíveis:

  • Qual é o número total de combinações possíveis? (Adivinhando 20 ao poder de 62.)
  • Além disso, se novas sequências de caracteres forem selecionadas aleatoriamente uma após a outra e adicionadas a uma lista de sequências de caracteres selecionadas até agora, quantas sequências de caracteres devem ser selecionadas antes que a chance de selecionar uma sequência que já tenha sido selecionada esteja abaixo de 1 em 100000 ( )?105

Nota: 62 vem de: dígitos numéricos (0 a 9), letras maiúsculas (AZ) e letras minúsculas (az).

erros
fonte
2
Seu segundo marcador pode ser lido de (pelo menos) duas maneiras possíveis. Eu estou querendo saber o que você está interessado. ( 1 ) A probabilidade de que o º seqüência corresponder a uma das seqüências anteriores ou ( 2 ) A probabilidade de que pelo tempo que o º string é selecionado existe algum duplicado dentro da coleção de cordas desenhadas até agora. As respostas para essas duas perguntas serão muito diferentes. :)nn
cardeal
11
Talvez considerar um alfabeto de dois caracteres torne a diferença clara. Deixe as letras ser e . Podemos perguntar: ( 1 ) Para que temos pelo menos 99% de chance da ésima sequência ser uma duplicata de uma sequência anterior? O aqui é 8, pois a única maneira de falharmos é se nossa sequência é ou , que tem probabilidade total . Ou, perguntamos ( 2 ) Para que temos pelo menos 99% de chance de ver alguma duplicata? Nesse caso, já que, no momento em que vimos três cadeias,HTnnnTTTTHHHHHT2(n1)nn=3Hou foi repetido pelo menos uma vez. T
cardeal
11
A resposta de Matt lida com ( 1 ), que essencialmente responde à pergunta sobre se "minha" string corresponde à de outra pessoa. Mas, se você está preocupado com o fato de as cordas de outras duas pessoas também potencialmente corresponderem, então você está interessado em ( 2 ). Tudo se resume a se você tem uma sequência específica de interesse com a qual está comparando todas as outras ou se está comparando todas as sequências. Não tenho certeza se estou deixando isso mais claro, no entanto. (Seu problema resume-se a uma das duas variantes do famoso chamado "paradoxo do aniversário".)
cardeal
11
Cardeal está, como sempre, correto. Presumi que você tivesse uma string "alvo", para a qual estava gerando uma lista de suposições. Se, em vez disso, você estiver gerando seqüências aleatoriamente e quiser saber o número que é seguro gerar antes que as duas correspondam, a resposta é muito diferente. Vou alterar minha resposta para resolver esse caso, se estiver tudo bem com você.
Matt Krause
11
Não deixei meu exemplo anterior completamente claro. Me desculpe por isso. Eu estava pensando em um alfabeto de duas letras e desenhando cordas de comprimento um . Por isso, quando eu escrevi , que representava , , ..., , . {H,T}HHHHTs1=Hs2=Hsn1=Hsn=T
cardeal

Respostas:

11

Número total de possibilidades

1) Fechar! Você tem 62 opções para o primeiro caractere, 62 para o 2º, etc., então você acaba com , que é um número absurdamente grande.62626262=6220

Colisão com uma String "Target"

2) Como estabelecemos acima, existem cadeias em potencial. Você quer saber quantas precisaria adivinhar para ter mais de 1 em 100.000 chances de adivinhar a sequência "alvo". Essencialmente, você está perguntando o que Para deixar claro, você teria que arredondar x para cima (ou adicionar um, se forem precisamente iguais), mas como você verá em um segundo, isso realmente não importa.6220

x62201105

Através da álgebra básica, podemos reorganizar isso como

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

Fazendo as contas, é de cerca de , então vamos chamar a coisa toda de ou, mais sucintamente, um monte de coisas.6.2207101571030

É por isso que as senhas longas funcionam muito bem :-) Para senhas reais, é claro, você precisa se preocupar com cadeias de comprimento menores ou iguais a vinte, o que aumenta ainda mais o número de possibilidades.

Duplicatas na lista

Agora, vamos considerar o outro cenário. As strings são geradas aleatoriamente e queremos determinar quantas podem ser geradas antes que exista uma chance de 1: 100.000 de quaisquer duas strings correspondentes. A versão clássica desse problema é chamada de Problema de Aniversário (ou 'Paradoxo') e pergunta qual é a probabilidade de duas de n pessoas terem o mesmo aniversário. O artigo da wikipedia [1] parece decente e possui algumas tabelas que você pode achar úteis. No entanto, vou tentar dar a você o sabor da resposta aqui também.

Algumas coisas a ter em mente:

-A probabilidade de uma correspondência e de não haver correspondência deve somar 1, então e vice-versa.P(match)=1P(no match)

-Para dois eventos independentes e , a probabilidade de .ABP(A&B)=P(A)P(B)

Para obter a resposta, começaremos calculando a probabilidade de não encontrar uma correspondência para um número fixo de cadeias . Uma vez que sabemos como fazer isso, podemos definir essa equação igual ao limite (1 / 100.000) e resolver para . Por conveniência, vamos chamar o número de sequências possíveis ( ).kkN6220

Nós vamos 'andar' pela lista e calcular a probabilidade de que a string ^ {th} corresponda a qualquer uma das strings "acima" dela na lista. Para a primeira string, temos strings totais e nada na lista, então . Para a segunda sequência, ainda existem possibilidades totais, mas uma delas foi "usada" pela primeira, portanto, a probabilidade de uma correspondência para essa sequência é Para a terceira sequência, há duas maneiras de uma correspondência e, portanto, não, portanto e assim por diante. Em geral, a probabilidade dokNPk=1(no match)=NN=1NPk=2(no match)=N1NN2Pk=3(no match)=N2Nk késima sequência que não corresponde às outras é

Pk(no match)=Nk+1N

No entanto, queremos a probabilidade de não haver correspondência entre nenhuma das strings. Como todos os eventos são independentes (de acordo com a pergunta), podemos apenas multiplicar essas probabilidades juntas, assim: Isso pode ser simplificado um pouco: O primeiro passo apenas multiplica as frações, o segundo usa a definição de fatorial ( ) para substituir os produtos dek

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+1N com algo um pouco mais gerenciável, e a etapa final alterna em um coeficiente binomial. Isso nos dá uma equação para a probabilidade de não haver correspondências após a geração de strings. Em teoria, você pode definir isso igual a e resolver para . Na prática, será difícil responder, pois você multiplicará / dividirá por grandes números - os fatoriais crescem muito rapidamente ( Tem mais de 150 dígitos).k1100,000k100!

No entanto, existem aproximações, tanto para calcular o fatorial quanto para todo o problema. Este artigo [2] sugere onde p é a probabilidade de não encontrar uma correspondência. Seus testes atingem o máximo de , mas ainda é bastante preciso lá. Conectando seus números, recebo aproximadamente .

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

Referências

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

[2] Mathis, Frank H. (junho de 1991). "Um problema generalizado de aniversário". Revisão do SIAM (Sociedade de Matemática Industrial e Aplicada) 33 (2): 265–270. Link JSTOR

Matt Krause
fonte
+1 Incrível, dado claramente que minhas habilidades matemáticas fracas resultaram na pergunta, deixarei a pergunta sem resposta por um dia, mas fica bem para mim e fica muito mais clara do que eu esperava - uma resposta muito clara - obrigado!
Erro #
11
Feliz em ajudar! Deixe-me saber se algo não está claro. Para chutes, corri os números. Você precisará de 7044234255469980229683302646164 suposições; como eu disse - muito!
Matt Krause
+1 @Matt Krause: +1 ao seu comentário abaixo da resposta; sua resposta e seu compromisso em dar a melhor resposta possível é exemplar, digna de nota e obrigado por todo o seu trabalho duro!
erros cometidos