Epónimos relacionados con las matemáticas

cadena de Cunningham es una sucesión de números primos (p₁,...,p_n) en la cual se cumple:

1. que cada término es igual al doble del anterior más uno (p_i+1 = 2 p_i + 1 para todo i con 1 ≤ i < n), en cuyo caso se denomina cadena de Cunningham de primera especie;
2. o bien que cada término es igual al doble del anterior menos uno (p_i+1 = 2 p_i - 1 para todo i con 1 ≤ i < n), en cuyo caso se denomina cadena de Cunningham de segunda especie.

Se denominan así en honor al matemático A. J. C. Cunningham.

En una cadena de Cunningham de primera especie, todos los términos menos el último son primos de Sophie Germain, y todos menos el primero son números primos seguros.

Una cadena de Cunningham se dice completa si no se puede extender más allá, es decir, si el término siguiente y el anterior ya no son números primos.

A veces el concepto de cadena de Cunningham se extiende a las llamadas cadenas generalizadas de Cunningham, que se definen como sucesiones de números primos (p₁,...,p_n) tales que para todo i con 1 ≤ i < n, p_i+1 = ap_i + b para dos enteros coprimos dados a y b.

Cadenas de Cunningham más largas

Una consecuencia de la conjetura de Dickson y la más general hipótesis H de Schinzel (ambas supuestas ciertas¹ ) es que para todo k existen infinitas cadenas de Cunningham de longitud k (es decir, con k términos). Sin embargo, no se conocen métodos directos para generar dichas cadenas.

A fecha de julio de 2008, la cadena de Cunningham más larga que se conoce es de segunda especie, de longitud 17 y su primer término es 1302312696655394336638441. La cadena de Cunningham más larga que se conoce de primera especie tiene longitud 13 y su primer término es 1753286498051×71# − 1, donde 71# es el primorial de 71: 2×3×5×7×...×71.

Propiedades derivadas de las congruencias

Cadenas de Cunningham de primera especie

Sea ${\displaystyle p_{1}}$ un número primo distinto de 2 que es el primer término de una cadena de Cunningham de primera especie. El primer término es impar, es decir, ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$. Como cada uno de los siguientes términos de la sucesión cumple ${\displaystyle p_{i+1}=2p_{i}+1}$, se tiene que ${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}}$. Así, ${\displaystyle p_{2}\equiv 3{\pmod {4}}}$, ${\displaystyle p_{3}\equiv 7{\pmod {8}}}$, etc.

Esta propiedad se puede comprobar de manera informal si se consideran los términos de una cadena en base 2. (Nótese que, como ocurre con cualquier base, si se multiplica un número por la base del sistema de numeración empleado para su representación, las cifras se desplazan un lugar a la izquierda.) Si se considera ${\displaystyle p_{i+1}=2p_{i}+1}$ en base 2, se puede ver que, al multiplicar ${\displaystyle p_{i}}$ por 2, la cifra menos significativa de ${\displaystyle p_{i}}$ pasa a ser la segunda cifra menos significativa de ${\displaystyle p_{i+1}}$. Como ${\displaystyle p_{i}}$ es impar, es decir, la cifra menos significativa es 1 en base 2, se sigue que la segunda cifra menos significativa de ${\displaystyle p_{i+1}}$ también es 1. Además, ${\displaystyle p_{i+1}}$ también es impar porque se le añade 1 a ${\displaystyle 2p_{i}}$. De esta manera, los sucesivos términos de una cadena de Cunningham de primera especie son el resultado de desplazar el anterior un lugar a la izquierda en binario y poner un uno como última cifra. He aquí, a modo de ejemplo, una cadena completa de longitud 6 que empieza con el número 141361469:

Binario	Decimal
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

