Cómo estimar el número de artículos en Wikipedia usando el "artículo al azar" de la función?

Question

Hay una Wikipedia-tipo de sitio web de un tamaño fijo de $S$ número de artículos. Iniciar en cualquier artículo en la Wikipedia. Tienes que pulsar la tecla "artículo al azar" botón y contar el número de veces $N$ que se necesita para generar aleatoriamente la página original de nuevo.

El objetivo es encontrar la mejor estimación de $S$ sólo el número de $N$.

Suponga que el "artículo al azar" función genera cualquier artículo en particular con un uniforme de la probabilidad y de que cada clic es un (EDICIÓN independiente) evento aleatorio. La página que usted comience en no cuenta como un clic y por lo tanto no se cuentan en $N$.

Este problema me recuerda a una de las soluciones a la locomotora problema y el tanque alemán problema. Desde que se pulsa el botón N veces, el caso con el mayor número de artículos que tiene todas las páginas N ser diferentes páginas, dando una estimación de (creo) $2N+1$. Esto significaría que la mejor estimación sería de menos de $2N+1$, porque siempre es posible para $N$ a contener un artículo, distinta a la que estabas buscando, para ser repetido varias veces.

Otra posible solución está basada en el método de captura y recaptura para estimar el tamaño de las poblaciones de animales silvestres. Este método proporciona la estimación como $S=N$. Esto sería debido a que de $N$ de las muestras tomadas durante la "reconquista", exactamente $1/N$ de ellos son artículos vistos durante la "marca" de la fase (artículo original que se recuerda). Desde $1/N$ de las páginas son conocidos para ser recogidos por el grupo de una página en particular, entonces el cálculo sería que no sería $N$ páginas en total.

Answer 1

Si $S$ es el número total de artículos, la probabilidad de observar $N$ es $$\frac{(S-1)^{N-1}}{S^N}.$$

Debemos elegir una estimación de $S$ que maximiza esta probabilidad. La diferenciación de da $$\frac{(N-1)(S-1)^{N-2} S^N - N S^{N-1} (S-1)^{N-1}}{S^{2N}} = (S-1)^{N-2} \frac{(N-1)S - N (S-1)}{S^{N+1}}$$

que es igual a $0$ al $S = 1$ e al $S = N$; el primero es un mínimo local y el segundo es un máximo local, por lo que, de hecho, $S = N$ es una buena estimación.

---

Sin embargo, si usted realmente va a tratar de hacer esto, creo que la espera hasta el primer artículo se repite es una mala idea. Usted tiene que esperar mucho y en el ínterin que no estás usando la información acerca de cualquier otro artículo que pueda haber repetido. Como Ross dice en los comentarios otra idea es esperar hasta que algún artículo se repite. Si $S$ es el número total de artículos, la probabilidad de observar $N$ es ahora $$P(S) = \frac{(S-1)(S-2)\cdots(S-N+1)N}{S^N} = \frac{N(S-1)!}{S^N (S-N)!}.$$

Stirling aproximación da $$P(S) \approx C_N \frac{ (S-1)^{S-1} }{S^N (S-N)^{S-N} }$$

donde $C_N$ es una constante que depende sólo de $N$. Tomando logaritmos da $$\log P(S) \approx \log C_N + (S-1) \log (S-1) - N \log S - (S-N) \log (S-N)$$

y tomando derivados da $$\frac{P'(S)}{P(S)} \approx 1 + \log (S-1) - \frac{N}{S} - 1 - \log (S-N).$$

Un máximo local debe producirse, por tanto, al $\log (S-1) - \log (S-N) \cong \frac{N}{S}$, o cuando $$1 + \frac{N-1}{S-N} \approx e^{ \frac{N}{S} } \approx 1 + \frac{N}{S}$$

dando a $S(N-1) \approx N(S-N)$ o $S \approx N^2$. Así como Ross indica que es mucho más eficiente para la obtención de una estimación.

Answer 2

Es el primer mejor para averiguar la distribución utilizada por el artículo al azar del generador. Para un sitio de gran tamaño, tales como Wikipedia, no me sorprendería escuchar que una más eficiente computacionalmente generador aleatorio se utiliza en lugar de una justa distribución uniforme.

Para comprobar su respuesta, WikiCount.net da una buena aproximación al número de artículos de la Wikipedia en inglés, el uso de un interpolados polinomio a partir de los datos publicados con la actualización de los coeficientes.