1. Introdução

Suponha que eu pergunte quantas pessoas devem estar em uma sala para que duas delas tenham um aniversário com 50% de probabilidade de um dia. Qual será a resposta? Isso é chamado de paradoxo do aniversário.

O paradoxo diz:

Se houver 23 pessoas na sala, então, com uma probabilidade de 50%, duas delas nasceram no mesmo dia.

Algumas versões do paradoxo fazem afirmações ainda mais fortes:

Se a sala tiver 70 pessoas, com uma probabilidade de 99%, duas delas nasceram no mesmo dia.

No começo, isso pareceu surpreendente e contra-intuitivo para mim. Vamos descobrir por que isso é verdade. Para simplificar a tarefa, fazemos as seguintes suposições:

1. Assumimos que todas as pessoas na sala não nasceram em um ano bissexto. Fazemos essa suposição para que não tenhamos que analisar dois casos diferentes.
2. Não há gêmeos na sala. Com um par de gêmeos, a solução será trivial.
3. Assumimos que as pessoas nascem de maneira uniforme e aleatória. O que isso significa? É provável que as pessoas nascam em qualquer dia do ano. Se isso for formalizado um pouco, a probabilidade de nascimento em qualquer dia escolhido será igual a $$$\ frac {1} {365}$ .
4. As pessoas nascem independentemente uma da outra. Isso significa que a data de nascimento de qualquer pessoa não afeta a data de nascimento de outra pessoa.

Vale a pena notar que essas condições não são necessariamente observadas no mundo real. Em particular, no mundo real, as pessoas não nascem com aleatoriedade uniforme. Este link possui estatísticas para os dias em que as pessoas nascem. Embora nosso modelo não seja um reflexo preciso do mundo real, sua simplicidade facilita muito a análise do problema.

Devo dizer que, se houver 366 ou mais pessoas em uma sala, é garantido que haja duas pessoas com o mesmo aniversário. Isso decorre do princípio de Dirichlet (o “princípio de pombos e caixas”): se houver 366 pessoas e 365 dias, pelo menos duas pessoas deverão ter o mesmo aniversário.

Imagine que há uma pessoa na sala, então a probabilidade de seu aniversário comum com outra pessoa é 0. Deixe $$$(A_n)$ será o resultado em que entre $$$n$ as pessoas não têm um único aniversário. Vamos $$$\ Pr [A_n]$ - a probabilidade de que entre $$$n$ das pessoas na sala, todo mundo faz aniversário no dia. Da mesma forma, vamos $$$\ overline {A_n}$ será complemento $$$A_n$ , ou seja, um resultado em que entre $$$n$ pessoas duas pessoas têm o mesmo aniversário.

$$