En base decimal, se tiene que los términos de una cadena completa de Cunningham de primera especie de longitud mayor o igual que 4 acaban todos en 9 (en lenguaje matemático, ${\displaystyle p_{i}\equiv 9{\pmod {10}}}$ para cada i) exceptuando el caso ${\displaystyle p_{i}=2}$. Esto se puede considerar fácilmente comprobando los términos siguientes de uno dado acabado en 1, 3, 7 o 9, y considerando que un número entero acabado en 5, exceptuando el propio 5, debe ser compuesto:

• ${\displaystyle p_{0}\equiv 5{\pmod {10}}}$ -> ${\displaystyle p_{1}\equiv 1{\pmod {10}}}$ -> ${\displaystyle p_{2}\equiv 3{\pmod {10}}}$ ${\displaystyle p_{3}\equiv 7{\pmod {10}}}$ ${\displaystyle p_{4}\equiv 5{\pmod {10}}}$. ${\displaystyle p_{0}}$ y ${\displaystyle p_{4}}$ acaban en 5, por tanto, en general no pueden ser primos, y la consecuencia es que:
  • una cadena con ${\displaystyle p_{1}\equiv 1{\pmod {10}}}$ tiene longitud a lo sumo 3
  • una cadena con ${\displaystyle p_{1}\equiv 3{\pmod {10}}}$ tiene longitud 2
  • no existen cadenas de Cunningham cuyo primer término sea de la forma ${\displaystyle p_{1}\equiv 7{\pmod {10}}}$
• ${\displaystyle p_{1}\equiv 9{\pmod {10}}}$ -> ${\displaystyle p_{2}\equiv 9{\pmod {10}}}$, por tanto, todos los siguientes términos acabarán en 9.

Cadenas de Cunningham de segunda especie

