Memperkirakan n dalam masalah pengumpul kupon

Dalam variasi pada masalah pengumpul kupon , Anda tidak tahu jumlah kupon dan harus menentukan ini berdasarkan data. Saya akan menyebut ini sebagai masalah kue keberuntungan:

Mengingat jumlah yang tidak diketahui yang berbeda pesan kue keberuntungan $n$ , estimasi $n$ dengan sampling cookies satu per satu dan menghitung berapa kali masing-masing muncul keberuntungan. Tentukan juga jumlah sampel yang diperlukan untuk mendapatkan interval kepercayaan yang diinginkan pada perkiraan ini.

Pada dasarnya saya membutuhkan algoritma yang sampel data hanya cukup untuk mencapai interval kepercayaan tertentu, katakanlah $n \pm 5$ dengan kepercayaan $95\%$ . Untuk kesederhanaan, kita dapat mengasumsikan bahwa semua kekayaan muncul dengan probabilitas / frekuensi yang sama, tetapi ini tidak benar untuk masalah yang lebih umum, dan solusi untuk itu juga diterima.

Ini tampaknya mirip dengan masalah tank Jerman , tetapi dalam hal ini, kue keberuntungan tidak diberi label secara berurutan, dan karenanya tidak memiliki urutan.

Untuk kasus probabilitas / frekuensi yang sama, pendekatan ini mungkin cocok untuk Anda.

Misalkan adalah total ukuran sampel, N menjadi jumlah item yang berbeda yang diamati, N 1 menjadi jumlah item yang terlihat tepat satu kali, N 2 menjadi jumlah item yang terlihat tepat dua kali, A = N 1 ( 1 - N $K$$N$$N_1$$N_2$dan Q =N$A=N_1(1− {N_1 \over K} )+2N_2,$$\hat Q = {N_1 \over K}.$

Kemudian perkiraan interval kepercayaan 95% pada ukuran total populasi diberikan oleh$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} }}$$

Saat menerapkan, Anda mungkin perlu menyesuaikan ini tergantung pada data Anda.

Metode ini karena Good and Turing. Referensi dengan interval kepercayaan adalah Esty, Warren W. (1983), "Hukum Batas Normal untuk Estimator Nonparametrik dari Cakupan Sampel Acak" , Ann. Statist. , Volume 11, Nomor 3, 905-912.

Untuk masalah yang lebih umum, Bunge telah menghasilkan perangkat lunak gratis yang menghasilkan beberapa perkiraan. Cari dengan namanya dan kata CatchAll .

Saya tidak tahu apakah itu bisa membantu tetapi itu adalah masalah mengambil bola yang berbeda selama percobaan n di guci dengan bola m berlabel berbeda dengan penggantian. Menurut halaman ini (dalam bahasa Perancis) jika X n jika variabel acak menghitung jumlah bola yang berbeda fungsi probabilitas diberikan oleh: 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}$

Kemudian Anda bisa menggunakan penduga kemungkinan maksimum.

Formula lain dengan bukti diberikan di sini untuk menyelesaikan masalah hunian .

Fungsi kemungkinan dan probabilitas

Dalam jawaban atas pertanyaan tentang masalah ulang tahun terbalik, solusi untuk fungsi kemungkinan telah diberikan oleh Cody Maughan.

$m$$k$$n$

$$\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}$$

Untuk derivasi probabilitas di sisi kanan lihat masalah hunian. Ini telah dijelaskan sebelumnya di situs web ini oleh Ben. Ungkapannya mirip dengan yang di jawab oleh Sylvain.

Estimasi kemungkinan maksimum

Kita dapat menghitung perkiraan urutan pertama dan urutan kedua dari maksimum fungsi likelihood di

$$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)}$$

Interval kemungkinan

(catatan, ini tidak sama dengan interval kepercayaan lihat: Logika dasar membangun interval kepercayaan )

$m^{-n} \frac{m!}{(m-k)!}$

Interval kepercayaan diri

Untuk interval kepercayaan kita dapat menggunakan perkiraan normal. Dalam jawaban Ben, mean dan varians berikut diberikan:

$$\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)$$

$n=200$ and observed unique cookies $k$ the 95% boundaries $\mathbb{E}[K] \pm 1.96 \sqrt{\mathbb{V}[K]}$ look like:

In the image above the curves for the interval have been drawn by expressing the lines as a function of the population size $m$ and sample size $n$ (so the x-axis is the dependent variable in drawing these curves).

The difficulty is to inverse this and obtain the interval values for a given observed value $k$. It can be done computationally, but possibly there might be some more direct function.

In the image I have also added Clopper Pearson confidence intervals based on a direct computation of the cumulative distribution based on all the probabilities $P(k \, \vert \, m,n)$ (I did this in R where I needed to use the Strlng2 function from the CryptRndTest package which is an asymptotic approximation of the logarithm of the Stirling number of the second kind). You can see that the boundaries coincide reasonably well, so the normal approximation is performing well in this case.

# 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))