Estendendo o paradoxo do aniversário para mais de 2 pessoas

29

No Paradoxo tradicional do aniversário, a pergunta é "quais são as chances de duas ou mais pessoas em um grupo de pessoas compartilharem um aniversário". Estou preso em um problema que é uma extensão disso.n

Em vez de saber a probabilidade de duas pessoas compartilharem um aniversário, preciso estender a pergunta para saber qual é a probabilidade de ou mais pessoas compartilharem um aniversário. Com você pode fazer isso calculando a probabilidade de duas pessoas não compartilharem um aniversário e subtraí-lo de , mas acho que não posso estender essa lógica para números maiores de .xx=21x

Para complicar ainda mais isso, também preciso de uma solução que funcione para números muito grandes para (milhões) e (milhares).nx

Simon Andrews
fonte
11
Eu presumo que é bioinformática problema
csgillespie
3
Na verdade, é um problema de bioinformática, mas como ele se resume ao mesmo conceito do paradoxo do aniversário, pensei em salvar os detalhes irrelevantes!
Simon Andrews
4
Normalmente, eu concordo com você, mas nesse caso os detalhes podem ser importantes, pois já pode haver um pacote de biocondutores que faz o que você pede.
precisa saber é o seguinte
Se você realmente quer saber, é um problema de localização de padrões em que estou tentando estimar com precisão a probabilidade de um determinado nível de enriquecimento de uma subsequência dentro de um conjunto de seqüências maiores. Portanto, tenho um conjunto de subsequências com contagens associadas e sei quantas subsequências observei e quantas seqüências teoricamente observáveis ​​estão disponíveis. Se eu vi uma sequência específica 10 vezes em 10.000 observações, preciso saber qual a probabilidade de ter ocorrido por acaso.
Simon Andrews
Quase oito anos depois, postei uma resposta para esse problema em stats.stackexchange.com/questions/333471 . O código não funciona para grande entanto, porque leva tempo quadrático em . n,n
whuber

Respostas:

17

Esse é um problema de contagem: existem possíveis atribuições de aniversários para pessoas. Dessas, seja o número de atribuições para as quais nenhum aniversário é compartilhado por mais de pessoas, mas pelo menos um aniversário é realmente compartilhado por pessoas. A probabilidade que procuramos pode ser encontrada somando para valores apropriados de e multiplicando o resultado por . b n q ( k ; n , b ) k k q ( k ; n , b ) k b - nbnbnq(k;n,b)kkq(k;n,b)kbn

Essas contagens podem ser encontradas exatamente para valores de inferiores a várias centenas. No entanto, eles não seguirão nenhuma fórmula direta: precisamos considerar os padrões de maneiras pelas quais os aniversários podem ser atribuídos . Ilustrarei isso em vez de fornecer uma demonstração geral. Seja (esta é a menor situação interessante). As possibilidades são:n = 4nn=4

  • Cada pessoa tem um aniversário único; o código é {4}.
  • Exatamente duas pessoas compartilham um aniversário; o código é {2,1}.
  • Duas pessoas têm um aniversário e as outras duas têm outro; o código é {0,2}.
  • Três pessoas compartilham um aniversário; o código é {1,0,1}.
  • Quatro pessoas compartilham um aniversário; o código é {0,0,0,1}.

Geralmente, o código é uma tupla de contagens cujo elemento estipula quantas datas de nascimento distintas são compartilhadas por exatamente pessoas. Assim, em particular,k th k{a[1],a[2],}kthk

1a[1]+2a[2]+...+ka[k]+=n.

Observe, mesmo neste caso simples, que existem duas maneiras pelas quais é atingido o máximo de duas pessoas por aniversário: uma com o código e outra com o código .{ 2 , 1 }{0,2}{2,1}

Podemos contar diretamente o número possível de atribuições de aniversário correspondentes a qualquer código. Este número é o produto de três termos. Um é um coeficiente multinomial; conta o número de maneiras de particionar pessoas em grupo de , grupo de e assim por diante. Como a sequência de grupos não importa, temos que dividir esse coeficiente multinomial por ; seu recíproco é o segundo termo. Por fim, alinhe os grupos e atribua a cada um aniversário: há candidatos para o primeiro grupo,a [ 1 ] 1 a [ 2 ] 2 a [ 1 ] ! a [ 2 ]na[1]1a[2]2b b - 1 b ( a [ 1 ] + a [ 2 ] + ) b ( m ) b ( b - 1 ) ( b - m + 1 )a[1]!a[2]!bb1para o segundo e assim por diante. Esses valores devem ser multiplicados juntos, formando o terceiro termo. É igual ao "produto fatorial" onde significa .b(a[1]+a[2]+)b(m)b(b1)(bm+1)

