Supongamos que tengo un regular, grafo, no bipartito, finito, gráfica conectada en $N$ vértices. Algunos fracción de $\frac{c}{N}$ de los vértices son de color oro, el resto son de color negro. Si me permiten realizar una caminata al azar en el gráfico, ¿qué mecanismos existen para que usted descubra lo que el valor de $c$ es?
Respuesta
¿Demasiados anuncios?
No sé cómo lo práctico que es este, pero en teoría empírica de la proporción de visitas a sitios oro se converge casi seguramente a la verdadera proporción. Que es, como $n\to\infty$ tenemos $${1\over n}\sum_{k=1}^n 1\lbrace X(k)\mbox{ is gold }\rbrace\to {c\over N}.$$
Esto se mantiene incluso si el grafo es bipartito. El requisito importante es la conexión, de tal forma que la cadena es irreducible.
Añadió: La calidad de esta estimación es considerablemente más difícil, y más interesante problema. En la Sección 12.6 (especialmente la ecuación (12.27)) de las Cadenas de Markov y los Tiempos de Mezcla por Levin, Peres, y Wilmer (disponible gratuitamente en http://pages.uoregon.edu/dlevin/MARKOV/)
Los autores sugieren una quemadura en el tiempo, es decir, tirar la primera $r$ observaciones. La quemadura-en el tiempo $r$ y el número de $t$ de observaciones adicionales para obtener una buena estimación depende de la eigenstructure de la matriz de transición. Estos dependerán en gran medida de la forma y la geometría de la gráfica.
Véase también la sección 6.3 de las cadenas de Markov: Gibbs campos, la simulación de Monte Carlo, y las colas por Pierre Brémaud, donde se calcula la varianza asintótica del estimador.