$$\ Pr [A_n] + \ Pr [\ overline {A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \ text {porque existe apenas uma pessoa na sala}$$

Suponha que haja duas pessoas na sala, A e B. Sem perda de generalização, imagine que a pessoa A nasceu em 1º de janeiro. Para B e A terem aniversários diferentes, B precisa nascer em qualquer dia, exceto em 1º de janeiro. A pessoa B terá 364 opções de aniversário.

$$

$$\ Pr [A_2] = \ Pr [\ text {B é diferente de A}] = \ frac {364} {365}$$

Imagine que há três pessoas na sala, A, B e C. Suponha que a pessoa A tenha nascido em 1º de janeiro, para que todas tenham nascido em dias diferentes, a pessoa B tenha apenas 364 dias, como no exemplo anterior. Como A e B levam dois dias, a pessoa C só pode nascer aos 365 - 2 = 363 dias.

$$

$$\ Pr [A_3] = \ Pr [\ text {B é diferente A e C é diferente de B, A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

Algo mais interessante acontece aqui: suponha que a sala já tenha $$$k - 1$ pessoas. Quando ele entra na sala $$$k$ essa pessoa $$$k$ pessoas tiveram aniversários diferentes, dois resultados devem ser verdadeiros

1. Todos $$$k - 1$ as pessoas que entraram na sala antes dele deveriam ter aniversários diferentes. Qual é a probabilidade disso? $$$\ Pr [A_ {k-1}]$ .
2. $$$k$ - essa pessoa precisa ter um aniversário diferente de todos os outros $$$k - 1$ pessoas na sala. Qual é a probabilidade disso? $$$\ frac {365 - (k-1)} {365}$ .

Note-se também que os dois resultados apresentados acima são independentes um do outro, porque, pelo pressuposto (4) feito no início do post, $$$k$ A segunda pessoa nasceu independentemente de todas as outras.

$$$$ display $$ \ begin {equação *} \ begin {split} \ Pr [A_k] e = \ Pr [k - 1 \ text {pessoas na sala têm diferentes aniversários} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ text {pessoa k tem aniversário diferente do} k - 1 \ text {pessoas}] \\ & = \ Pr [k - 1 \ text {pessoas na sala têm aniversários diferentes}] \\ & \ \ \ \ \ times \ Pr [\ text {pessoa k tem um aniversário diferente do} k - 1 \ text {people}] \\ & = \ Pr [A_ {k-1}] \ times \ frac { 365 - (k-1)} {365} \ end {split} \ end {equação *} $$ display $$

Agora calculamos as probabilidades:

$$exibição em $$ $$ \ begin {equação *} \ begin {split} \ Pr [A_1] & = 1 \\ \ Pr [A_2] e = \ Pr [A_1] \ times \ frac {364} {365} = \ frac {364} {365} \ aproximadamente 0,997 \\ \ Pr [A_3] & = \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \ aproximadamente 0,991 \\ \ Pr [A_4] e = \ Pr [A_3] \ times \ frac {362} {365} \ aproximadamente 0,983 \\ & \ vdots \\ \ Pr [A_ {22}] & = \ Pr [A_ {21}] \ times \ frac {344} {365} \ aprox 0,525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ times \ frac {343} {365 } \ aproximadamente 0,493 \\ \ end {divisão} \ end {equação *} $$ display $$

Desde que chegamos $$$\ Pr [A_ {23}] = 0,493 <0,5$ , isso significa que a probabilidade de um aniversário comum para duas pessoas é igual

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0,493 = 0,507> 0,5$$

Com aumento $$$n$ a probabilidade tende a 1 e a atinge.

Tarefa mais difícil

Suponha que desejemos generalizar esse problema para o caso em que houver $$$n$ pessoas e $$$m$ possíveis aniversários. Tendo $$$n, m$ , podemos determinar a probabilidade de duas pessoas terem um aniversário em comum?

Você pode usar o mesmo sistema: teremos um resultado $$$A_n$ denotando tudo $$$n$ pessoas nascidas em dias diferentes. No caso de uma pessoa, nada muda

$$

$$\ Pr [A_1] = 1$$

No caso de duas pessoas, designamo-las como A e B. Para a pessoa B nascer em outro dia, a pessoa B deve ter um aniversário entre $$$m - 1$ outras opções.

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

No caso de três pessoas, a pessoa B deve ter um aniversário diferente do aniversário de A. A pessoa C deve ter um dia diferente dos aniversários de A e B.

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ times \ frac {m-2} {m}$$

Geralmente para qualquer $$$n$ podemos usar a mesma fórmula recursiva que na seção anterior:

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m}$$

Suponha que, se queremos encontrar uma expressão de forma fechada para $$$\ Pr [A_n]$ , então decompomos a expressão

$$exibição $$ $$ \ begin {equação *} \ begin {split} \ Pr [A_n] & = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m} \ \ & = \ Pr [A_ {n-2}] \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ Pr [A_ {n-3}] \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n -1)} {m} \\ & \ \ vdots \\ & = \ Pr [A_2] \ times \ frac {m-2} {m} \ times \ frac {m-3} {m} \ times \ cdots \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1 - \ frac {i} {m} \\ & \ approx \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {usando a identidade} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ aprox e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {equação *} $$ display $$

Uma aproximação deste resultado é $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$ . Embora possamos encontrar limites mais aproximados, isso nos dá uma aproximação suficiente. A única identidade que usamos nesta aproximação:

$$

$$1 - x \ approx e ^ {- x}$$

Em sua forma abstrata, o paradoxo do aniversário tem muitos usos na computação. Em particular, é usado no hash, que por si só tem muitos usos. As conclusões feitas nesta tarefa são fundamentais para analisar a probabilidade de fazer o hash de dois elementos em uma chave. Esse problema pode ser generalizado para o problema probabilístico de bolas e bacias (problema de bolas e caixotes), que deixaremos para outro post.

