La constante de Kemeny

En teoría de la probabilidad , la constante de Kemeny es el número esperado de pasos de tiempo necesarios para que una cadena de Markov pase de un estado inicial i a un estado de destino aleatorio muestreado de la distribución estacionaria de la cadena de Markov. Sorprendentemente, esta cantidad no depende de qué estado inicial i se elija. ^[1] En ese sentido, es una constante, aunque es diferente para diferentes cadenas de Markov. Cuando John Kemeny publicó por primera vez en 1960, se ofreció un premio a quien diera una explicación intuitiva de por qué la cantidad era constante. ^{[2] [3]}

Definición

Para una cadena de Markov ergódica finita ^[4] con matriz de transición P y distribución invariante π , escriba m _ij para el tiempo medio de primer paso del estado i al estado j (que denota el tiempo medio de recurrencia para el caso i  =  j ). Luego

${\displaystyle K=\sum _{j}\pi _{j}m_{ij}}$

es una constante y no depende de i . ^[5]

Premio

Kemeny escribió, (para i el estado inicial de la cadena de Markov) “Se ofrece un premio a la primera persona que dé una razón intuitivamente plausible de que la suma anterior sea independiente de  i ”. ^[2] Grinstead y Snell ofrecen una explicación de Peter Doyle como ejercicio, con la solución “¡lo consiguió!” ^{[6] [7]}

En el transcurso de un paseo con Snell por la avenida Minnehaha en Minneapolis en el otoño de 1983, Peter Doyle sugirió la siguiente explicación para la constancia de la constante de Kemeny. Elija un estado objetivo de acuerdo con el vector fijo w . Comience desde el estado i y espere hasta el momento T en que el estado objetivo ocurra por primera vez. Sea K _i el valor esperado de T . Observe que

${\displaystyle K_{i}+w_{i}\cdot 1/w_{i}=\sum _{j}P_{ij}K_{j}+1}$

y por lo tanto

${\displaystyle K_{i}=\sum _{j}P_{ij}K_{j}.}$

Por el principio del máximo , K _i es una constante. ¿Debería haberle dado el premio a Peter?

Referencias

1. Crisostomi, E.; Kirkland, S.; Shorten, R. (2011). "Un modelo similar a Google de la dinámica de la red vial y su aplicación a la regulación y el control". Revista Internacional de Control . 84 (3): 633. doi :10.1080/00207179.2011.568005.
2. Kemeny, JG ; Snell, JL (1960). Cadenas finitas de Markov . Princeton, Nueva Jersey: D. Van Nostrand.(Corolario 4.3.6)
3. Catral, M.; Kirkland, SJ; Neumann, M.; Sze, N.-S. (2010). "La constante de Kemeny para cadenas de Markov ergódicas homogéneas finitas" (PDF) . Revista de informática científica . 45 (1–3): 151–166. CiteSeerX 10.1.1.295.9600 . doi :10.1007/s10915-010-9382-1. 
4. Levene, Mark; Loizou, George (2002). "La constante de Kemeny y el surfista aleatorio" (PDF) . The American Mathematical Monthly . 109 (8): 741–745. CiteSeerX 10.1.1.305.937 . doi :10.2307/3072398. JSTOR  3072398. 
5. Hunter, Jeffrey J. (2012). "El papel de la constante de Kemeny en las propiedades de las cadenas de Markov". Comunicaciones en estadística: teoría y métodos . 43 (7): 1309–1321. arXiv : 1208.4716 . doi :10.1080/03610926.2012.741742.
6. Grinstead, Charles M.; Snell, J. Laurie. Introducción a la probabilidad (PDF) .
7. "Dos ejercicios sobre la constante de Kemeny" (PDF) . Archivado desde el original el 31 de enero de 2024. Consultado el 1 de marzo de 2013 .{{cite web}}: CS1 maint: URL no apta ( enlace )