Esta é uma generalização do famoso Problema do Aniversário : dado indivíduos que têm "aniversários" aleatórios e uniformemente distribuídos entre um conjunto de possibilidades, qual é a chance de nenhum aniversário ser compartilhado por mais de indivíduos?d = 6 m = 20n=100d=6m=20
Um cálculo exato fornece a resposta (para dobrar a precisão). Vou esboçar a teoria e fornecer o código para geral O tempo assintótico do código é que o torna adequado para um número muito grande de aniversários e fornece um desempenho razoável até que esteja na casa dos milhares. Nesse ponto, a aproximação de Poisson discutida em Estendendo o paradoxo do aniversário para mais de duas pessoas deve funcionar bem na maioria dos casos.n , m , d . O ( n 2 log ( d ) ) d n0.267747907805267n,m,d.O(n2log(d))dn
Explicação da solução
A função geradora de probabilidade (pgf) para os resultados de rolos independentes de um dado com face édnd
d−nfn(x1,x2,…,xd)=d−n(x1+x2+⋯+xd)n.
O coeficiente de na expansão desse multinomial fornece o número de maneiras pelas quais posso aparecer exatamente vezes, i e i i = 1 , 2 , ... , d .xe11xe22⋯xeddieii=1,2,…,d.
Limitar nosso interesse a não mais que aparências por qualquer face é o mesmo que avaliar modulo o ideal gerado por Para executar esta avaliação, use o Teorema Binomial recursivamente para obterf n I x m + 1 1 , x m + 1 2 , … , x m + 1 d .mfnIxm+11,xm+12,…,xm+1d.
fn(x1,…,xd)=((x1+⋯+xr)+(xr+1+xr+2+⋯+x2r))n=∑k=0n(nk)(x1+⋯+xr)k(xr+1+⋯+x2r)n−k=∑k=0n(nk)fk(x1,…,xr)fn−k(xr+1,…,x2r)
quando é par. Escrevendo ( terms), temosd=2rf(d)n=fn(1,1,…,1)d
f(2r)n=∑k=0n(nk)f(r)kf(r)n−k.(a)
Quando é ímpar, use uma decomposição análogad=2r+1
fn(x1,…,xd)=((x1+⋯+x2r)+x2r+1)n=∑k=0n(nk)fk(x1,…,x2r)fn−k(x2r+1),
dando
f(2r+1)n=∑k=0n(nk)f(2r)kf(1)n−k.(b)
Nos dois casos, também podemos reduzir tudo o módulo , que é facilmente realizado começando comI
fn(xj)≅{xn0n≤mn>mmodI,
fornecendo os valores iniciais para a recursão,
f(1)n={10n≤mn>m
O que torna isso eficiente é que, dividindo as variáveis em dois grupos de tamanho igual de variáveis cada e definindo todos os valores das variáveis como precisamos avaliar tudo apenas uma vez para um grupo e depois combinar os resultados. Isso exige a computação de até termos, cada um deles precisando de cálculo de para a combinação. Nem precisamos de uma matriz 2D para armazenar , porque ao calcular apenas e são necessários.dr1,n+1O(n)f(r)nf(d)n,f(r)nf(1)n
O número total de etapas é um a menos que o número de dígitos na expansão binária de (que conta as divisões em grupos iguais na fórmula ) mais o número de unidades na expansão (que conta todas as vezes um número ímpar é encontrado um valor, exigindo a aplicação da fórmula ). Isso ainda é apenas etapas.d(a)(b)O(log(d))
Em R
uma estação de trabalho de uma década, o trabalho foi realizado em 0,007 segundos. O código está listado no final desta postagem. Ele usa logaritmos das probabilidades, em vez das próprias probabilidades, para evitar possíveis estouros ou acumular muito subfluxo. Isso torna possível remover o fator na solução, para que possamos calcular as contagens subjacentes às probabilidades.d−n
Observe que esse procedimento resulta no cálculo de toda a sequência de probabilidades uma só vez, o que facilmente nos permite estudar como as chances mudam com .f0,f1,…,fnn
Formulários
A distribuição no Problema Generalizado de Aniversário é calculada pela função tmultinom.full
. O único desafio está em encontrar um limite superior para o número de pessoas que devem estar presentes antes que a chance de uma colisão se torne muito grande. O código a seguir faz isso com força bruta, começando com pequeno e dobrando-o até que seja grande o suficiente. Portanto, todo o cálculo leva tempo em que é a solução. Toda a distribuição de probabilidades para o número de pessoas até é calculada.m+1nO(n2log(n)log(d))nn
#
# The birthday problem: find the number of people where the chance of
# a collision of `m+1` birthdays first exceeds `alpha`.
#
birthday <- function(m=1, d=365, alpha=0.50) {
n <- 8
while((p <- tmultinom.full(n, m, d))[n] > alpha) n <- n * 2
return(p)
}
Como exemplo, o número mínimo de pessoas necessárias em uma multidão para tornar mais provável que pelo menos oito delas compartilhem um aniversário é , conforme encontrado pelo cálculo . Demora apenas alguns segundos. Aqui está um gráfico de parte da saída:798birthday(7)
Uma versão especial desse problema é abordada em Estendendo o paradoxo do aniversário para mais de duas pessoas , que diz respeito ao caso de um dado de lados que é rolado muitas vezes.365
Código
# Compute the chance that in `n` independent rolls of a `d`-sided die,
# no side appears more than `m` times.
#
tmultinom <- function(n, m, d, count=FALSE) tmultinom.full(n, m, d, count)[n+1]
#
# Compute the chances that in 0, 1, 2, ..., `n` independent rolls of a
# `d`-sided die, no side appears more than `m` times.
#
tmultinom.full <- function(n, m, d, count=FALSE) {
if (n < 0) return(numeric(0))
one <- rep(1.0, n+1); names(one) <- 0:n
if (d <= 0 || m >= n) return(one)
if(count) log.p <- 0 else log.p <- -log(d)
f <- function(n, m, d) { # The recursive solution
if (d==1) return(one) # Base case
r <- floor(d/2)
x <- double(f(n, m, r), m) # Combine two equal values
if (2*r < d) x <- combine(x, one, m) # Treat odd `d`
return(x)
}
one <- c(log.p*(0:m), rep(-Inf, n-m)) # Reduction modulo x^(m+1)
double <- function(x, m) combine(x, x, m)
combine <- function(x, y, m) { # The Binomial Theorem
z <- sapply(1:length(x), function(n) { # Need all powers 0..n
z <- x[1:n] + lchoose(n-1, 1:n-1) + y[n:1]
z.max <- max(z)
log(sum(exp(z - z.max), na.rm=TRUE)) + z.max
})
return(z)
}
x <- exp(f(n, m, d)); names(x) <- 0:n
return(x)
}
A resposta é obtida com
print(tmultinom(100,20,6), digits=15)
0.267747907805267
Cálculo da força bruta
Esse código leva alguns segundos no meu laptop
saída: 0.2677479
Ainda assim, pode ser interessante encontrar um método mais direto, caso você deseje fazer muitos desses cálculos ou usar valores mais altos, ou apenas para obter um método mais elegante.
Pelo menos esse cálculo fornece um número calculado de maneira simplista, mas válida, para verificar outros métodos (mais complicados).
fonte