Estimando n no problema do coletor de cupom

Em uma variação do problema do coletor de cupons , você não sabe o número de cupons e deve determinar isso com base nos dados. Vou me referir a isso como o problema do biscoito da sorte:

Dado um número desconhecido de mensagens distintas sobre cookies da sorte , estime amostrando os cookies um de cada vez e contando quantas vezes cada fortuna aparece. Determine também o número de amostras necessárias para obter um intervalo de confiança desejado nessa estimativa.$n$$n$

Basicamente, preciso de um algoritmo que faça a amostragem de dados suficientes para atingir um determinado intervalo de confiança, digamos com confiança. Por uma questão de simplicidade, podemos assumir que todas as fortunas aparecem com igual probabilidade / frequência, mas isso não é verdade para um problema mais geral e uma solução para isso também é bem-vinda.$n \pm 5$$95\%$

Isso parece semelhante ao problema do tanque alemão , mas, neste caso, os biscoitos da sorte não são rotulados sequencialmente e, portanto, não têm pedidos.

Para o caso de igual probabilidade / frequência, essa abordagem pode funcionar para você.

Seja o tamanho total da amostra, N o número de itens diferentes observados, N 1 o número de itens vistos exatamente uma vez, N 2 o número de itens vistos exatamente duas vezes, A = N 1 ( 1 - N $K$$N$$N_1$$N_2$e Q =N$A=N_1(1− {N_1 \over K} )+2N_2,$$\hat Q = {N_1 \over K}.$

Então, um intervalo aproximado de 95% de confiança no tamanho total da população é dado por$n$

$$\hat n_{Lower}={1 \over {1-\hat Q+{1.96 \sqrt{A} \over K} }}$$

$$\hat n_{Upper}={1 \over {1-\hat Q-{1.96 \sqrt{A} \over K} }}$$

Ao implementar, pode ser necessário ajustá-los, dependendo dos seus dados.

O método é devido a Good e Turing. Uma referência com o intervalo de confiança é Esty, Warren W. (1983), "Uma lei de limite normal para um estimador não paramétrico da cobertura de uma amostra aleatória" , Ann. Statist. , Volume 11, Número 3, 905-912.

Para o problema mais geral, a Bunge produziu software livre que produz várias estimativas. Pesquise com o nome dele e a palavra CatchAll .

Não sei se isso pode ajudar, mas é o problema de pegar bolas diferentes durante n testes em uma urna com m bolas rotuladas diferentemente com a substituição. De acordo com esta página (em francês), se X n se a variável aleatória contar o número de bolas diferentes, a função de probabilidade é dada por: P ( X n = k ) = ($k$$n$$m$$X_n$$P(X_n = k) = {m \choose k} \sum_{i=0}^k {(-1)^{k-i}{k \choose i}}{(\frac{i}{m})^n}$

Em seguida, você pode usar um estimador de probabilidade máxima.

Outra fórmula com prova é dada aqui para resolver o problema de ocupação .

Função de probabilidade e probabilidade

Em uma resposta a uma pergunta sobre o problema do aniversário reverso, Cody Maughan deu uma solução para uma função de probabilidade.

A função de probabilidade para o número de tipos de fortuna cozinha $m$ quando desenhamos $k$ biscoitos da sorte diferentes em $n$ sorteios (onde cada tipo de biscoito da sorte tem probabilidade igual de aparecer em um sorteio) pode ser expressa como:

$$\begin{array}{} \mathcal{L}(m \, \vert \, k,n ) = m^{-n} \frac{m!}{(m-k)!} \propto P(k \, \vert \, m,n) &=& m^{-n}\frac{m!}{(m-k)!} \cdot \underbrace{S(n,k)}_{\begin{subarray}{l}\text{Stirling number }\\ \text{of the 2nd kind}\end{subarray}}\\ &=& m^{-n}\frac{m!}{(m-k)!} \cdot \frac{1}{k!} \sum_{i=0}^k {(-1)^{i}{k \choose i}}{(k-i)^n} \\ &=& {{m}\choose{k}} \sum_{i=0}^k {(-1)^{i}{k \choose i}}{\left(\frac{k-i}{m}\right)^n} \end{array}$$

Para uma derivação da probabilidade no lado direito, consulte o problema de ocupação. Isso já foi descrito anteriormente neste site por Ben. A expressão é semelhante à da resposta de Sylvain.

Estimativa de máxima verossimilhança

Podemos calcular aproximações de primeira e segunda ordem do máximo da função de verossimilhança em

$$m_1 \approx \frac{ {{n}\choose{2}}}{n-k}$$

$$m_2 \approx \frac{ {{n}\choose{2}} + \sqrt{{{n}\choose{2}}^2 - 4(n-k) {{n}\choose{3}}}}{2(n-k)}$$

Intervalo de probabilidade

(observe, isso não é o mesmo que um intervalo de confiança, consulte: A lógica básica da construção de um intervalo de confiança )

Isso continua sendo um problema em aberto para mim. Ainda não tenho certeza de como lidar com a expressão $m^{-n} \frac{m!}{(m-k)!}$(é claro que é possível calcular todos os valores e selecionar os limites com base nisso, mas seria mais agradável ter alguma fórmula ou estimativa exata explícita). Não consigo relacioná-lo com nenhuma outra distribuição que ajudaria muito a avaliá-lo. Mas sinto que uma expressão agradável (simples) poderia ser possível a partir dessa abordagem de intervalo de probabilidade.

Intervalo de confiança

Para o intervalo de confiança, podemos usar uma aproximação normal. Na resposta de Ben, são dadas as seguintes médias e variações:

$$\mathbb{E}[K] = m \left(1-\left(1 - \frac{1}{m}\right)^n\right)$$ $$\mathbb{V}[K] = m \left(\left(m-1\right)\left(1-\frac{2}{m}\right)^n + \left(1 - \frac{1}{m}\right)^n - m \left(1 - \frac{1}{m}\right)^{2n} \right)$$

Digamos para uma determinada amostra $n=200$ e observamos cookies únicos $k$ os limites de 95% $\mathbb{E}[K] \pm 1.96 \sqrt{\mathbb{V}[K]}$ parece com:

$m$$n$

$k$

$P(k \, \vert \, m,n)$Strlng2

# function to compute Probability
library("CryptRndTest")
P5 <- function(m,n,k) {
  exp(-n*log(m)+lfactorial(m)-lfactorial(m-k)+Strlng2(n,k))
}
P5 <- Vectorize(P5)

# function for expected value 
m4 <- function(m,n) {
  m*(1-(1-1/m)^n)
}

# function for variance
v4 <- function(m,n) {
  m*((m-1)*(1-2/m)^n+(1-1/m)^n-m*(1-1/m)^(2*n))
}


# compute 95% boundaries based on Pearson Clopper intervals
# first a distribution is computed
# then the 2.5% and 97.5% boundaries of the cumulative values are located
simDist <- function(m,n,p=0.05) {
  k <- 1:min(n,m)
  dist <- P5(m,n,k)
  dist[is.na(dist)] <- 0
  dist[dist == Inf] <- 0
  c(max(which(cumsum(dist)<p/2))+1,
       min(which(cumsum(dist)>1-p/2))-1)
}


# some values for the example
n <- 200
m <- 1:5000
k <- 1:n

# compute the Pearon Clopper intervals
res <- sapply(m, FUN = function(x) {simDist(x,n)})


# plot the maximum likelihood estimate
plot(m4(m,n),m,
     log="", ylab="estimated population size m", xlab = "observed uniques k",
     xlim =c(1,200),ylim =c(1,5000),
     pch=21,col=1,bg=1,cex=0.7, type = "l", yaxt = "n")
axis(2, at = c(0,2500,5000))

# add lines for confidence intervals based on normal approximation
lines(m4(m,n)+1.96*sqrt(v4(m,n)),m, lty=2)
lines(m4(m,n)-1.96*sqrt(v4(m,n)),m, lty=2)
# add lines for conficence intervals based on Clopper Pearson
lines(res[1,],m,col=3,lty=2)
lines(res[2,],m,col=3,lty=2)

# add legend
legend(0,5100,
       c("MLE","95% interval\n(Normal Approximation)\n","95% interval\n(Clopper-Pearson)\n")
       , lty=c(1,2,2), col=c(1,1,3),cex=0.7,
       box.col = rgb(0,0,0,0))