Contando cupones en una caja

Question

Tengo una pregunta con respecto a la cuenta. Yo vengo de un fondo en la computación cuántica, así que no estoy familiarizado con la literatura relevante aquí. Para el lector interesado, puedo proporcionar más detalles acerca de la computación cuántica, de fondo y cómo llegué a este problema.

El "conteo" pregunta a la que quiero resolver es: Supongamos que un cuadro de ha $N$ distintos cupones numerados $1,2,\dotsc,N$. Cada vez, me aleatoriamente un cupón de la caja, mira el número que aparece en el cupón, y, a continuación, poner de nuevo en la caja. Mi objetivo es estimar el número total $N$. Aproximadamente, ¿cuántas veces debo sorteo de un cupón de la caja y, a continuación, poner de nuevo, que tengo una razonablemente buena estimación de $N$ con un grado bastante alto de probabilidad? Si usted quiere ser riguroso, después de $M$ vueltas, ¿cuál es la probabilidad de $$P\left(\frac{|N_{\text{estimate}}-N|}{N} <\epsilon\right)?$$

Ahora, para el fondo: quantum annealers se utilizan para alcanzar el estado fundamental de un deseada de Hamilton. Quiero contar la cantidad de tierra de los estados del este de Hamilton. Hago esto varias veces la medición de la función de onda, que es como escoger al azar un cupón de un cuadro, como en el problema anterior. Tengo ideas para asegurarse de que cada cupón es recogida con igual probabilidad (denominada "feria de muestreo").

Answer 1

Yo sólo tendrá en cuenta el estimador de que tiene el número más grande que hemos visto hasta ahora. Como se ha mencionado en los comentarios, se podría considerar algo un poco más grande que este estimador, ya que sabemos que siempre subestima el máximo (por ejemplo, corregir el sesgo de este estimador). Que el estimador de que usted elija dependerá de su contexto (hacer incurrir en una grave pena si sobreestimar $N$?).

La probabilidad de que su suposición es $\le N-n$ (para $0 \le n \le N$) es la misma que la probabilidad de que usted nunca dibuje $N-n+1, N-n+2, \ldots, N$ en la $M$turnos. $$P(N_{est} \le N-n) = \left(1 - \frac{n}{N}\right)^M.$$ Reorganización de los rendimientos $$P\left(\frac{N - N_{est}}{N} \ge \frac{n}{N} \right) = \left(1 - \frac{n}{N}\right)^M.$$

Answer 2

Parece que mi pregunta está estrechamente relacionada con la captura y recaptura problema, como señala Ross Millikan: Supongamos que un bosque tiene una población $N$ de una especie animal, ¿cuántos animales debería de captura para la estimación de $N$? Las soluciones que va como sigue: En mi primera visita al campo, decir que la etiqueta de M individuos al azar. En mi segunda visita de campo, captura de M individuos al azar y se encuentra que k de estos ya han sido etiquetados. Entonces, puedo estimar el $\frac{k}{M} = \frac{M}{N} \Rightarrow N=\frac{M^2}{k}$. Para que esto funcione, $k\geq1 \Rightarrow M\geq\sqrt{N}$. Es decir, que se puede estimar $N$ mediante el etiquetado sólo $\sim\sqrt{N}$ de los individuos.

Esta es la respuesta que yo estaba buscando, y yo por separado obtenido la misma respuesta empleando una ruta indirecta. Es útil tener a mi intuición confirmado, sin embargo, resulta sorprendente que me puede estimar $N$ sólo en $\sim\sqrt{N}$ del tiempo.

Creo que tengo un mango en responder a la pregunta, "¿Cuál es la probabilidad de que esta estimación es la respuesta correcta con exactitud relativa $\epsilon$?". Muchas gracias a todos!