Resumen

Capítulo 2
Fuente de información discreta con memoria
La infomación a transmitir considera también los valores históricos originados con anterioridad.
Para este efecto, las técnicas a utilizar se basan en la teoría de Markov.
Consideremos una secuencia de variables estocásticas discretas u1, u2, u3,….. un-1
Estos pueden ser símbolos de una fuente, por ejemplo donde el primer término u 1relaciona a
todos los símbolos de un conjunto determinado.
En particular interesa determinar la distribución de probabilidad de un, el cual corresponde a una
cadena de Markov de orden k, y es dependiente de los valores de las variables estocásticas
precedentes desde u1 hasta uk-1.
La probabilidad condicional de un valor un está dado por todos los valores precedentes de orden k,
mediante el cualla probabilidad está dada por:
p(un/ un-k, un-k-1,……., un-1)
De esa forma, si definimos Si=( un-k, un-k-1,…, un), entonces Si se denomina el estado de la cadena de
Markov.
Si ahora el valor de un ocurre, entonces la cadena de Markov genera un nuevo estado
denominado Sj=( un-k-1, un-k-2,…, un).
En este caso se habla de una transición desde el estado S i al estado Sj. Esto puede sercaracterizado por una cadena de Markov, donde se forma una matriz de transiciones para los
diversos estados.
De esta forma, denotaremos que la probabilidad de la cadena de Markov desde el estado Si al
estado Sj por P(j/i).

Supongamos que se tienen 3 estados S1,S2 y S3 denotados por a,b y c respectivamente. De estos 3
estados, se originan un número determinado de transiciones (probabilidades) talcomo se indica a
continuación:

Entonces, dada una fuente de información generada por una cadena de Markov, las
probabilidades asociadas por c/u de los estados pueden ser determinadas en base a las
probabilidades de transición.
En forma genérica se tiene:
p(Si)=p(S1)p(Si/S1)+ p(S2)p(Si/S2)+p(S3 )p(Si/S3)+ p(Si)p(Si/Si) [1]
Además, debe cumplirse que:
p(S1)+p(S2)+…..+p(Si)=1 [2]
Así, lasprobabilidades asociadas a p(S1), p(S2) y p(S3) serán:
p(S1)=p(S1)p(S1/S1)+p(S2)p(S1/S2)+p(S3)p(S1/S3)
p(S2)=p(S1)p(S2/S1)+p(S2)p(S2/S2)+p(S3)p(S2/S3)
p(S3)=p(S1)p(S3/S1)+p(S2)p(S3/S2)+p(S3)p(S3/S3)
Y adicionalmente se cumple que: p(S1)+p(S2)+p(S3)=1

Ejemplo
Considere una fuente discreta con memoria (cadena de Markov).
La fuente del alfabeto está dada por Q={0,1}
Las probabilidades detransición para esta cadena de Markov son:
p(0/00)=p(1/11)=0,8
p(1/00)=p(0/11)=0,2
p(0/01)=p(0/10)=p(1/01)=p(1/10)=0,5
Determine:
a) Diagrama de estado
b) Probabilidad asociada a cada uno de los estados
Solución
La cadena de Markov se compone de 4 estados, donde estos se denominan S1, S2, S3 y S4
Definición de los estados
S1=00
S2=01
S3=10
S4=11
Significado de p(0/00)
Lasprobabilidades dadas corresponden a las probabilidades de transiciones de los estados
definidos como S1, S2, S3 y S4.
De allí que tenemos que relacionar cada una de las probabilidades de transición con cada uno de
los estados pendientes.
p(0/00)

0 0 0
Estado Final
Estado inicial o dado

p(Si/Sj)

Si estado final y Sj estado inicial o dado

Entonces:
 p(0/00)=p(S1/S1)
 p(1/11)= p(S4/S4)
p(1/00)= p(S2/S1)
 p(0/11)= p(S3/S4)
y así sucesivamente, pudiendo entonces representar el diagrama de estados, tal como se
muestra a continuación:

a) Diagrama de estados de la cadena de Markov

A continuación calcularemos las probabilidades asociadas a cada uno de los estados de la cadena
de markov.
b)
0

0

p( S1 )  p( S1 )  p( S1 / S1 )  p( S 2 )  p( S1 / S 2 )  p( S3 )  p(S1 / S3 )  p( S 4 )  p( S1 / S 4 ) [1]
p( S1 )  0,8 p( S1 )  0.5 p( S3 )
 p( S1 ) 

5
p( S3 ) [2]
2

De manera análoga:

p( S 2 )  p( S1 )  p( S 2 / S1 )  p( S 2 )  p( S 2 / S 2 )  p( S3 )  p( S 2 / S3 )  p( S 4 )  p( S 2 / S 4 ) [3]
p( S 2 )  0,2 p( S1 )  0.5 p( S3 )

1 5
1
p ( S 2 )   p( S3 )  p( S3 )
5 2
2
 p( S 2 )  p( S3 ) [4]
p( S3 )  p( S1 )  p(...