MATEMÁTICA E AS TECNOLOGIAS DA INFORMAÇÃO: Os aniversariantes e a desigualdade

Os aniversariantes e a desigualdade $(1- x ) < e^{(-x)}$

Problema do aniversário : considere k pessoas numa sala. Qual a probabilidade de que, pelo menos duas pessoas, faça aniversário no mesmo dia e mês ? Qual é o valor mínimo de k, para qie este evento ocorra com probabilidade maior que 1/2.

A probabilidade é dada por :

$P(365,k)= 1- \frac{365!}{(365-k)!365^k}$

(Bussab e Moretin, 127p).

Generalização : Considere uma variável aleatória a valor inteiro com distribuição uniforme entre 1 e n, e uma seleção de k ocorrências da variável aleatória, com k ≤ n. Qual a probabilidade P(n,k) de que ocorra pelo menos uma duplicata ? Qual o valor mínimo de k para que este evento ocorra, com probabilidade maior que 1/2 ? Este problema é o do aniversário com n = 365.Assim, podemos escrever :

$P(n,k)= 1- \frac{n!}{(n-k)!n^k}$

(troque 365 por n na anterior)

Temos:

$P(n,k)= 1- \frac{n(n-1)(n-2)...(n-k+1)}{n^k}$

$P(n,k)=1-\frac{n}{n}\frac{(n-1)}{n}\frac{(n-2)}{n}...\frac{(n-k+1)}{n}$

Logo,

$P(n,k)=1-(1-\frac{1}{n})(1-\frac{2}{n})...(1-\frac{k-1}{n})$

A presença da desiguldade :

$(1-\frac{1}{n})\le e^{\frac{-1}{n}};(1-\frac{2}{n})\le e^{\frac{-2}{n}};...;(1-\frac{k-1}{n})\le e^{\frac{-(k-1)}{n}}$

Assim,

$P(n,k)> 1- e^{\frac{-1}{n}}e^{\frac{-2}{n}}...e^{\frac{-(k-1)}{n}}= 1-e^{-[\frac{1}{n}+\frac{2}{n}+...+\frac{(k-1)}{n}]}$

Mas,

$\frac{1}{n}+\frac{2}{n}+...+\frac{(k-1)}{n}}& = & \frac{k(k-1)}{2n}$

De forma que ,

$P(n,k) > 1-e^{-\frac{-k(k-1)}{2n}}$

O valor de k:

Queremos k mínimo tal que :

$P(n,k) \leq \dfrac{1}{2}$

Logo, escrevemos :

$\frac{1}{2}= 1-e^{-\frac{k(k-1)}{2n}}\Leftrightarrow 2= 1-e^{-\frac{k(k-1)}{2n}}\Leftrightarrow {2}= 1-e^{-\frac{k(k-1)}{2n}}\Leftrightarrow$

$\Leftrightarrow ln(2)=\frac{k(k-1)}{2n}\cong \frac{k^2}{2n}$

Para k grande.

Finalmente,

$k =\sqrt{(2n)ln(2)} = 1,18\sqrt{n} \approx \sqrt{n}$

Para o problema do aniversário, temos :

$n = 365 \Rightarrow k = 1,18\sqrt{365} = 22,54$

Logo, k = 23 e FELIZ ANIVERSÁRIO!

O irmão computacional : O problema também este versão : considere uma função F, com 2^m possíveis saídas (saída de m bits). Se aplicarmos F a k entradas aleatórias, qual o valor de k para que haja pelo menos uma duplicata, isto é, F(x)=F(y) para algumas entradas x e y com probabilidade maior que ½ ?

Neste caso :

$k =1,18\sqrt{2^{m}} = 1,18 x 2^{\frac{m}{2}}$