5 votos

¿De un proceso discreto deterministico a una cadena de Markov: condiciones?

Cuando se probabilística se obtiene por un proceso de "abstracción" de un determinista discretos proceso satisface la propiedad de Markov?

Ejemplo #1) Supongamos que tenemos algunos de recurrencia, por ejemplo,, $a_t=a^2_{t-1}$, $t>0$. Es un proceso determinista. Sin embargo, si hacemos una "abstracción" por sólo teniendo en cuenta la particular dígitos de cada una de las $a_t$, tenemos un proceso probabilístico. Nos preguntamos si se satisface una propiedad de Markov o no?

Ejemplo #2) Supongamos que tenemos un autómata de estado finito. Ahora hacemos una "abstracción" mediante la agrupación de los estados a los conjuntos de los estados y de la obtención de un probabilístico autómata de estado finito. Consideramos que este autómata en el tiempo y nos preguntamos si satisface la propiedad de Markov o no.

Los ejemplos en particular no son importantes, de interés son algunas de las condiciones generales cuando un determinista proceso se convierte en un proceso de Markov después de una "abstracción" de la clase anterior (en cualquier contexto). Estoy buscando cualquier referencia en esta materia.


Edit: como se señaló en los comentarios de abajo, los ejemplos #1 y #2 no fueron bien especificado. Ahora hay una distribución en el estado inicial $a_0$ $a_t=f(a_{t-1})$ es una función determinista. Entonces, $a_t$, $t\geq 0$ es un degenerado de la cadena de Markov. Ahora la pregunta es si la agrupación de algunos de los estados de una cadena puede producir una cadena de Markov (es decir, los punteros a la literatura donde las condiciones serían discutidos es necesario).

Un problema más general parece ser "Dado cualquier cadena de Markov (es decir, no un degenerado uno), del grupo de los estados en grupos: ¿cuáles son las condiciones en el proceso resultante satisface la asunción de Markov?"

3voto

Did Puntos 1

Al parecer, los dos ejemplos que encajan en la siguiente configuración. Uno comienza a partir de un (determinista) sistema dinámico definido por $a_0\in A$ $a_{t+1}=u(a_t)$ para cada entero no negativo $t$, para una función determinada,$u:A\to A$, y se considera el $X$valores de proceso $(x_t)_{t\geqslant0}$ definido por $x_t=\xi(a_t)$ para cada entero no negativo $t$, para una función determinada,$\xi:A\to X$.

Para todos los fijos $a_0$, $(x_t)_{t\geqslant0}$ es determinista, por lo tanto $(x_t)_{t\geqslant0}$ es un (bastante degenerada) inhomogenous de la cadena de Markov cuya transición en el tiempo $t$ es el kernel $Q_t$ tal que $Q_t(x,y)=P(x_{t+1}=y\mid x_t=x)$ no está definido para cada $x\ne\xi(a_t)$ $\delta_y(\xi(a_{t+1}))$ si $x=\xi(a_t)$.

Una manera de conseguir realmente un proceso aleatorio $(x_t)_{t\geqslant0}$ en esta opción es elegir un distribuidas aleatoriamente $a_0$. Pero entonces no hay motivo para esperar que $(x_t)_{t\geqslant0}$ no ser una cadena de Markov y, de hecho, la construcción de arriba es un modo clásico para codificar procesos aleatorios con una dependencia compleja estructura.

Un ejemplo que podría ayudarle a conseguir una sensación de lo que está sucediendo es el caso cuando $A=\mathbb R$, $u(a)=a+\frac15$ para cada $a\in A$, $a_0$ distribuidos de manera uniforme en $(0,1)$, e $\xi:\mathbb R\to\mathbb N$ la función parte entera. A continuación, $x_{t+1}\in\{x_t,x_t+1\}$ con total probabilidad, sino $(x_t)_{t\geqslant0}$ no está de Markov. Sin embargo, $x_{t+1}$ es una función determinista de $(x_{t},x_{t-1},x_{t-2},x_{t-3},x_{t-4})$ (o algo similar) por lo tanto $(x_t)_{t\geqslant0}$ es un (degenerado) de la quinta de Markov de orden de proceso.