Existe uma recursão óbvia e bastante simples relacionando a contagem de um padrão à contagem do padrão . Isso permite o cálculo rápido das contagens para valores modestos de . Especificamente, representa as datas de nascimento de compartilhadas por exatamente pessoas cada. Depois que esses grupos de pessoas foram retirados das pessoas, o que pode ser feito de maneiras distintas (digamos), resta contar o número de maneiras de alcançar o padrão{ a [ 1 ] , , a [ k - 1 ] } n{a[1],,a[k]}{a[1],,a[k1]}na [ k ] k um [ k ] k n X { um [ 1 ] , ... , um [ k - 1 ] } xa[k]a[k]ka[k]knx{a[1],,a[k1]}entre as pessoas restantes. Multiplicar por fornece a recursão.x

Duvido que exista uma fórmula de forma fechada para , que é obtida somando as contagens para todas as partições de cujo termo máximo é igual a . Deixe-me oferecer alguns exemplos:n kq(k;n,b)nk

Com (cinco possíveis aniversários) (quatro pessoas), obtemosn = 4b=5n=4

q(1)=q(1;4,5)=120q(2)=360+60=420q(3)=80q(4)=5.

Daí, por exemplo, a chance de três ou mais pessoas em quatro compartilharem o mesmo "aniversário" (em datas possíveis) é igual a .( 80 + 5 ) / 625 = 0,1365(80+5)/625=0.136

Como outro exemplo, tomar e . Aqui estão os valores de para o menor (até seis sig figs):b=365n=23q(k;23,365)k

k=1:0.49270k=2:0.494592k=3:0.0125308k=4:0.000172844k=5:1.80449E6k=6:1.48722E8k=7:9.92255E11k=8:5.45195E13.

Usando essa técnica, podemos calcular prontamente que há cerca de 50% de chance de (pelo menos) uma colisão de três anos entre 87 pessoas, 50% de chance de uma colisão de quatro vias entre 187 e 50% de chance de uma colisão de cinco vias entre 310 pessoas. Esse último cálculo começa a demorar alguns segundos (no Mathematica, pelo menos) porque o número de partições a considerar começa a aumentar. Para substancialmente maior , precisamos de uma aproximação.n

Uma aproximação é obtida por meio da distribuição de Poisson com expectativa , porque podemos ver uma atribuição de aniversário como decorrente de variáveis ​​Poisson quase (mas não completamente) independentes, cada uma com expectativa : a variável para qualquer aniversário possível descreve quantas das pessoas têm esse aniversário. A distribuição do máximo é, portanto, aproximadamente onde é o CDF de Poisson. Este não é um argumento rigoroso, então vamos fazer um pequeno teste. A aproximação para , fornecen/bbn/bnF(k)bFn=23b=365

k=1:0.498783k=2:0.496803k=3:0.014187k=4:0.000225115.

Comparando com o anterior, você pode ver que as probabilidades relativas podem ser ruins quando são pequenas, mas as probabilidades absolutas são razoavelmente bem aproximadas de cerca de 0,5%. Testar com uma ampla gama de e sugere que a aproximação geralmente é sobre esse bem.nb

Para finalizar, vamos considerar a pergunta original: pegue (o número de observações) (o número possível de "estruturas", aproximadamente). A distribuição aproximada para o número máximo de "aniversários compartilhados" én=10,000b=1000000

k=1:0k=2:0.8475+k=3:0.1520+k=4:0.0004+k>4:<1E6.

(Este é um cálculo rápido.) Claramente, observar uma estrutura 10 vezes em 10.000 seria altamente significativo. Como e são grandes, espero que a aproximação funcione muito bem aqui.nb

Aliás, como Shane sugeriu, as simulações podem fornecer verificações úteis. Uma simulação do Mathematica é criada com uma função como

simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];

que é iterado e resumido, como neste exemplo, que executa 10.000 iterações do caso , :n=10000b=1000000

Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm

Sua saída é

2 8503

3 1493

4 4

Essas frequências concordam estreitamente com as previstas pela aproximação de Poisson.

whuber
fonte
Que resposta fantástica, muito obrigado @whuber.
JKnight 21/08
"Existe uma recursão óbvia e bastante simples" - Ou seja?
Kodiologist 14/10
11
@ Kodiologist Inseri uma breve descrição da idéia.
whuber
+1, mas onde na pergunta original você viu que n = 10000 eb = 1mln? Parece que o OP está perguntando sobre n = 1mln ek = 10000, com b não especificado (presumivelmente b = 365). Não que isso importe neste momento :)
ameba diz Reinstate Monica
11
@amoeba Depois de todo esse tempo (seis anos, 1600 respostas e lendo atentamente dezenas de milhares de posts) não consigo me lembrar, mas provavelmente interpretei mal a última linha. Em minha defesa, observe que, se a lermos literalmente, a resposta é imediata (ao aplicar uma versão do Princípio do Buraco de Pombo): é certo que entre = milhões de pessoas haverá pelo menos um aniversário que é compartilhado entre pelo menos = milhares deles! xnx
whuber
2