Aplicação

O paradoxo do aniversário não é apenas uma tarefa artificial ou um truque interessante, tem muitas aplicações no mundo real. Pessoalmente, acredito que a análise probabilística usada na evidência é útil na análise de outras tarefas nas quais a randomização está envolvida. Em particular, isso se refere ao desenvolvimento de funções hash criptográficas. Veremos como a análise feita acima pode ser bastante útil na criação de funções de hash com proteção contra ataques de "aniversários".

Primeiro, vamos definir o que é uma função hash. Função hash $$$h: U \ rightarrow [0, m-1]$ É uma função que executa um mapeamento de um conjunto $$$U$ em um número no intervalo $$$[0, m-1]$ . Função $$$h$ definido como $$$h (x) = x \ mod m$ - função hash de exemplo de $$$\ mathbb {N} \ rightarrow [0, m-1]$ . As funções de hash têm muitos usos, especialmente em combinação com a estrutura de dados da tabela de hash popular. Também é usado em criptografia, onde é usado um tipo específico de função hash denominada "função hash criptográfica".

Uma das muitas propriedades que uma função hash criptográfica deve ter é a resistência à colisão. Deve ser difícil encontrar dois desses $$$u_1, u_2 \ em U$ para que eles colidam, ou seja, $$$h (u_1) = h (u_2)$ .

É sobre a resistência a colisões que focaremos. Primeiro, explicarei por que é uma propriedade desejável. Para fazer isso, primeiro consideraremos as assinaturas digitais.

No passado, pessoas e organizações usavam assinaturas e selos para "assinar" documentos. Recentemente, houve uma transição para assinaturas eletrônicas ou digitais. Uma assinatura digital deve satisfazer três propriedades básicas.

1. Ao assinar um documento, você precisa verificar quem assinou o documento.
2. Depois de assinar o documento, ninguém poderá falsificá-lo.
3. A pessoa que assinou o documento não pode posteriormente refutar a assinatura do documento.

Uma assinatura digital é uma maneira de verificar comprovadamente a verdade de um documento ou mensagem. Uma assinatura digital garante que a mensagem recebida foi criada por um remetente conhecido e não alterada.

Digamos que temos um documento $$$m$ . Como assinamos?

Cada usuário / organização possui uma chave privada exclusiva $$$p_k$ e chave pública $$$pub_k$ . Eles usam a função de assinatura para assinar um documento com sua própria chave privada. No entanto, uma assinatura digital pode assinar apenas um pequeno número de documentos. O escopo da função de assinatura é pequeno. Uma maneira de resolver esse problema é criar um documento menor que represente o documento original, mas em um tamanho muito menor. Na maioria das vezes, uma função de hash é aplicada a este documento grande. Uma função de hash é usada para mapeá-la de um espaço grande para outro menor, e o resultado dessa operação é chamado de "impressão digital". A assinatura usa a impressão digital e a chave privada para criar a assinatura. O procedimento pode ser descrito da seguinte maneira:

1. Obter a chave privada $$$p_k$ .
2. Hash de um documento $$$m$ e consiga $$$h (m)$ .
3. Assinar $$$h (m)$ usando a chave privada $$$p_k$ .
4. Nós enviamos $$ e chave pública $$$pub_k$ quem quiser confirmar o documento.

Quem tem $$ chave pública, pode verificar se o documento é realmente $$$m$ assinado pela pessoa certa.

Problema: suponha que o invasor Eva encontrou dois documentos $$$m, m '$ onde $$$m$ - este é o presente contrato, e $$$m '$ - um documento fraudulento que $$$h (m) = h (m ')$ . Suponha que Eva saiba com antecedência que Alice só assinará $$$m$ mas não $$$m '$ . Antes de assinar, uma função de hash criptográfico é aplicada ao documento $$$h$ . Eve vai até Alice e pede que ela assine um documento $$$m$ usando a sequência descrita acima. Agora, Eve pode alegar que Alice assinou um documento fraudulento $$$m '$ porque $$$h (m) = h (m ')$ . Alice não poderá provar de forma alguma que não assinou $$$m '$ .