Las propiedades de estas cadenas son análogas a las de la primera especie. Sabiendo que ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$, así como la relación ${\displaystyle p_{i+1}=2p_{i}-1}$, se sigue que ${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$. En notación binaria, los términos de una cadena de Cunningham de la segunda especie acabarán en "0...01", y cada término tendrá un cero más que el anterior antes del uno. Y en notación binaria se puede demostrar análogamente que los términos de las cadenas de longitud 4 o más acaban todos en 1.

Sólo el 2 y el 3 pertenecen a cadenas de Cunningham de primera y segunda especie

Las propiedades descritas anteriormente se pueden generalizar para otras bases de numeración. En particular, se puede demostrar que un mismo número no puede formar parte a la vez de una cadena de Cunningham de la primera especie de una de la segunda especie, con la excepción del 2 y el 3, si se considera la representación de los números en base 6. En esta base, los números primos sólo pueden acabar en 1 o 5, ya que, en los demás casos se obtiene un múltiplo de 2 o 3. Es fácil ver que los términos de una cadena de Cunningham de primera especie acaban en 5 con la única salvedad del 2 y el 3, y los términos de una cadena de segunda especie acaban en 1 con las mismas salvedades.

Estas son las excepciones:

• El 2 es el primer elemento de una cadena de primera especie de 5 elementos (2, 5, 11, 23 y 47) y el primero de una cadena de segunda especie de 3 elementos (2, 3, 5).
• El 3 es el primer elemento de una cadena de primera especie de 2 elementos (3 y 7) y el segundo de una cadena de segunda especie de 3 elementos (2, 3, 5).

La cadena de Ehrenfest, llamada así en honor al físico y matemático austriaco Paul Ehrenfest, es una cadena de Márkov en tiempo discreto usada para modelar el intercambio de moléculas de gas entre dos urnas.

Supongamos que tenemos dos urnas, ${\displaystyle C_{1}}$ y ${\displaystyle C_{2}}$. En ellas están distribuidas d bolas numeradas; en cada paso, se elige un número al azar entre {1,2,...,d}. A continuación se observa en qué urna está la bola con el número elegido y se cambia de urna.

Simulación de una Cadena de Ehrenfest con 20 bolas, distribución inicial 10-10 y 50 pasos.

Modelo

Sea ${\displaystyle X_{n}}$ la variable aleatoria que denota el número de bolas contenidas en la urna ${\displaystyle C_{1}}$ al tiempo n. El espacio de estados será entonces E={0,1,2,...,d} y la matriz de transición estará dada por:

${\displaystyle P_{x,y}={\begin{cases}x/d&{\mbox{si }}x>0,y=x-1\\(d-x)/d&{\mbox{si }}x$

Propiedades

Para la cadena de Ehrenfest:

• La cadena es irreducible.
• Todos sus estados son recurrentes.
• La cadena es positivo-recurrente (pues todos sus estados lo son).

Como consecuencia de las anteriores propiedades, resulta que la cadena tiene un único vector de probabilidad invariante para su matriz de transición y está dado por:

${\displaystyle \nu ={1 \over {2^{d}}}\left({\binom {d}{0}},{\binom {d}{1}},...,{\binom {d}{d}}\right)}$

cadena de Márkov o modelo de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior. Esta característica de falta de memoria recibe el nombre de propiedad de Markov.

Cadena simple biestable de Markov.

Recibe su nombre del matemático ruso Andréi Márkov (1856-1922), que lo introdujo en 1907.¹

Estos modelos estadísticos cuentan con un gran número de aplicaciones reales.

Definición formal

En matemática se define como un proceso estocástico discreto que cumple con la propiedad de Márkov, es decir, si se conoce la historia del sistema hasta su instante actual, su estado presente resume toda la información relevante para describir en probabilidad su estado futuro.

Una cadena de Márkov es una secuencia X₁, X₂, X₃,... de variables aleatorias. El dominio de estas variables es llamado espacio estado; el valor de X_n es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de X_n+1 en estados pasados es una función de X_n por sí sola, entonces:

${\displaystyle P(X_{n+1}=x_{n+1}|X_{n}=x_{n},X_{n-1}=x_{n-1},\ldots ,X_{2}=x_{2},X_{1}=x_{1})=P(X_{n+1}=x_{n+1}|X_{n}=x_{n}).\,}$

Donde x_i es el estado del proceso en el instante i. La identidad mostrada es la propiedad de Márkov.

Notación útil

Cadenas homogéneas y no homogéneas

• Una cadena de Márkov se dice homogénea si la probabilidad de ir del estado i al estado j en un paso no depende del tiempo en el que se encuentra la cadena, esto es:

${\displaystyle P(X_{n}=j|X_{n-1}=i)=P(X_{1}=j|X_{0}=i)\,}$ para todo n y para cualquier i, j.

Si para alguna pareja de estados y para algún tiempo n la propiedad antes mencionada no se cumple diremos que la cadena de Márkov es no homogénea.

Probabilidades de transición y matriz de transición

• La probabilidad de ir del estado i al estado j en n unidades de tiempo es

${\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,}$,

en la probabilidad de transición en un paso se omite el superíndice de modo que queda

${\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,}$

• Un hecho importante es que las probabilidades de transición en n pasos satisfacen la ecuación de Chapman-Kolmogórov, esto es, para cualquier k tal que 0 < k < n se cumple que

${\displaystyle p_{ij}^{(n)}=\sum _{r\in E}p_{ir}^{(k)}p_{rj}^{(n-k)}}$

donde E denota el espacio de estados.

• Cuando la cadena de Márkov es homogénea, muchas de sus propiedades útiles se pueden obtener a través de su matriz de transición, definida entrada a entrada como ${\displaystyle A_{i,j}=p_{ij}\,}$

esto es, la entrada i, j corresponde a la probabilidad de ir del estado i a j en un paso.

Del mismo modo se puede obtener la matriz de transición en n pasos como:

${\displaystyle A_{i,j}^{(n)}=P_{ij}^{(n)}}$, donde ${\displaystyle P_{ij}^{(n)}=P(X_{n}=j|X_{0}=i)}$.

Vector de probabilidad invariante

• Se define la distribución inicial ${\displaystyle \pi (x)=P(X_{0}=x)\,}$.

• Diremos que un vector de probabilidad (finito o infinito numerable) es invariante para una cadena de Márkov si

${\displaystyle \nu P=\nu \,}$

donde P denota la matriz de transición de la cadena de Márkov. Al vector de probabilidad invariante también se le llama distribución estacionaria o distribución de equilibrio.

Clases de comunicación

• Para dos estados i,j en el espacio de estados E, diremos que de i se accede a j (y se denotará ${\displaystyle i\rightarrow j}$) si

${\displaystyle p_{ij}^{(n)}>0\,}$ para algún n,

si ${\displaystyle i\rightarrow j}$ y ${\displaystyle j\rightarrow i}$ entonces diremos que i comunica con j y se denotará i↔j.

La propiedad "↔" es una relación de equivalencia. Esta relación induce una partición en el espacio de estados. A estas clases de equivalencia las llamaremos clases de comunicación.

Dado un estado x, denotaremos a su clase de comunicación como C(x).

• Diremos que un subconjunto C del espacio de estados (al que denotaremos E) es cerrado si ningún estado de E-C puede ser accedido desde un estado de C, es decir, si ${\displaystyle p_{x,y}^{(m)}=0}$ para todo x∈C, para todo y∈E-C y para todo natural m>0.

Tiempos de entrada

Si ${\displaystyle C\subset E}$, definimos el primer tiempo de entrada a C como la variable aleatoria

${\displaystyle T_{C}={\begin{cases}\min\{n>0|X_{n}\in C\}&{\mbox{si }}\{n>0|X_{n}\in C\}\neq \emptyset \\{\mathcal {1}}\,&{\mbox{si }}\{n>0|X_{n}\in C\}=\emptyset \end{cases}}}$

esto es, ${\displaystyle T_{C}\,}$ denota la primera vez que la cadena entra al conjunto de estados C.

Recurrencia

En una cadena de Márkov con espacio de estados E, si x∈E se define ${\displaystyle L_{x}=\mathbb {P} \,(X_{n}=x\ para\ algun\ n\in \mathbb {N} \,|X_{0}=x)}$ y diremos que:

• x es estado recurrente si ${\displaystyle L_{x}=1\,}$.
• x es transitorio si ${\displaystyle L_{x}<1 annotation="">$
• x es absorbente si ${\displaystyle p_{x,x}=1\,}$
• Una clase de comunicación es clase recurrente si todos sus estados son recurrentes.

Sea ${\displaystyle \mu _{x}=\mathbb {E} \,(T_{x}|X_{0}=x)}$, si x∈Ediremos que:

• x es cero-recurrente si ${\displaystyle \mu _{x}={\mathcal {1}}\,}$
• x es positivo-recurrente si ${\displaystyle \mu _{x}<{\mathcal {1}}\,}$

El real ${\displaystyle \mu _{x}}$ se interpreta como el tiempo promedio de recurrencia.

Periodicidad

• El periodo de un estado x∈E se define como:

${\displaystyle d(x)={\rm {mcd}}\{n:P_{x,x}^{(n)}>0\}}$

donde ${\displaystyle {\rm {mcd}}}$ denota el máximo común divisor.

• Si d(x)=1 diremos que x es un estado aperiódico.

• Una cadena de Márkov se dice aperiódica si todos sus estados son aperiódicos.

Tipos de cadenas de Márkov

Cadenas erráticas

Una cadena de Márkov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí):

1. Desde cualquier estado de E se puede acceder a cualquier otro.
2. Todos los estados se comunican entre sí.
3. C(x)=E para algún x∈E.
4. C(x)=E para todo x∈E.
5. El único conjunto cerrado es el total.

La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Márkov irreducibles.

Cadenas positivo-recurrentes

Una cadena de Márkov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

${\displaystyle \pi _{x}=1/\mu _{x}\,}$

Cadenas regulares

Una cadena de Márkov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero.

Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que:

${\displaystyle \lim _{n\to {\mathcal {1}}\,}P^{n}=W}$

donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector invariante es único.

Cadenas absorbentes

Una cadena de Márkov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes:

1. La cadena tiene al menos un estado absorbente.
2. De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:

• Su matriz de transición siempre se puede llevar a una de la forma

${\displaystyle P={\begin{pmatrix}Q&R\\0&I\end{pmatrix}}}$

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.

• ${\displaystyle P_{x}(T_{A}<{\mathcal {1}}\,)=1}$, esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.

Cadenas de Márkov en tiempo continuo

Si en lugar de considerar una secuencia discreta X₁, X₂,..., X_i,.. con i indexado en el conjunto ${\displaystyle \mathbb {N} \;\!}$ de números naturales, se consideran las variables aleatorias X_t con t que varía en un intervalo continuo del conjunto ${\displaystyle \mathbb {R} \;\!}$ de números reales, tendremos una cadena en tiempo continuo. Para este tipo de cadenas en tiempo continuo la propiedad de Márkov se expresa de la siguiente manera:

${\displaystyle P(X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n},\ldots ,X(t_{1})=x_{1})=P(X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n})}$ tal que ${\displaystyle t_{n+1}>t_{n}>t_{n-1}>\dots >t_{1}}$

Para una cadena de Márkov continua con un número finito de estados puede definirse una matriz estocástica dada por:

${\displaystyle \mathbf {P} (t_{1},t_{2})=[p_{ij}(t_{1},t_{2})]_{i,j=1,\dots ,N},\qquad p_{ij}(t_{1},t_{2})=P[X(t_{2})=j|X(t_{1})=i],\ 0\geq t_{1}$

La cadena se denomina homogénea si ${\displaystyle \mathbf {P} (t_{1},t_{2})=\mathbf {P} (t_{2}-t_{1})}$. Para una cadena de Márkov en tiempo continuo homogénea y con un número finito de estados puede definirse el llamado generador infinitesimal como:²

${\displaystyle \mathbf {Q} =\lim _{h\to 0^{+}}{\frac {\mathbf {P} (h)-\mathbf {I} }{h}}}$

Y puede demostrarse que la matriz estocástica viene dada por:

${\displaystyle \mathbf {P} (t)=e^{\mathbf {Q} t}=\sum _{n=0}^{\infty }{\frac {\mathbf {Q} ^{n}t^{n}}{n!}}}$

Aplicaciones

Meteorología

Si consideramos el tiempo atmosférico de una región a través de distintos días, es plausible asumir que el estado actual sólo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Márkov para formular modelos climatológicos básicos. Por ejemplo, se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Márkov.³

Modelos epidemiológicos

Una importante aplicación de las cadenas de Márkov se encuentra en el proceso Galton-Watson. Éste es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).

Internet

El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Márkov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena.

Simulación

Las cadenas de Márkov son utilizadas para proveer una solución analítica a ciertos problemas de simulación, por ejemplo en teoría de colas el Modelo M/M/1⁴ es de hecho un modelo de cadenas de Márkov.

Juegos de azar

Son muchos los juegos de azar que se pueden modelar a través de una cadena de Márkov. El modelo de la ruina del jugador, (Gambler's ruin), que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Márkov en este rubro.

Economía y finanzas

Las cadenas de Márkov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de los precios. En los negocios, las cadenas de Márkov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo.

Genética

Se emplean cadenas de Márkov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.

Música

Diversos algoritmos de composición musical usan cadenas de Márkov, por ejemplo el software Csound o Max

Operaciones

Se emplean cadenas de Márkov en inventarios, mantenimiento, flujo de proceso

Redes Neuronales

Se utilizan en las máquinas de Boltzmann (redes neuronales)