Sempre é possível resolver esse problema com uma solução monte-carlo, embora isso esteja longe de ser o mais eficiente. Aqui está um exemplo simples do problema de duas pessoas no R (de uma apresentação que fiz no ano passado ; usei isso como um exemplo de código ineficiente), que pode ser facilmente ajustado para dar conta de mais de 2:

birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}
Shane
fonte
Não tenho certeza se a solução de vários tipos funcionará aqui.
Eu acho que a generalização ainda funciona apenas para 2 ou mais pessoas que compartilham um aniversário - apenas que você pode ter diferentes subclasses de pessoas.
Simon Andrews
1

Esta é uma tentativa de uma solução geral. Pode haver alguns erros, portanto, use com cuidado!

Primeiro alguma notação:

P(x,n) é a probabilidade de que ou mais pessoas compartilhem um aniversário entre pessoas,xn

P(y|n) é a probabilidade de exatamente pessoas compartilharem um aniversário entre pessoas.yn

Notas:

  1. O abuso de notação como Está sendo usado de duas maneiras diferentes.P(.)

  2. Por definição, não pode assumir o valor de 1, pois não faz sentido e = 0 pode ser interpretado como significando que ninguém compartilha um aniversário em comum.yy

A probabilidade requerida é dada por:

P(x,n)=1P(0|n)P(2|n)P(3|n)....P(x1|n)

Agora,

P(y|n)=(ny)(365365)y k=1k=ny(1k365)

Aqui está a lógica: você precisa da probabilidade de exatamente compartilhar um aniversário.y

Etapa 1: você pode escolher people de .( ny(ny)

Etapa 2: como eles compartilham um aniversário, pode ser um dos 365 dias em um ano. Então, basicamente temos 365 opções que nos dão .(365365)y

Passo 3: Os restantes as pessoas não devem compartilhar um aniversário com os primeiros pessoas ou com o outro. Esse raciocínio nos fornece .y k = n - y k = 1 ( 1 - knyyk=1k=ny(1k365)

Você pode verificar se, para = 2, o item anterior se reduz à solução padrão de paradoxo de aniversário.x


fonte
Essa solução sofrerá com a maldição da dimensionalidade? Se, em vez de n = 365, n = 10 ^ 6, essa solução ainda é viável?
precisa saber é o seguinte
Algumas aproximações podem ter que ser usadas para lidar com altas dimensões. Talvez, use a aproximação de Stirling para fatoriais no coeficiente binomial. Para lidar com os termos do produto, você pode pegar logs e calcular as somas em vez dos produtos e, em seguida, pegar o anti-log da soma.
Existem também várias outras formas de aproximações possíveis, usando, por exemplo, a expansão da série Taylor para a função exponencial. Veja a página wiki para estas aproximações: en.wikipedia.org/wiki/Birthday_problem#Approximations
Suponha que y = 2, n = 4 e haja apenas dois aniversários. Sua fórmula, adaptada substituindo 365 por 2, parece dizer que a probabilidade de exatamente duas pessoas compartilharem um aniversário é Comb (4,2) * (2/2) ^ 2 * (1-1 / 2) * (1-2 / 2) = 0. (Na verdade, é fácil ver - por enumeração de força bruta, se quiser - que as probabilidades de 2, 3 ou 4 pessoas compartilharem um "aniversário" sejam 16/06, 16/08, e 2/16, respectivamente.) De fato, sempre que ny> = 365, sua fórmula gera 0, enquanto que n aumenta e ey é fixo, a probabilidade deve aumentar para um máximo diferente de zero antes de n atingir 365 * y e depois diminuir, mas nunca abaixo de 0.
whuber
Por que você está substituindo 365 por ? A probabilidade de duas pessoas compartilharem um aniversário é calculada como: 1 - Prob (eles têm aniversário exclusivo). Prob (que eles tenham aniversário único) = (364/365). A lógica é a seguinte: Escolha uma pessoa. Essa pessoa pode ter qualquer dia dos 365 dias como aniversário. A segunda pessoa só pode fazer aniversário em um dos 364 dias restantes. Assim, a probabilidade de que eles tenham um aniversário único é 364/365. Não sei como você está calculando 16/06. n