No exemplo acima $$$h$ acabou por ser uma função resistente a colisões, portanto, Eve conseguiu encontrar dois conjuntos de dados recebidos com o mesmo valor. Eve foi capaz de afirmar que Alice assinou $$$m '$ embora de fato ela tenha assinado apenas $$$m$ . Isso enfatiza a importância da resistência à colisão e mostra por que as assinaturas digitais são vulneráveis ​​se a função hash é instável.

Vamos $$$h: U \ rightarrow [0, m-1]$ será uma função de hash. Suponha que os dados de entrada sejam distribuídos aleatoriamente de maneira uniforme e independente em qualquer um dos elementos $$$m$ .

A tarefa do ataque de "aniversário" é encontrar o menor número de elementos $$$n$ que pode ser misturado com $$$h$ para que possamos encontrar dois elementos $$$x, y \ em U$ em que $$$h (x) = h (y)$ .

Ao atacar "aniversários", o atacante pega aleatoriamente $$$x \ em U$ e manter casais $$$(x, h (x))$ . Um atacante seleciona e salva repetidamente esses pares até encontrar dois valores $$$x, y$ em que $$$h (x) = h (y)$ . Precisamos determinar quantas vezes o atacante precisa repetir essa operação até encontrar uma colisão.

Para analisar o ataque de "aniversários", você pode usar os mesmos princípios que usamos para o paradoxo do aniversário. No ataque "aniversários" $$$m$ denota o número de dias em um ano e $$$U$ semelhante a pessoas que entram em uma sala. As pessoas fazem hash nos aniversários, o que pode ser um dos significados. $$$m$ . Digamos que precisamos encontrar uma colisão com uma probabilidade de 99%. Precisamos saber qual é o menor $$$n$ , em que o hash de dois valores será um aniversário (no mundo das funções de hash, isso significa que dois conjuntos de dados de entrada são divididos em hash no mesmo valor).

Mostramos anteriormente que $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$

Nós queremos perguntar $$$\ Pr [\ overline {A} _n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ isso é $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$exibição $$ $$ \ begin {equação *} \ begin {split} e ^ {\ frac {-n ^ 2} {2m}} & = \ frac {1} {100} \\ \ frac {n ^ 2} {2m} & = \ ln 100 \\ n ^ 2 & = 2 m \ ln 100 \\ n & = \ sqrt {2 m \ ln 100} \ end {split} \ end {equação *} $$ display $$

A análise mostrada acima nos diz que para obter colisões em funções hash com um intervalo de tamanho $$$m$ um invasor precisa fazer o hash de maneira uniforme e independente, aproximadamente $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ para uma garantia quase completa (probabilidade de 99%) de que dois elementos são hash no mesmo valor.

Suponha que desejemos obter uma colisão com uma probabilidade de 50%; então precisamos $$$n = \ sqrt {2 m \ ln 2}$ . A conclusão importante aqui é que, para obter uma colisão com uma probabilidade superior a 0,5, precisamos fazer o hash da ordem $$$\ sqrt {m}$ elementos. Isso é consistente com nossa análise anterior para $$$m = 365$ porque $$$\ sqrt {2 \ ln 2 \ cdot 365}$ aproximadamente igual a 23.

Tarefas adicionais

1. Tendo $$$n$ de pessoas $$$m$ dias e um certo número $$$k$ encontre a probabilidade de que exatamente $$$k$ as pessoas têm o mesmo aniversário.
2. Vamos transformar um pouco a tarefa acima. Digamos que temos $$$m$ dias e um certo número $$$k$ . Qual será o menor valor $$$n$ em que não menos $$$k$ as pessoas terão o mesmo aniversário com uma probabilidade de pelo menos 0,5? Você pode generalizar esta tarefa com qualquer probabilidade $$$p> 0$ ?
3. Suponha que temos 100 números de 1 a 100, bem como uma máquina que adivinha um número aleatório de 1 a 100 em uma ordem uniforme e aleatória. Quantas vezes precisaremos usar a máquina conforme o esperado, para que ela adivinhe todos os números de 1 a 100?
4. Você pode generalizar esta tarefa para qualquer $$$n$ ?
5. Suponha que tenhamos uma função hash que exibe aleatoriamente uniformemente elementos em uma região de memória. Deixe áreas totais $$$m$ . Quantos itens $$$n$ precisamos adicionar expectativa matemática à nossa estrutura de dados para que pelo menos dois elementos sejam divididos em hash em cada região?