Editar Una función de prevención de $(x_t)_{t\geqslant0}$ de Markov en el ejemplo anterior es la existencia de puntos de $a$ $a'\ne a$ $A$ visitado por el proceso de $(a_t)_{t\geqslant0}$ tal que $\xi(a)=\xi(a')$ pero $\xi(u(a))\ne\xi(u(a'))$. Esto es una reminiscencia de la condición de una ocultos de la cadena de Markov a ser una cadena de Markov, que se lee como sigue.

Suponga que $(a_t)_{t\geqslant0}$ es una cadena de Markov con la transición del kernel $q$ y deje $(x_t)_{t\geqslant0}$ denotar el proceso definido por $x_t=\xi(a_t)$ por cada positivo $t$. A continuación, $(x_t)_{t\geqslant0}$ es una cadena de Markov para cada partida distribución de $a_0$ si y sólo si la suma $$ q_\xi(a,y)=\sum\limits_{b\in A}p(a,b)\cdot[\xi(b)=y] $$ depende de a $a$ sólo a través de la $x=\xi(a)$, es decir, si y sólo si $q_\xi(a,y)=Q(x,y)$ para una función determinada,$Q$. Cuando esta condición, llamada lumpability, sostiene, la cadena de Markov $(a_t)_{t\geqslant0}$ se dice que lumpable (por la función $\xi:A\to X$) y $Q$ es la transición del núcleo de la cadena de Markov $(x_t)_{t\geqslant0}$.

La pregunta para saber si $(x_t)_{t\geqslant0}$ es una cadena de Markov para una determinada distribución inicial de $a_0$ es más complicado, pero una condición para que esto se sostenga como se indica aquí.


Segunda edición Aquí es un ejemplo en el continuo de espacio de estado que muestra que la distribución inicial es importante.

Deje $A=\mathbb R/\mathbb Z$ denotar el círculo unidad, $u:A\to A$ definido por $u(a)=2a$, $X=\{0,1\}$, $\xi:A\to X$ definido por $\xi(a)=[a\in A_1]$ donde $A_1=(\mathbb Z+[\frac12,1))/\mathbb Z$, e $a_{t+1}=u(a_t)$ $x_t=\xi(a_t)$ por cada positivo $t$. Entonces, si la distribución de los $a_0$ es uniforme en $A$, el proceso de $(x_t)_{t\geqslant0}$ es una cadena de Markov, ya que es de hecho yo.yo.d. con $x_t$ uniforme en $X$ por cada $t$.

Esta es una adaptación del ejemplo basado en la logística de ruta presentada en estas notas por Cosma Shalizi, que va como sigue.

Vamos $B=[0,1]$, $v:B\to B$ definido por $v(b)=4b(1-b)$, $\eta:B\to X$ definido por $\eta(b)=[b\in B_1]$ donde $B_1=[\frac12,1]$, e $b_{t+1}=v(b_t)$ $y_t=\eta(b_t)$ por cada positivo $t$. Entonces, si la distribución de los $b_0$ es el arcoseno de distribución, con la densidad $1/(\pi\sqrt{b(1-b)})$$B$, el proceso de $(y_t)_{t\geqslant0}$ es una cadena de Markov, ya que es de hecho yo.yo.d. con $y_t$ uniforme en $X$ por cada $t$. Shalizi notas que $(y_t)_{t\geqslant0}$ es una cadena de Markov con respecto a su propia filtración, ya que las distribuciones de $y_{t+1}$ condicionalmente en $(y_s)_{s\leqslant t}$ o condicionalmente en $y_t$ son los mismos (y ambos son la distribución uniforme en $X$). Por otro lado, la distribución de $y_{t+1}$ condicionalmente en $(b_s)_{s\leqslant t}$ es la medida de Dirac en $+1$ o a $0$ desde $y_{t+1}$ es una función determinista de $b_t$. Más precisamente, este condicional de distribución es la de Dirac medida en $\eta(v(b_t))$.

Por último, los ejemplos basados en $u$ $v$ son conjugado desde $v\circ \sigma=\sigma\circ u$ $\sigma:A\to B$ definido por $\sigma(a)=\sin^2(\pi a)$. Tenga en cuenta que, si $a_0$ es uniforme en $A$, $\sigma(a_0)$ sigue el arcoseno de distribución en $B$.

1voto

goric Puntos 5230

Como @Did señala, usted quiere saber cuando se "junten" conserva la propiedad de Markov. Ver el lema 2.5 en cadenas de Markov y tiempos de mezcla por Levin, Peres y Wilmer. El libro está disponible en línea aquí.

0voto

MiDiMaN Puntos 81

La respuesta simple es: cada proceso determinístico discreto es ya un proceso de Markov. Las "probabilidades" de que se trate están restringidas sólo a ser 0 o 1.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X