Fuente Markoviana

Publicado: 14 enero 2011 en 12 de Enero de 2011

Examinemos el siguiente caso:

Sea una fuente capaz de generar lenguaje en castellano. Ésta emitirá secuencias de letras bajo unas determinadas reglas sintácticas, que hacen que aparezcan situaciones como las siguientes:

– Si la última letra generada es, por ejemplo, una m, la probabilidad de que la siguiente sea, pongamos por caso, una r es casi nula, mientras que la de una a es bastante mayor: la combinación ma es, desde luego, mucho más frecuente en castellano que la mr.

– Supongamos ahora que la letra generada es una a. En este caso, la probabilidad de que se emita a continuación una r es mucho mayor que la de que se emita una a, que es casi nula (la combinación aa en castellano es, cuando menos, muy rara). Se tiene, entonces, que la probabilidad de emitir un símbolo depende de el/los anteriormente generados.

Es inmediato observar como el modelo de fuente de memoria nula, basado en la generación de símbolos estadísticamente independientes, no es capaz de adaptarse a situaciones como la descrita, es un modelo muy limitado. Se hace, por lo tanto, necesaria la introducción de un nuevo tipo de fuente de carácter más general.

Este nuevo tipo de fuente de información se la denomina de Markov, y se caracteriza porque la probabilidad de aparición de un determinado símbolo si, depende de cuales hayan sido los m anteriormente emitidos, donde m es el orden de la fuente. Una fuente de este tipo viene descrita, entonces, por:

• Su alfabeto: S={s1,s2,…,sq}

• El conjunto de probabilidades condicionales:

P(si / sj1,sj2,…,sjm) con i =1,2,…,q

jp=1,2,…,q

Donde si será el símbolo a generar, y sj1,sj2,…,sjm es la secuencia de los últimos m símbolos generados, siendo sjm el último de ellos, es decir, que si iría detrás de sjm.

Ejemplo

Un ejemplo de fuente de Markov de segundo orden sería:

– S={0,1}

– P(0/00)=0.8 P(1/00)=0.2

P(0/01)=0.5 P(1/01)=0.5

P(0/10)=0.5 P(1/10)=0.5

P(0/11)=0.2 P(1/11)=0.8

Cada posible combinación de las m últimas salidas, define un conjunto de probabilidades distinto sobre el siguiente símbolo a generar. Lo que tenemos, en definitiva, es que cada una de esas combinaciones define un estado diferente de la fuente, de manera que la emisión de un nuevo símbolo supone un cambio en dicho estado. Esto nos proporciona un método gráfico de describir una fuente de Markov: mediante su diagrama de estados. En él, se representa a cada estado por un círculo, y mediante flechas que los unen las transiciones entre ellos. A cada una de estas flechas se la asocia la salida de la fuente que produce la transición y la probabilidad de ocurrencia de ésta.

Referencia:
http://www.infor.uva.es/~cevp/FI_I/fichs_pdf_teo/FI_I_Tema3.pdf

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s