Teora-de-la-informacion-clasica-y-cuantica

Vista previa del material en texto

UNIVERSIDAD  NACIONAL 
AUTÓNOMA DE MÉXICO
FACULTAD DE CIENCIAS
LICENCIATURA EN MATEMÁTICAS
Teoría de la Información Clásica y Cuántica
T   E   S   I   S
QUE PARA OBTENER EL TÍTULO DE:
LICENCIATURA EN MATEMÁTICAS
PRESENTA:
JUAN PABLO CHÁVEZ OCHOA
DIRECTOR DE TESIS: DR. MIGUEL 
ARTURO BALLESTEROS MONTERO
2018 
 
CIUDAD UNIVERSITARIA, CDMX
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
1. Datos del alumno 
 Chávez 
 Ochoa 
 Juan Pablo 
 55 96 00 85 
 Universidad Nacional Autónoma de 
 México 
 Facultad de Ciencias 
 311593765 
 
2. Datos del tutor 
 Dr 
 Miguel Arturo 
 Ballesteros 
 Montero 
 
3. Datos de sinodal 1 
 Dr 
 Luis Octavio 
 Silva 
 Pereyra 
 
4. Datos de sinodal 2 
 Dr 
 Francisco Javier 
 Torres 
 Ayala 
 
5. Datos de sinodal 3 
 Dr 
 Rafael René 
 del Río 
 Castillo 
 
6. Datos de sinodal 4 
 Dr 
 Luis Antonio 
 Rincón 
 Solís 
 
7. Datos del trabajo escrito 
 Teoría de la Información Clásica y Cuántica 
 108p 
 2018
 
 
Este trabajo fue posible gracias a la ayuda proveniente de diversos lugares: 
 
Estoy agradecido con la Universidad Nacional Autónoma de México, por la excelente 
preparación y recursos que me ha ofrecido. Durante mi educación en la UNAM adquirí el 
pensamiento científico y la capacidad de razonamiento crítico que forman una parte 
crucial de mi preparación, como científico y como persona. Agradezco mucho los apoyos 
economicos que me fueron proporcionados durante esta etapa, los programas PAPIIT- 
DGAPA UNAM IN103918 y SEP-CONACYT 254062. 
 
Agradezco a mi padre, Francisco Javier, por su orientación y por el incansable apoyo a lo 
largo de la carrera, así como a mi madre, Beatriz Eugenia, por siempre estar disponible 
en momentos de necesidad. Agradezco cariñosamente a mi hermana, María Fernanda, 
por ser una gran amiga y consejera. Estoy enormemente agradecido con mi tío y padrino, 
Juan Carlos. Su ayuda ha facilitado mis estudios de forma inimaginable. 
 
A Jimena, por su apoyo y compañía durante esta difícil etapa. Por demostrarme su cariño 
y amor incondicionales, por ser una gran amiga. Por su ayuda, incluso de las formas más 
inesperadas, le agradezco con todo mi corazón. 
 
A mi asesor, el Dr. Miguel Ballesteros, por ser una inagotable fuente de consejos y por 
haber tomado en sus manos el progreso de mi educación, así como la dirección de este 
trabajo. Su tutela me ha demostrado la importancia del rigor y ha fomentado en mi una 
fuerte noción acerca de lo que es científicamente correcto. 
 
A los miembros de mi Jurado: el Dr. Luis Octavio Silva Pereyra, el Dr. Rafael René del 
Río Castillo, el Dr. Francisco Javier Torres Ayala, y el Dr. Luis Antonio Rincón Solís, por 
haber aceptado la responsabilidad de revisar este trabajo. Al Dr. Rincón le agradezco 
también el haberme introducido al campo de la Teoría de la Información. 
 
Finalmente, quiero agradecer a mis familiares y amigos más cercanos, porque siempre 
puedo contar con ellos, y porque su presencia hace y hará siempre de mi vida una mejor 
experiencia. 
Agradecimientos
Índice general
1. Introducción 3
I Teoŕıa de la Información Clásica 5
2. Conceptos Fundamentales 7
3. Propiedad de equipartición asintótica y Tipicalidad 35
4. Capacidad de canales 43
II Teoŕıa de la Información Cuántica 63
5. Conceptos Fundamentales de la Teoŕıa Cuántica 65
6. Tipicalidad cuántica 103
1
2 ÍNDICE GENERAL
Caṕıtulo 1
Introducción
La presente Tesis está dividida en dos partes: Teoŕıa de la Información
Clásica, y Teoŕıa de la Información Cuántica. La primera parte está basada
principalmente en [2], mientras que la segunda se basa en [8] y [4]. El objetivo
de este trabajo es doble: en primer lugar, se presentan los conceptos clave y
muchos de los resultados más relevantes de ambas teoŕıas de forma rigurosa,
de manera que un estudiante de licenciatura con conocimientos sólidos de
Probabilidad y Álgebra Lineal pueda comprenderlos. En segundo lugar, se
tratan ambas teoŕıas de tal forma que el lector pueda encontrar puntos de
comparación importantes, y que se pueda entender a la Teoŕıa de la Infor-
mación Cuántica como una generalización, o al menos como una extensión
de la Teoŕıa clásica (más en general, se puede ver a la Probabilidad Cuántica
como una generalización de la Teoŕıa de la Probabilidad Clásica.)
En la primera parte se desarrollan los conceptos fundamentales de la
Teoŕıa de la Información Clásica, con el objetivo de desarrollar una teoŕıa
para el concepto de Canal de Comunicación, y culminando en el segundo
Teorema de Shannon, que afirma la existencia de un código que nos per-
mite enviar información a través de un canal ruidoso (en la práctica puede
ser una red de telecomunicaciones inalámbricas o de fibra óptica, por ejem-
plo) de manera óptima, es decir, minimizando los errores de transmisión.
Además de éste Teorema, se presentan resultados relevantes por śı solos co-
mo la Desigualdad de Fano, La Desigualdad de Procesamiento de Datos y
la Propiedad de Equipartición Asintótica. Por cuestiones de espacio, se han
omitido los temas sobre tasas de entroṕıa para procesos estocásticos, fuentes
de información y Teoŕıa de Códigos. Por esta razón, nos limitareos a presen-
tar una versión particular del Teorema de Shannon, que sin embargo ilustra
3
4 CAPÍTULO 1. INTRODUCCIÓN
las ideas generales de éste y sus implicaciones. El lector pude consultar [2] o
[9] para tratamientos informales de estos temas, enfocados en aplicaciones, y
[1] para un tratamiento formal y una prueba formal del Teorema de Shannon
para canales discretos.
En la segunda parte, se desarrollan los conceptos fundamentales de la
Teoŕıa Cuántica. Después de introducir algunos conceptos básicos de Mecáni-
ca Cuántica para sistemas con un número finito de estados, se desarrolla una
teoŕıa de canales cuánticos. De entre los resultados técnicos de ésta parte,
vale la pena destacar el Teorema de Choi-Kraus, que nos da una forma de
descomponer canales cuánticos en una suma de productos de operadores que
cumplen ciertas condiciones, dándo una manera simple de definir canales a
través de dichos operadores. Además del concepto de canal, se definen varios
conceptos análogos a los de la Teoŕıa Clásica como el de Entroṕıa, Distancia
de Kullback-Liebler, Información mutua, etc. Además de esto se presenta
un caṕıtulo sobre Tipicalidad Cuántica. En éste se demuestran muchos re-
sultados con análogos clásicos, y se ilustran algunos puntos de comparación
sutiles. A diferencia de la primera parte, no dedicaremos un tercer caṕıtulo a
una vrsión cuántica del Teorema de Shannon; la Teoŕıa de canales cuánticos
se presenta en conjunto con los fundamentos de la Teoŕıa Cuántica en el pri-
mer caṕıtulo. El desarrollo de la teoŕıa necesaria para deducir un resultado
como éste aumentaŕıa la longitud de este trabajo de forma considerable. Para
un desarrollo completo puede consultarse [8].
Parte I
Teoŕıa de la Información
Clásica
5
Caṕıtulo 2
Conceptos Fundamentales
Definición 1. (Variable Aleatoria Discreta) Sea (Ω,F , P ) un espacio de
probabilidad y sea (X , S) un espacio medible discreto. Una variable aleatoria
(v.a) discreta es una función X :Ω→ X talque X−1 (A) ∈ F ∀A ∈ S.
Definición 2. (Entroṕıa de una v.a. discreta) Sea X una v.a. discreta con
medida de probabilidad P. Definimos la Entroṕıa en base a de X como
Ha (X) := −
∑
x∈X
P (ω ∈ Ω : X (ω) = x) loga P (ω ∈ Ω : X (ω) = x). (2.1)
En esta definición adoptamos la convención de que 0 loga 0 = 0, justificada
por la continuidad de x loga x y el hecho de que ĺımx→0 x loga x = 0. Al con-
junto X le llamamos el alfabeto de X. Si a = 2, decimos que la entroṕıa de X
se mide en bits. A partir de ahora escribiremos log en lugar de log2 y H(X)
en lugar de H2(X).
Definición 3. (Rectángulo medible) Sean (X1, S1), ..., (Xn, Sn) espacios me-
dibles. Un subconjunto R ⊂ X1 × ... × Xn se llama rectángulo medible si es
de la forma R = A1 × ... × An con A1 ∈ S1, ..., An ∈ Sn. Nos referiremos a
A1, ..., An como los lados de R. Denotaremos por S1×...×Sn = {A1×...×An :
A1 ∈ S1, ..., An ∈ Sn} a la familia de rectángulos medibles.
Definición 4. (Espacio medible producto) Sean (X1, S1), ..., (Xn, Sn) espacios
medibles. Definimos el espacio medible producto como la pareja
(X1 × ...×Xn, S1 ⊗ ...⊗ Sn) (2.2)
en donde S1 ⊗ ... ⊗ Sn es la mı́nima σ-álgebra generada por la colección
S1 × ...× Sn.
7
8 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Definición 5. (Vector aleatorio discreto) Sea (Ω,F , P ) un espacio de proba-
bilidad. Sea X : Ω→ X1× ...×Xn una función. Diremos que X es un vector
aleatorio si X−1(A) ∈ F ∀A ∈ S1⊗...⊗Sn. El vector X puede representarse
de la forma X = (X1, ...Xn), donde cada coordenada Xi es una función de Ω
en Xi.
Nota 6. Puede demostrarse que una función (X1, ..., Xn) : Ω→ X1× ...×Xn
es un vector aleatorio si y sólo si cada coordenada Xi : Ω → Xi es una
función F − Si medible, i.e. una variable aleatoria (ver [7], capt. 3).
Definición 7. (Entroṕıa conjunta) Sea (Ω,F , P ) un espacio de probabilidad.
Sean Xi : Ω → Xi, i = 1, 2, ..., n variables aleatorias discretas. Definimos
la entroṕıa conjunta de X1, ..., Xn como la entroṕıa sobre los valores de la
ditribución P del vector aleatorio (X1, ...Xn), es decir
H(X1, ..., Xn) := −
∑
x∈X1×...×Xn
P (ω ∈ Ω : (X1, ...Xn)(ω) = x)
logP (ω ∈ Ω : (X1, ...Xn)(ω) = x)
(2.3)
Notación 8. A partir de este punto escribiremos
P (ω ∈ Ω : (X1, ...Xn)(ω) = (x1, ..., xn)) = P (X1 = x1, ..., Xn = xn) (2.4)
= p(x1, ..., xn) (2.5)
y
P (ω ∈ Ω : Xi(ω) = xi) = P (Xi = xi) (2.6)
= p(xi). (2.7)
También utilizaremos las notaciones (X1, ...Xn) = X
n y (x1, ...xn) = x
n.
Definición 9. (Valor esperado) Sea (Ω,F , P ) un espacio de probabilidad.
Sea X : Ω→ X ⊂ R una v.a. en este espacio, y sea g : X → R una función.
Entonces podemos definir la v.a. g(X) : Ω→ R. Definimos el valor esperado
de g(X) como
EP (g(X)) :=
∑
x∈X
g(x)p(x) (2.8)
Si no existe riesgo de confusión, escribiremos EP = E.
9
Nota 10. Si hacemos g(x) = log 1
p(x)
en la Definición 9, tenemos que
E(g(X)) =
∑
x∈X
p(x) log
1
p(x)
(2.9)
= H(X). (2.10)
Lema 11. Sea X : Ω → X una variable aleatoria discreta (vector aleatorio
discreto) en el espacio (Ω,F , P ). Entonces H(X) ≥ 0.
Demostración. Como 0 ≤ p(x) ≤ 1 para x ∈ X , tenemos que 0 ≤ p(X) ≤ 1,
por lo cual log 1
p(X)
≥ 0. por lo tanto
E
(
log
1
p(X)
)
≥ 0. (2.11)
Definición 12. (Probabilidad condicional) Sea (Ω,F , P ) un espacio de pro-
babilidad, y sea B ∈ F tal que P (B) > 0. Para cada A ∈ F definimos la
probabilidad condicional de A dadoB como
P (A | B) := P (A ∩B)
P (B)
(2.12)
Es fácil ver que P (· | B) es medida de probabilidad. Si X : Ω→ X y Y : Ω→
Y son v.a.s en (Ω,F , P ), podemos definir la cantidad P (X = x | Y = y) para
x ∈ X y y ∈ Y haciendo
A = {X = x} = {ω ∈ Ω : X(ω) = x} (2.13)
B = {Y = y} = {ω ∈ Ω : Y (ω) = y} (2.14)
en la definición de P (A | B), es decir,
P (X = x | Y = y) = P ({X = x} | {Y = y}) (2.15)
En adelante asumremos que P (Y = y) > 0 para y ∈ Y.
Notación 13. En adelante escribiremos P (X = x | Y = y) = p(x | y), si no
es necesario hacer mención de las variables X y Y .
10 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Definición 14. (Entroṕıa condicional) Sea (Ω,F , P ) espacio de probabilidad
y sean X : Ω→ X y Y : Ω→ Y v.a.s en este espacio. Definimos la entroṕıa
condicional de X dada Y como
H(X | Y ) := −
∑
x∈X
∑
y∈Y
p(x, y) log p(x | y) (2.16)
Nota 15. Si hacemos g(x, y) = log 1
p(x,y)
en la definición 9, obtenemos que
E(g(X, Y )) =
∑
x∈X
∑
y∈Y
p(x, y) log
1
p(x, y)
(2.17)
= H(X, Y ), (2.18)
y si hacemos g(x, y) = log 1
p(x|y) en la definición 9, tenemos que
E(g(X, Y )) =
∑
x∈X
∑
y∈Y
p(x, y) log
1
p(x | y)
(2.19)
= H(X | Y ). (2.20)
Teorema 16. (Regla de la cadena) Sean X : Ω → X y Y : Ω → Y v.a.s en
el espacio de probabilidad (Ω,F , P ). Entonces
H(X, Y ) = H(X) +H(Y | X) (2.21)
Demostración. Primero observemos que
P (X = x) = P ({X = x} ∩ Ω) (2.22)
= P
(
{X = x} ∩
⋃
y∈Y
{Y = y}
)
(2.23)
= P
( ⋃
y∈Y
({X = x} ∩ {Y = y})
)
(2.24)
= P
( ⋃
y∈Y
{X = x, Y = y}
)
(2.25)
= P (X = x, Y = y), (2.26)
11
pues Y es discreto. Es decir, p(x) =
∑
y∈Y p(x, y). Entonces
H(X, Y ) = −
∑
x∈X
∑
y∈Y
p(x, y) log p(x, y) (2.27)
= −
∑
x∈X
∑
y∈Y
p(x, y) log p(y | x)p(x) (2.28)
= −
∑
x∈X
∑
y∈Y
p(x, y) log p(y | x)−
∑
x∈X
∑
y∈Y
p(x, y) log p(x) (2.29)
= −
∑
x∈X
∑
y∈Y
p(x, y) log p(y | x)−
∑
x∈X
p(x) log p(x) (2.30)
= H(Y | X) +H(X). (2.31)
Definición 17. (Entroṕıa condicional) Sean X1 : Ω→ X1, . . . , Xn : Ω→ Xn
v.a.s en el espacio de probabilidad (Ω,F , P ). Definimos la entroṕıa condicio-
nal de Xn dadas las variables Xn−1, . . . , X1 como la entroṕıa condicional de
Xn dado el vector (Xn−1, . . . , X1), es decir
H(Xn | Xn−1, . . . , X1) := H(Xn | (Xn−1, . . . , X1)) (2.32)
Teorema 18. (Regla de la cadena) Sean X1 : Ω → X1, . . . , Xn : Ω → Xn
para n ≥ 2 v.a.s en el espacio de probabilidad (Ω,F , P ). Entonces
H(Xn, . . . , X1) = H(X1) +
n∑
i=2
H(Xi | Xi−1, . . . , X1), (2.33)
Demostración. Procedemos por inducción sobre n ≥ 2 El caso base (n = 2)
es la prueba del Teorema 16. Supongamos que el resultado es cierto para
algún natural n ≥ 2. Entonces
H(X1, . . . , Xn, Xn+1) = H((X1, . . . , Xn), Xn+1) (2.34)
= H(Xn+1 | (Xn, . . . , X1)) +H(X1, . . . , Xn) (2.35)
= H(Xn+1 | (Xn, . . . , X1)) (2.36)
+H(X1) +
n∑
i=2
H(Xi | Xi−1, . . . , X1) (2.37)
= H(X1) +
n+1∑
i=2
H(Xi | Xi−1, . . . , X1), (2.38)
12 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
donde la segunda igualdad se sigue del Teorema 16, y la tercera de la hipótesis
de inducción.
Definición 19. (Entroṕıa relativa o distancia de Kullback-Leibler) Sean X :
Ω → X y Y : Ω → X v.a.s en los espacios de probabilidad (Ω,F , P ) y
(Ω,F , Q) respectivamente. Definimos la entroṕıa relativa de X con Y como
D(p || q) :=
∑
x∈X
p(x) log
p(x)
q(x)
(2.39)
Aqúı aceptamos las convenciones 0 log 0
0
= 0, 0 log 0
q
= 0, y p log p
0
= ∞.
Por lo tanto, si existe x ∈ X tal que p(x) > 0 y q(x) = 0, tenemos que
D(p || q) =∞.
Nota 20. Si hacemos g(x) = log p(x)
q(x)
en la definición 9, tenemos que
E(g(x)) =
∑
x∈X
p(x) log
p(x)
q(x)
(2.40)
= D(p || q). (2.41)
Definición 21. (Información mutua) Sea (X, Y ) : Ω → X × Y un vector
aleatorio en el espacio de probabilidad (Ω,F , P ). Sean p(x) y q(y) las dis-
tribuciones marginales de X y Y respectivamente. Definimos la información
mutua de las variables X y Y como la entroṕıa relativa de las distribuciones
p(x, y) y p(x)q(y), es decir,
I(X : Y ) := D(p(x, y) || p(x)q(y)) (2.42)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x, y)
p(x)q(y)
(2.43)
Nota 22. Si hacemos g(x, y) = log p(x,y)
p(x)q(y)
en la definición 9, tenemos que
E(g(x, y)) =
∑
x∈X
∑
y∈Y
p(x, y) log
p(x, y)
p(x)q(y)
(2.44)
= I(X : Y ). (2.45)
Teorema 23. (Propiedades de la Información Mutua) Sea (X, Y ) : Ω →
X ×Y un vector aleatorio en el espacio de probabilidad (Ω,F , P ). Entonces
13
1. I(X : Y ) = H(X)−H(X | Y )
2. I(X : Y ) = H(Y )−H(Y | X)
3. I(X : Y ) = H(X) +H(Y )−H(X, Y )
4. I(X : Y ) = I(Y : X)
5. I(X : X) = H(X)
Demostración. 1. Recordemos que p(x | y) = p(x,y)
p(y)
por definición. Enton-
ces
I(X : Y ) =
∑
x∈X
∑
y∈Y
p(x, y) log
p(x,y)
p(x)p(y)
(2.46)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x | y)
p(x)
(2.47)
= −
∑
x∈X
∑
y∈Y
p(x, y) log p(x) +
∑
x∈X
∑
y∈Y
p(x, y) log p(x | y)
(2.48)
= −
∑
x∈X
p(x) log p(x)−
(
−
∑
x∈X
∑
y∈Y
p(x, y) log p(x | y)
)
(2.49)
= H(X)−H(X | Y ), (2.50)
donde la penúltima igualdad sucede porque p(x) =
∑
y∈Y p(x, y).
2. Es análoga al inciso anterior, usando que p(y | x) = p(x,y)
p(x)
en lugar de
p(x | y) = p(x,y)
p(y)
.
3. Usando el teorema 16, tenemos que
H(X, Y ) = H(X) +H(Y | Y ). (2.51)
Entonces del inciso anterior tenemos que
I(X : Y ) = H(Y )−H(Y | X) (2.52)
= H(Y ) +H(X)−H(X, Y ). (2.53)
14 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
4. Por definición de la Información Mutua, usando que p(x, y) = p(y, x).
5. Observemos que
p(x, y) = P ({X = x} ∩ {X = y}) = P ({X = x}) = p(x) (2.54)
si x = y, y
p(x, y) = P (∅) = 0 (2.55)
si x 6= y, por lo cual
H(X | X) = −
∑
x∈X
∑
y∈X
p(x, y) log
p(x, y)
p(x)
(2.56)
= −
∑
x∈X
p(x, x) log
p(x, x)
p(x)
(2.57)
= −
∑
x∈X
p(x) log(1) = 0. (2.58)
Por lo tanto, del primer inciso se sigue que
I(X : X) = H(X)−H(X | X) = H(X). (2.59)
Definición 24. (Información mutua condicional) Sea (X, Y, Z) : Ω→ X1 ×
X2×X3 un vector aleatorio en el espacio de probabilidad (Ω,F , P ). Definimos
la información mutua de X y Y dada Z como la cantidad
I(X : Y | Z) := H(X | Z)−H(X | Y, Z). (2.60)
Teorema 25. (Regla de la cadena para la información mutua) Sea (X1, . . . , Xn, Y ) :
Ω → X1 × · · · × Xn × Y un vector aleatorio en el espacio de probabilidad
(Ω,F , P ). Entonces
I(X1, . . . , Xn;Y ) = I(X1;Y ) +
n∑
i=2
I(Xi;Y | Xi−1, . . . , X1). (2.61)
15
Demostración. De los teoremas 18 y 23, tenemos que
I(X1, . . . , Xn : Y ) (2.62)
= H(X1, . . . , Xn)−H(X1, . . . , Xn | Y ) (2.63)
= H(X1) +
n∑
i=2
H(Xi | Xi=1, . . . , X1)−H(X1, . . . , Xn | Y ) (2.64)
= H(X1) +
n∑
i=2
H(Xi | Xi=1, . . . , X1) +H(Y )−H(X1, . . . , Xn, Y ) (2.65)
= H(X1) +
n∑
i=2
H(Xi | Xi=1, . . . , X1) +H(Y )−H(Y ) (2.66)
−
n∑
i=1
H(Xi | Xi−1, . . . , X1, Y ) (2.67)
= H(X1) +
n∑
i=2
H(Xi | Xi=1, . . . , X1)−
n∑
i=1
H(Xi | Xi−1, . . . , X1, Y )
(2.68)
= H(X1)−H(X1 | Y ) +
n∑
i=2
I(Xi : Y | Xi−1, . . . , X1) (2.69)
= I(X1;Y ) +
n∑
i=2
I(Xi : Y | Xi−1, . . . , X1). (2.70)
Teorema 26. Sea (X, Y ) : Ω → X × Y un vector aleatorio en los espacios
de probabilidad (Ω,F , P ) y (Ω,F , Q). Entonces
D(p(x, y) || q(x, y)) = D(p(x) || q(x)) +
∑
x∈X
p(x)D(p(y | x) || q(y | x)).
(2.71)
16 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Demostración.
D(p(x, y) || q(x, y)) =
∑
x∈X
∑
y∈Y
p(x, y) log
p(x, y)
q(x, y)
(2.72)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(y | x)p(x)
q(y | x)q(x)
(2.73)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x)
q(x)
+
∑
x∈X
∑
y∈Y
p(x, y) log
p(y | x)
q(y | x)
(2.74)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x)
q(x)
(2.75)
+
∑
x∈X
p(x)
[∑
y∈Y
p(y | x) log p(y | x)
q(y | x)
]
(2.76)
= D(p(x) || q(x)) +
∑
x∈X
p(x)D(p(y | x) || q(y | x)).
(2.77)
Definición 27. (Función real convexa) Sea f : (a, b) → R una función.
Decimos que f es convexa en (a, b) si para cada x1, x2 ∈ (a, b) y 0 ≤ λ ≤ 1,
f(λx1 + (1− λ)x2) ≤ λf(x1) + (1− λ)f(x2), (2.78)
con x1 < x2. Decimos que f es etrictamente convexa si la igualdad se cumple
sólo cuando λ = 1 o λ = 0.
Definición 28. Decimos que f : (a, b)→ R es cóncava si −f es convexa, y
estrictamente cóncava si −f es estrictamente convexa.
Teorema 29. (Desigualdad de Jensen) Sea X : Ω → R una v.a. en el
espacio de probabilidad (Ω,F , P ) con E(X) < ∞, y sea φ : R → R una
función convexa. Entonces
φ(E(X)) ≤ E(φ(X)). (2.79)
Cuando se cumple la igualdad y φ es estrictamente convexa, entonces X es
constante casi seguramente, es decir, X = E(X) c.s.
17
Demostración. Haremos la prueba para el caso discreto, que es el que será
usado más adelante. Sea X : Ω → X ⊂ R una v.a. discreta en (Ω,F , P ).
Procedemos por inducción sobre n =| X |. Para n = 1 el resultado es trivial.
Para n = 2, tenemos por convexidad que
φ(E(X)) = φ(p(x1)x1 + p(x2)x2) (2.80)
= p(x1)φ(x1) + p(x2)φ(x2) (2.81)
= E(φ(X)), (2.82)
pues p(x1) + p(x2) = 1 y p(x1), p(x2) ≥ 0.
Supongamos que el resultado es cierto para n = k − 1. Denotemos por
pi = p(xi), i = 1, . . . , k a los valores de la distribución p(x) de la v.a X
que toma k valores. Entonces {p′1, . . . , p′k−1} con p′i =
pi
1−pk
(pk 6= 1) para
i = 1, . . . , k − 1, es una distribución de probabilidad para una v.a que toma
valores x1, . . . , xk−1. Entonces
φ(E(X)) = φ
(
k∑
i=1
pixi
)
(2.83)
= φ
(
pkxk + (1− pk)
k−1∑
i=1
pi
1− pk
xi
)
(2.84)
≤ pkφ(xk) + (1− pk)φ
(
k−1∑
i=1
pi
1− pk
xi
)
(2.85)
≤ pkφ(xk) + (1− pk)
k−1∑
i=1
pi
1− pk
φ(xi) (2.86)
=
k∑
i=1
piφ(xi) = E(φ(X)), (2.87)
donde la primera desigualdad se sigue del caso n = 2, y la segunda por
hipótesis de inducción. Para la segunda parte del teorema, supongamos queX
toma los valores x1, x2, . . . con probabilidades p1, p2, . . . (para esta parte no
necesitamos que X sea finita), y supongamos que φ es estrictamente convexa.
Supongamos por reducción al absurdo que X no es constante. Es decir, p1 6=
18 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
1, p2 6= 1, . . . Que la igualdad se cumpla implica lo siguiente:
E(φ(X)) = p1φ(x1) + p2φ(x2) + . . . (2.88)
= φ(p1x1 + p2x2 + . . . ) (2.89)
= φ
(
p1x1 + (1− p1)
(
p2
1− p− 1
x2 +
p3
1− p1
x3 + . . .
))
(2.90)
< p1φ(x1) + (1− p1)φ
(
p2
1− p1
x2 +
p3
1− p1
x3 + . . .
)
(2.91)
= p1φ(x1) + p2φ(x2) + (1− p1)(1− p2)φ
(
p3
(1− p1)(1− p2)
x3 + . . .
)
(2.92)
= (2.93)
... (2.94)
= p1φ(x1) + p2φ(x2) + · · · = E(φ(X)), (2.95)
donde la segunda igualdad se da por la hipótesis de que φ(E(X)) = E(φ(X))
y la primera desigualdad por convexidad estricta, e iteramos el proceso. Por
lo tanto E(φ(X)) < φ(E(X)). Esto es una contradicción. Por lo tanto existe
i tal que pi = 1, es decir, X es constante, y E(X) = pixi = 1xi = X c.s.
Recordemos el siguiente hecho del Cálculo:
Teorema 30. Si una función f : I → R de clase C2 tiene segunda derivada
no negativa (positiva), entonces f es convexa (estrictamente convexa) en I.
Teorema 31. Sean p(x) y q(x) dos medidas de probabilidad en el alfabeto
X . Entonces
D(p || q) ≥ 0, (2.96)
y la igualdad se cumple si y sólo si p(x) = q(x) para toda x ∈ X .
19
Demostración. Sea A = {x ∈ X : p(x) > 0}. Entonces
−D(p || q) = −
∑
x∈X
p(x) log
p(x)
q(x)
(2.97)
= −
∑
x∈A
p(x) log
p(x)
q(x)
(2.98)
=
∑
x∈A
p(x) log
q(x)
p(x)
(2.99)
= Ep
(
log
q(x)
p(x)
)
(2.100)
≤ logEp
(
q(x)
p(x)
)
(2.101)
= log
∑
x∈A
p(x)
q(x)
p(x)
(2.102)
= log
∑
x∈A
q(x) (2.103)
≤ log
∑
x∈X
q(x) (2.104)
= log(1) = 0, (2.105)
donde la primera desigualdad se sigue del Teorema 29 y la concavidad de
t → log t en (0, 1] (Teorema 30). Además, t → log t es estrictamente cnvexa
en (0, 1] (Teorema 30). Entonces por el Teorema 29 tenemos que D(p || q) = 0
si y sólo si p(x)
q(x)
= c c.s. con c una constante, si y sólo si p(x)
q(x)
= c para toda
x ∈ X . Es decir, p(x) = cq(x) para toda x ∈ X para alguna constante c.
Entonces ∑
x∈X
q(x) = c
∑
x∈X
= c > 0, (2.106)
por lo cual c = 1. Es decir, q(x) = p(x) para toda x ∈ X .
Definición 32. (Independencia) Sean Xi : Ω → X , i = 1, 2, . . . v.a.s en el
espacio (Ω,F , P ). Sea G1,G2, . . . una sucesión de sub σ-álgebras de F .
1. Para un entero fijo n, decimos que las n σ-álgebras G1, . . . ,Gn son in-
dependientes si
P (A1 ∩ A2 ∩ · · · ∩ An) = P (A1)P (A2) . . . P (An) (2.107)
20 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
para todos A1 ∈ G1, A2 ∈ G2, . . . , An ∈ Gn.
2. Decimos que las n v.a.s X1, . . . , Xn son independientes si las corres-
pondientes σ-álgebras generadas σ(X1), . . . , σ(Xn) son independientes.
3. Decimos que toda la sucesión G1,G2, . . . de σ-álgebras es independiente
si para cada n las σ-álgebras G1, . . . ,Gn son independientes.
4. Decimos que la sucesión de v.a.s {Xi}∞i=1 es independiente si para cada
n, las v.a.s X1, . . . , Xn son independientes.
Nota 33. Consideremos el contexto de la Definición 32, tomando las v.a.s
con valores en un alfabeto (finito). Entonces las v.a.s X1,. . . , Xn son inde-
pendientes si y sólo si
P ({X1 = x1}∩· · ·∩{Xn = xn}) = P ({X1 = x1}) . . . P ({Xn = xn}) (2.108)
para todas x1, . . . , xn ∈ X . De forma abreviada, p(x1, . . . , xn) = p(x1) . . . p(xn).
Corolario 34. Sean X : Ω→ X y Y : Ω→ Y v.a.s en (Ω,F , P ). Entonces
I(X : Y ) ≥ 0, (2.109)
con igualdad si y sólo si p(x, y) = p(x)p(y) (i.e. si X y Y son independientes).
Demostración. Por el teorema 31, tenemos que
I(X : Y ) = D(p(x, y) || p(x)p(y)) ≥ 0, (2.110)
con igualdad si y sólo si p(x, y) = p(x)p(y).
Corolario 35. Sean X : Ω→ X y Y : Ω→ Y v.a.s en los espacios (Ω,F , P )
y (Ω,F , Q). Entonces
D(p(x, y) || q(x, y)) ≥ D(p(x) || q(x)) (2.111)
21
Demostración. Por el Teorema 31 obtenemos que
0 ≤ D(p(y | x) || q(y | x)) (2.112)
=
∑
x∈X
p(x)
∑
y∈Y
p(y | x) log p(y | x)
q(y | x)
(2.113)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x, y)q(x)
q(x, y)p(x)
(2.114)
=
∑
x∈X
∑
y∈Y
p(x, y) log
p(x, y)
q(x, y)
−
∑
x∈X
∑
y∈Y
p(x, y) log
p(x)
q(x)
(2.115)
= D(p(x, y) || q(x, y))−D(p(x) || q(x)). (2.116)
Corolario 36. Sean X : Ω → X , Y : Ω → Y y Z : Ω → Z v.a.s en
(Ω,F , P ). Entonces
1. I(X : Y | Z) ≥ 0
2. I(X : Y | Z) = 0 si y sólo si p(x, y | z) = p(x | z)p(y | z) (i.e. X y Y
son condicionalmente independientes de Z).
Demostración. Observemos que
p(x | y, z) = p(x, y, z)
p(y, z)
(2.117)
=
p(x, y | z)p(z)
p(y | z)p(z)
(2.118)
=
p(x, y | z)
p(y | z)
. (2.119)
Entonces,
22 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
I(X : Y | Z) = H(X | Z)−H(X | Y, Z) (2.120)
=
∑
x,z
p(x, z) log
1
p(x | z)
−
∑
x,y,z
p(x, y, z) log
1
p(x | y, z)
(2.121)
=
∑
x,y,z
p(x, y, z) log
1
p(x | z)
−
∑
x,y,z
p(x, y, z) log
1
p(x | y, z)
(2.122)
=
∑
x,y,z
p(x, y, z) log
1
p(x | z)
+
∑
x,y,z
p(x, y, z) log p(x | y, z)
(2.123)
=
∑
x,y,z
p(x, y, z) log
p(x | y, z)
p(x | z)
(2.124)
=
∑
x,y,z
p(x, y, z) log
p(x, y | z)
p(x | z)p(y | z)
(2.125)
=
∑
z
p(z)
∑
x,y
p(x, y | z) log p(x, y | z)
p(x | z)p(y | z)
(2.126)
=
∑
z
p(z)D(p(x, y | z) || p(x | z)p(y | z)) ≥ 0 (2.127)
con igualdad si y sólo si p(x, y | z) = p(x | z)p(y | z).
Teorema 37. Sea X : Ω→ X v.a. en (Ω,F , P ) con | X |= n. Entonces
1. H(X) ≤ log n
2. Se cumple la igualdad si y sólo si p(x) = 1
n
para toda x ∈ X .
Demostración. 1. Sea u : F → [0, 1] la medida de probabilidad uniforme
en X , es decir, u(x) = 1
n
, x ∈ X . Entonces por el Teorema 31 tenemos
23
que
0 ≤ D(p || u) (2.128)
=
∑
x∈X
p(x) log
p(x)
u(x)
(2.129)
=
∑
x∈X
p(x) log np(x) (2.130)
=
∑
x∈X
p(x) log n+
∑
x∈X
p(x) log p(x) (2.131)
= log n−H(X). (2.132)
2. D(p || u) = 0 si y sólo si p(x) = u(x) para toda x ∈ X , es decir
H(X) = log n si y sólo si p(x) = u(x) para toda x ∈ X .
Teorema 38. (El condicionamiento reduce la entroṕıa) Sean X : Ω → X y
Y : Ω→ X v.a.s en (Ω,F , P ). Entonces
H(X | Y ) ≤ H(X). (2.133)
Demostración. Por el corolario 34 y el teorema 23 tenemos que
0 ≤ I(X : Y ) = H(X)−H(X | Y ). (2.134)
Observemos que por 34, H(X) = H(X | Y ) si y sólo si X y Y son indepen-
dientes.
Teorema 39. Sea (X1, . . . , Xn) : Ω→ X1 × · · · × Xn un vector aleatorio en
(Ω,F , P ). Entonces
H(X1, . . . , Xn) ≤
n∑
i=1
H(Xi) (2.135)
y la igualdad se da si y sólo si X1, . . . , Xn son independientes.
Demostración. Por el Teorema 18, se cumple que
H(X1, . . . , Xn) =
n∑
i=1
H(Xi | Xi−1, . . . , X1). (2.136)
24 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Por el Teorema 38, tenemos que
n∑
i=1
H(Xi | Xi−1, . . . , X1) ≤
n∑
i=1
H(Xi). (2.137)
La igualdad se cumple si y sólo si H(Xi) = H(Xi | Xi−1, . . . , X1), si y
sólo si Xi es independiente de (Xi−1, . . . , X1), si y sólo si p(xi, xi−1, . . . , x1) =
p(xi)p(xi−1, . . . , x1) para i = 1, . . . , n, si y sólo si p(x1, . . . , xn) = p(x1) . . . p(xn),
si y sólo si X1, . . . , Xn son independientes.
Lema 40. (Desigualdad del logaritmo y la suma) Sean a1 ≥ 0, . . . , an ≥ 0 y
b1 ≥ 0, . . . , bn ≥ 0 números reales. Entonces
n∑
i=1
ai log
ai
bi
≥
(
n∑
i=1
ai
)
log
(∑n
i=1 ai
)
(∑n
i=1 bi
) , (2.138)
y la igualdad se cumple si y sólo si ai
bi
es constante para i = 1, . . . , n (definimos
ai
0
:=∞).
Demostración. Sin pérdida de generalidad podemos suponer que ai > 0 y
bi > 0, i = 1, . . . , n, pues consideramos los siguientes casos:
1. Si alguna bi = 0 y ai > 0, el lado izquierdo es infinito, pues ai log
ai
0
:=
∞.
2. Si alguna ai = 0 y bi > 0, el sumando correspondiente en cada lado es
cero, pues 0 log 0
bi
:= 0, y la desigualdad permanece sin cambio.
3. Si ai = 0 y bi = 0, ambos lados de la desigualdad permanecen sin
cambio, pues 0 log 0
0
:= 0.
Entonces supongamos que ai > 0 y bi > 0. Se puede probar (usando el
Teorema 30) que φ(t) = t log t es estrictamente convexa. Por la desigualdad
de Jensen (Teorema 29), si t1, . . . , tn son numeros reales positivos y α1, . . . , αn
son reales en [0, 1] tales que
∑n
i=1 αi = 1, se cumple que
φ
(
n∑
i=1
αiti
)
≤
n∑
i=1
αiφ(ti). (2.139)
25
Tomando αi =
bi∑n
i=1 bi
y ti =
ai
bi
, se obtiene que(
n∑
i=1
ai∑n
i=1 bi
)
log
(
n∑
i=1
ai∑n
i=1 bi
)
≤
n∑
i=1
(
bi∑n
i=1 bi
)
ai
bi
log
ai
bi
, (2.140)
es decir, (∑n
i=1 ai
)
(∑n
i=1 bi
) log
(∑n
i=1 ai
)
(∑n
i=1 bi
) ≤ ∑ni=1 ai log aibi(∑n
i=1 bi
) . (2.141)
Como φ es estrictamente convexa, por 29 tenemos que la igualdad se cumple
si y sólo si t1 = t2 = · · · = tn (v.a. constante), si y sólo si aibi es constante para
i = 1, . . . , n. La rećıproca es directa: si ai
bi
= c para i = 1, . . . , n, entonces el
lado izquierdo es (log c)
∑n
i=1 ai, y el derecho es(
n∑
i=1
ai
)
log
∑n
i=1 ai
1
c
∑n
i=1 ai
= (log c)
n∑
i=1
ai. (2.142)
Teorema 41. La entroṕıa relativa D(p || q) es convexaa vista como función
de los pares (p, q), es decir, si (p1, q1) y (p2, q2) son dos pares de funciones
de probabilidad sobre un alfabeto X . entonces
D(λp1+(1−λ)p2 || λq1+(1−λ)q2) ≤ λD(p1 || q1)+(1−λ)D(p2 || q2) (2.143)
para toda λ ∈ [0, 1].
Demostración. Por definición y aplicando el Lema 40, obtenemos que
D(λp1 + (1− λ)p2 || λq1 + (1− λ)q2) (2.144)
=
∑
x∈X
(λp1(x) + (1− λ)p2(x)) log
λp1(x) + (1− λ)p2(x)
λq1(x) + (1− λ)q2(x)
(2.145)
≤
∑
x∈X
[
λp1(x) log
λp1(x)
λq1
+ (1− λ)p2(x) log
(1− λ)p2(x)
(1− λ)q2(x)
]
(2.146)
= λ
∑
x∈X
p1(x) log
p1(x)
q1(x)
+ (1− λ)
∑
x∈X
p2(x) log
p2(x)
q2(x)
(2.147)
= λD(p1 || q1) + (1− λ)D(p2 || q2). (2.148)
26 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Observemos que por el Lema 40, la igualdad se da si y sólo si
p1,i
q1,i
y
p2,i
q2,i
son
constantes para i = 1, . . . , n =| X |. Como pk,i ≥ 0 y qk,i ≥ 0, k = 1, 2, y
además
∑n
i=1 pk,i = 1 y
∑n
i=1 qk,i = 1, tenemos que la igualdad se da si y sólo
si pk = qk, k = 1, 2.
Corolario 42. En el contexto del Teorema 41, la función p → D(p || q) es
convexa.
Demostración. Sean p1 y p2 funciones de probabilidad en X . Por el Teorema
41 tenemos que
D(λp1 + (1− λ)p2 || q) ≤ λD(p1 || q) + (1− λ)D(p2 || q) (2.149)
haciendo q1 = q2 = q.
Corolario 43. En el contexto del Teorema 41, la función q → D(p || q) es
convexa.
Demostración. Sean q1 y q2 funciones de probabilidad en X . Hacemos p =
p1 = p2 en el Teorema 41, y obtenemos
D(p || λq1 + (1− λ)q2) ≤ λD(p || q1) + (1− λ)D(p || q2). (2.150)
Teorema 44. Consideremos a la entroṕıa como una función de los vectores
de probabilidad p = (p1, . . . , pn) sobre el alfabeto X , es decir, aquellos tales
que pi ≥ 0 y
∑n
i=1 pi = 1. Es decir,
H(p) :=
n∑
i=1
pi log pi (2.151)
para p = (p1, . . . , pn). Entonces p→ H(p) es cóncava.
Demostración. Sea p = (p1, . . . , pn) un vector de probabilidad y se u la dis-
tribución uniforme en X , es decir, u = ( 1
n
, . . . , 1
n
). Por el Teorema 37 sabemos
27
que H(u) = log n. Observemos que
D(p || u) =
n∑
i=1
pi log
pi
ui
=
n∑
i=1
pi log
pi
1
n
=
n∑
i=1
pi log npi
=
n∑
i=1
pi(log n+ log pi)
= log n−H(p).
(2.152)
Por lo tanto, H(p) = log n −D(p || u). Por el corolario 42, p → D(p | u) es
convexa. Por lo tanto, p→ log n−D(p || u) es cóncava.
Nota 45. Lo anterior se puede escribir como
H(λp1 + (1− λ)p2) ≥ λH(p1) + (1− λ)H(p2) (2.153)
para λ ∈ [0,1] y p1, p2 vectores de probabilidad en X .
Definición 46. (Proceso estocástico a tiempo discreto) Un proceso estocásti-
co a tiempo discreto es una colección de v.a.s {Xn : n = 1, 2, . . . } en un
espacio de probabilidad (Ω,F , P ) y donde todas las v.a.s toman valores en
un conjunto S (llamado el espacio de estados).
Definición 47. (Cadena de Markov) Decimos que un proceso estocástico
{Xn}n con espacio de estados discreto es una cadena de Markov si cumple
la propiedad de Markov, es decir,
P (Xn = xn | Xn−1 = xn−1, . . . , X1 = x1) = P (Xn = xn | Xn−1 = xn−1)
(2.154)
para n = 1, 2, . . . En forma abreviada, p(xn | xn−1, . . . , x1) = p(xn | xn−1).
Nota 48. En particular, nos interesa el caso en el que las cadenas están
indexadas por el conjunto {1, 2, 3} y el espacio de estados es un alfabeto
S = X . En este caso, la propiedad de Markov se escribe como p(x3 | x2, x1) =
p(x3 | x2).
28 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Lema 49. En el caso de la Nota 48, la propiedad de Markov es equivalente
a las siguientes identidades:
1. p(x1, x2, x3) = p(x3 | x2)p(x2 | x1)p(x1)
2. p(x1, x3 | x2) = p(x1 | x2)p(x3 | x2).
Demostración. 1. Supongamos la propiedad de Markov. Entonces
p(x1, x2, x3) = p(x3 | x2, x1)p(x1, x2) (2.155)
= p(x3 | x2)p(x1, x2) (2.156)
= p(x3 | x2)p(x2 | x1)p(x1). (2.157)
Para el regreso, supongamos la primera identidad. Entonces
p(x3 | x2, x1) =
p(x1, x2, x3)
p(x1, x2)
(2.158)
=
p(x3 | x2)p(x2 | x1)p(x1)
p(x2, x1)
(2.159)
=
p(x3 | x2)p(x2 | x1)p(x1)
p(x2 | x1)p(x1)
(2.160)
= p(x3 | x2). (2.161)
2. Supongamos la propiedad de Markov. Entonces
p(x1, x3 | x2) =
p(x1, x2, x3)
p(x2)
(2.162)
=
p(x1, x2, x3)
p(x1, x2)
p(x1, x2)
p(x2)
(2.163)
= p(x3 | x1, x2)p(x1 | x2) (2.164)
= p(x3 | x2)p(x1 | x2). (2.165)
29
Para el regreso, supongamos la segunda identidad. Entonces
p(x3 | x1, x2) =
p(x1, x2, x3)
p(x1, x2)
(2.166)
=
p(x1, x2, x3)
p(x1 | x2)p(x2)
(2.167)
=
p(x1, x3 | x2)
p(x1 | x2)
(2.168)
=
p(x3 | x2)p(x1 | x2)
p(x1 | x2)
(2.169)
= p(x3 | x2). (2.170)
Teorema 50. Sea {X1, X2, X3} una cadena de Markov en el espacio (Ω,F , P ),
donde cada v.a. Xi toma valores en el alfabeto X . Entonces
I(X1 : X3 | X2) = 0. (2.171)
Demostración. Por definición y por el Lema 49, segundo inciso, tenemos que
I(X1 : X3 | X2) (2.172)
= H(X1 | X2)−H(X1 | X3, X2) (2.173)
=
∑
x1,x2
p(x1, x2) log
1
p(x1 | x2)
−
∑
x1,x2,x3
p(x1, x2, x3) log
1
p(x1 | x3, x2)
(2.174)
=
∑
x1,x2,x3
p(x1, x2, x3) log
1
p(x1 | x2)
−
∑
x1,x2,x3
p(x1, x2, x3) log
1
p(x1 | x3, x2)
(2.175)
=
∑
x1,x2,x3
p(x1, x2, x3) log
p(x1 | x3, x2)
p(x1 | x2)
(2.176)
=
∑
x1,x2,x3
p(x1, x2, x3) log
p(x1, x3 | x2)
p(x1 | x2)p(x3 | x2)
(2.177)
=
∑
x1,x2,x3
p(x1, x2, x3) log(1) (2.178)
= 0. (2.179)
30 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Teorema 51. (Desigualdad del procesamiento de datos) Sea {X1, X2, X3}
una cadena de Markov en el espacio de probabilidad (Ω,F , P ), donde el es-
pacio de estados es un alfabeto X . Entonces
I(X1 : X2) ≥ I(X1 : X3). (2.180)
Demostración. Por el Teorema 25 tenemos que
I(X2, X3 : X1) = I(X2 : X1) + I(X3 : X1 | X2) (2.181)
I(X3, X2 : X1) = I(X3 : X1) + I(X2 : X1 | X3). (2.182)
Por el Teorema 50 tenemos que I(X3 : X1 | X2) = 0. Además es claro que
I(X2, X3 : X1) = I(X3, X2 : X1). Por lo tanto,
I(X1 : X3) + I(X1 : X2 | X3) = I(X1 : X2). (2.183)
Por el Corolario 36, I(X1 : X2 | X3) ≥ 0. Por lo tanto
I(X1 : X3) ≤ I(X1 : X2). (2.184)
Corolario 52. Sea (X1, X2) : Ω→ X1×X2 un vector aleatorio en (Ω,F , P ).
Sea φ : X1 → X2 función, y sea X3 = φ(X2). Entonces
I(X1 : X2) ≥ I(X1 : φ(X2)). (2.185)
Demostración. Observemos que
{ω ∈ Ω : X2(ω) = x2} = {ω ∈ Ω : (φ(X2(ω)), X2(ω)) = (φ(x2), x2)}.
(2.186)
Por lo tanto, se cumple que
p(x1 | φ(x2), x2) = p(x1 | x2), (2.187)
si y sólo si
p(φ(x2), x2, x1)
p(φ(x2), x2)
=
p(x2, x1)
p(x2)
, (2.188)
si y sólo si
p(φ(x2), x2, x1)
p(x2, x1)
=
p(φ(x2), x2)
p(x2)
, (2.189)
si y sólo si
p(φ(x2) | x2, x1) = p(φ(x2) | x2). (2.190)
Por lo tanto {X1, X2, φ(X3)} es cadena de Markov, y por el Teorema 51 se
sigue el resultado.
31
Corolario 53. Sea {X1, X2, X3} cadena de Markov en (Ω,F , P ). Entonces
I(X1 : X2 | X3) ≤ I(X1 : X2). (2.191)
Demostración. Por el Teorema 25 tenemos que
I(X1 : X2, X3) = I(X1 : X2 | X3) + I(X1 : X3) (2.192)
= I(X1 : X3 | X2) + I(X1 : X2). (2.193)
Como {X1, X2, X3} es cadena de Markov, del Teorema 50 obtenemos que
I(X1 : X3 | X2) = 0. De esto y el desarrollo anterior se sigue que
I(X1 : X2 | X3) ≤ I(X1 : X2). (2.194)
Teorema 54. (Desigualdad de Fano) Sea X : Ω→ X una v.a en el espacio
(Ω,F , P ), tal que | X |= n. Sea Y : Ω → Y v.a. en (Ω,F , P ), y definamos
X̂ := g(Y ) para alguna función g : Y → X , tales que {X, Y, X̂} es una
cadena de Markov. Definamos E : Ω→ {0, 1} como
E := I{X=X̂} =
{
0 si X 6= X̂
1 si X = X̂.
(2.195)
Es claro que E es una v.a. en (Ω,F , P ). Entonces
H(E) + log(n− 1)P (E = 0) ≥ H(X | X̂) ≥ H(X | Y ). (2.196)
A X̂ le llamamos un estimador para X, y a E le llamamos la función de
error.
Demostración. Empezaremos por la desigualdad de la izquierda. Por el Teo-
rema 18 tenemos que
H(E,X | X̂) = H(E,X, X̂)−H(X̂) (2.197)
= H(X | E, X̂) +H(E, X̂)−H(X̂) (2.198)
= H(X | E, X̂) +H(E | X̂). (2.199)
32 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
También,
H(E,X | X̂) = H(E,X, X̂)−H(X̂) (2.200)
= H(E | X, X̂) +H(X, X̂)−H(X̂) (2.201)
= H(E | X, X̂) +H(X | X̂). (2.202)
Como {E = 1} = {X = X̂}, tenemos que
P (E = 1 | X = x, X̂ = x̂) = P (X = X̂ | X = x, X̂ = x̂) (2.203)
=
{
1 si x = x̂
0 si x 6= x̂,
(2.204)
por lo cual
H(E | X, X̂) = −
∑
x∈X
∑
x̂∈X
∑
e=0,1
p(e, x, x̂) log p(e | x, x̂)
= 0.
(2.205)
Por lo tanto H(X | X̂) = H(X | E, X̂) + H(E | X̂). Además H(X | X̂) ≤
H(E) por el Teorema 38. Afirmamos que
H(X | E, X̂) ≤ log(n− 1)P (E = 0). (2.206)
33
Ahora probamos la afirmación:
H(X | E, X̂) = −
∑
x∈X
∑
x̂∈X
∑
e=1,0
p(x, e, x̂) log p(x | e, x̂) (2.207)
= −
∑
x∈X
∑
x̂∈X
p(x,E = 0, x̂) log p(x | E = 0, x̂) (2.208)
−
∑
x∈X
∑
x̂∈X
p(x,E = 1, x̂) log p(x | E = 1, x̂) (2.209)
= −
∑
x∈X
∑
x̂∈X
p(x,E = 0, x̂) log p(x | E = 0, x̂) (2.210)
= −
∑
x∈X
∑
x̂∈X
p(x, x̂ | E = 0)P (E = 0) log p(x | x̂, E = 0)
(2.211)
= −
∑
x 6=x̂
p(x, x̂ | E = 0)P (E = 0) log p(x | x̂, E = 0) (2.212)
= −
∑
x̂∈X
[∑
x 6=x̂
p(x, x̂)P (E = 0) log p(x | x̂)
]
(2.213)
=
∑
x̂∈X
p(x̂)
[
−
∑
x 6=x̂
p(x | x̂) log p(x | x̂)
]
P (E = 0). (2.214)
El término entre corchetes es menor a la entroṕıa de una v.a. en (Ω,F , P )
que toma n − 1 valores, la cuál está acotada por log(n − 1) por el Teorema
37. Por lo tanto
H(X | E, X̂) ≤
∑
x̂∈X
p(x̂)[log(n− 1)]P (E = 0) (2.215)
≤ log(n− 1)P (E = 0). (2.216)
Esto prueba la afirmación. Por lo tanto
H(X | X̂) ≤ log(n− 1)P (E = 0) +H(E). (2.217)
Esto demuestra la desigualdad de la izquierda. Para la desigualdad de la de-
recha observemos que como {X, Y, X̂} es cadena de Markov, por el Teorema
51 tenemos que
I(X : X̂) ≤ I(X : Y ). (2.218)
34 CAPÍTULO 2. CONCEPTOS FUNDAMENTALES
Recordando que I(X : Y ) = H(X)−H(X | Y ), tenemos que
H(X)−H(X | X̂) ≤ H(X)−H(X | Y ), (2.219)
es decir, H(X | X̂) ≤ H(X | Y ).
Nota 55. 1. Como H(E) ≤ 1 = log 2 por el Teorema 37
P (E = 0) ≥ H(X | Y )−H(E)
log(n− 1)
(2.220)
≥ H(X | Y )− 1
log(n− 1)
. (2.221)
2. Cuando P (E = 0) = 0 (i.e. no hay error), H(X | Y ) = 0.
Caṕıtulo 3
Propiedad de equipartición
asintótica y Tipicalidad
Definición 56. (Convergencia en probabilidad) Sean Xi : Ω → X ⊂ R con
i = 1, 2, . . . v.a.s en (Ω,F , P ), y sea X : Ω → X una v.a. en el mismo
espacio. Decimos que la sucesión {Xi}∞i=1 converge en probabilidad a X si
para toda � > 0 se cumple que
ĺım
n→∞
P (| Xn −X |> �) = 0. (3.1)
Notación 57. Consideremos las v.a.s Xi : Ω → X para i = 1, . . . , n en el
espacio (Ω,F , P ). Entonces podemos denotar por
p(X1, . . . , Xn), (3.2)
p(Xi), (3.3)
a las funciones
ω →p(X1(ω), . . . , Xn(ω)), (3.4)
ω →p(Xi(ω)). (3.5)
Teorema 58. (Propiedad de equipartición asintótica [AEP]) Sea {Xi}∞i=1
una sucesión de v.a.s independientes con valoresen el alfabeto X definidas
en (Ω,F , P ) y tales que E(X1) = E(Xi) <∞ para i = 1, 2, . . . . Entonces
− 1
n
logP (X1, . . . , Xn)→ H(X1) (3.6)
cuando n→∞.
35
36CAPÍTULO 3. PROPIEDAD DE EQUIPARTICIÓN ASINTÓTICA Y TIPICALIDAD
Demostración. Por independencia tenemos que para cada n
P (X1, . . . , Xn) = P (X1) . . . P (Xn). (3.7)
Entonces
− 1
n
logP (X1, . . . , Xn) = −
1
n
log
n∏
i=1
P (Xi) (3.8)
= − 1
n
n∑
i=1
logP (Xi)→ −E(logP (X1)) (3.9)
cuando n → ∞ en probabilidad, en virtud de la Ley débil de los grandes
números. Haciendo g(x) = − log p(x) en la definición 9 y usando la notación
57, tenemos que −E(logP (X1)) = H(X1).
Definición 59. (Cojunto t́ıpico) Sea {Xi}ni=1 una sucesión de v.a.s inde-
pendientes e idénticamente distribuidas (i.i.d) en (Ω,F , P ) con valores en
el alfabeto X . Sea H(X) su entroṕıa. El conjunto �-t́ıpico de la sucesión
X1, . . . , Xn con � > 0 es
A(n)� := {(x1, . . . , xn) ∈ X n | 2−n(H(X)+�) ≤ p(x1, . . . , xn) ≤ 2−n(H(X)−�)}.
(3.10)
Teorema 60. (Propiedades del conjunto t́ıpico) En el contexto de la defini-
ción 59, tenemos que
1. si (x1, . . . , xn) ∈ A(n)� , entonces
H(X)− � ≤ − 1
n
logP (X1, . . . , Xn) ≤ H(X) + �. (3.11)
2. P ((X1, . . . , Xn) ∈ A(n)� ) > 1− � para n suficientemente grande.
3. | A(n)� |≤ 2n(H(X)+�) para n suficientemente grande.
4. | A(n)� |≥ (1− �)2n(H(X)−�) para n suficientemente grande.
Demostración. 1. Sea (x1, . . . , xn) ∈ A(n)� . Entonces
2−n(H(X)+�) ≤ p(x1, . . . , xn) ≤ 2−n(H(X)−�), (3.12)
37
lo que implica que
−n(H(X) + �) ≤ log p(x1, . . . , xn) ≤ −n(H(X)− �), (3.13)
por lo cual
H(X)− � ≤ − 1
n
log p(x1, . . . , xn) ≤ H(X) + �. (3.14)
2. Por el Teorema 58 tenemos que dada � > 0,
1 = ĺım
n→∞
P
(
| − 1
n
logP (X1, . . . , Xn)−H(X) |≤ �
)
(3.15)
= ĺım
n→∞
P
(
− � ≤ − 1
n
logP (X1, . . . , Xn)−H(X) ≤ �
)
(3.16)
= ĺım
n→∞
P
(
2−n(H(X)+�) ≤ P (X1, . . . , Xn) ≤ 2−n(H(X)−�)
)
(3.17)
= ĺım
n→∞
P
(
(X1, . . . , Xn) ∈ A(n)�
)
. (3.18)
Por lo tanto, para n suficientemente grande,
P
(
(X1, . . . , Xn) ∈ A(n)�
)
> 1− �. (3.19)
3. Por la definición de A
(n)
� tenemos que
1 =
∑
xn∈Xn
p(x1, . . . , xn) (3.20)
≥
∑
xn∈A(n)�
p(x1, . . . , xn) (3.21)
≥
∑
xn∈A(n)�
2−n(H(X)+�) (3.22)
= 2−n(H(X)+�) | A(n)� | . (3.23)
38CAPÍTULO 3. PROPIEDAD DE EQUIPARTICIÓN ASINTÓTICA Y TIPICALIDAD
4. Por el segundo inciso, tenemos que para n grande
1− � < P
(
(X1, . . . , Xn) ∈ A(n)�
)
(3.24)
=
∑
xn∈A(n)�
p(x1, . . . , xn) (3.25)
≤
∑
xn∈A(n)�
2−n(H(X)−�) (3.26)
= 2−n(H(X)−�) | A(n)� | . (3.27)
Definición 61. (Tipicalidad conjunta) Sea (X, Y ) : Ω → X × Y un vec-
tor aleatorio en el espacio (Ω,F , P ). Al conjunto de sucesiones �-t́ıpicas
{(xn, yn)} en X n × Yn para � > 0 lo definimos como
A(n)� :=
{
(xn, yn) ∈ X n × Yn : | − 1
n
log p(xn)−H(X) |< �
| − 1
n
log p(yn)−H(Y ) |< �
| − 1
n
log p(xn, yn)−H(X, Y ) |< �
}
.
(3.28)
Teorema 62. (AEP conjunta) Sea {(Xi, Yi)}∞i=1 una sucesión de vectores
aleatorios i.i.d en (Ω,F , P ) con valores en X × Y. Denotemos H(X) :=
H(Xi), H(Y ) := H(Yi), H(X, Y ) := H(Xi, Yi) y I(X : Y ) := I(Xi : Yi) para
i = 1, 2, . . . . Sea � > 0. Entonces
1. Si (xn, yn) ∈ A(n)� , entonces
H(X)− � ≤ − 1
n
log p(xn) ≤ H(X) + � (3.29)
H(Y )− � ≤ − 1
n
log p(yn) ≤ H(Y ) + � (3.30)
H(X, Y )− � ≤ − 1
n
log p(xn, yn) ≤ H(X, Y ) + �. (3.31)
2. P ((Xn, Y n) ∈ A(n)� ) ≥ 1− � para n suficientemente grande.
39
3. | A(n)� |≤ 2n(H(X,Y )+�).
4. Sea (X̂n, Ŷ n) otro vector aleatorio, ahora con distribución p(xn)p(yn)
(es decir, X̂n es independiente de Ŷ n). Entonces
(1− �)2−n(I(X:Y )+3�) ≤ P ((X̂n, Ŷ n) ∈ A(n)� ) ≤ 2−n(I(X:Y )−3�). (3.32)
Demostración. 1. Sea (xn, yn) ∈ A(n)� . Entonces
| − 1
n
log p(xn)−H(X) | < �, (3.33)
| − 1
n
log p(yn)−H(Y ) | < �, y (3.34)
| − 1
n
log p(xn, yn)−H(X, Y ) | < �, (3.35)
es decir,
H(X)− � < − 1
n
log p(xn) < H(X) + � (3.36)
H(Y )− � < − 1
n
log p(yn) < H(Y ) + � (3.37)
H(X, Y )− � < − 1
n
log p(xn, yn) < H(X, Y ) + �. (3.38)
2. Basta probar que P ((Xn, Y n) ∈ A(n)� )→ 1 si n→∞. Por la Ley débil
de los grandes números,
− 1
n
log p(Xn)→ −E(log p(X)) = H(X) (3.39)
cuando n→∞ en probabilidad. Entonces dada δ > 0 existe n1 tal que
para toda n ≥ n1,
P
(
| − 1
n
log p(Xn)−H(X) |≥ �
)
<
δ
3
. (3.40)
De manera similar, por la Ley débil de los grandes números,
− 1
n
log p(Y n)→ −E(log p(Y )) = H(Y ), (3.41)
40CAPÍTULO 3. PROPIEDAD DE EQUIPARTICIÓN ASINTÓTICA Y TIPICALIDAD
y
− 1
n
log p(Xn, Y n)→ −E(log p(X, Y )) = H(X, Y ) (3.42)
en probabilidad. Por lo tanto, existen n2 y n3 tales que para toda
n ≥ n2,
P
(
| − 1
n
log p(Y n)−H(Y ) |≥ �
)
<
δ
3
, (3.43)
y para toda n ≥ n3,
P
(
| − 1
n
log p(Xn, Y n)−H(X, Y ) |≥ �
)
<
δ
3
. (3.44)
Sea n > máx{n1, n2, n3}, y sean
B(n)� =
{
ω ∈ Ω :| − 1
n
log p(Xn(ω))−H(X) |≥ �
}
, (3.45)
C(n)� =
{
ω ∈ Ω :| − 1
n
log p(Y n(ω))−H(X) |≥ �
}
, y (3.46)
D(n)� =
{
ω ∈ Ω :| − 1
n
log p(Xn(ω), Y n(ω))−H(X) |≥ �
}
. (3.47)
Observemos que (Xn, Y n)−1(Ω \ A(n)� ) ⊆ B(n)� ∪ C(n)� ∪D(n)� . Entonces
P ((Xn, Y n) ∈ Ω \ A(n)� ) ≤ P (B(n)� ) + P (C(n)� ) + P (D(n)� ) (3.48)
< δ. (3.49)
Por lo tanto P ((Xn, Y n) ∈ A(n)� ) ≥ 1 − δ para n grande. El resultado
se sigue haciendo δ = �.
41
3. Observemos que para n y � > 0 fijos,
1 =
∑
xn∈Xn
∑
yn∈Yn
p(xn, yn) (3.50)
≥
∑
(xn,yn)∈A(n)�
p(xn, yn) (3.51)
≥
∑
(xn,yn)∈A(n)�
2−n(H(X,Y )+�) (3.52)
=| A(n)� | 2−n(H(X,Y )+�), (3.53)
y por lo tanto
| A(n)� |≤ 2n(H(X,Y )+�). (3.54)
4. Probaremos primero la desigualdad de la derecha. Sean X̂n y Ŷ n inde-
pendientes, pero con las mismas distribuciones que Xn y Y n respecti-
vamente. Entonces
P ((X̂n, Ŷ n) ∈ A(n)� ) =
∑
(xn,yn)∈A(n)�
p(xn)p(yn) (3.55)
≤
∑
(xn,yn)∈A(n)�
2−n(H(X)−�)2−n(H(Y )−�) (3.56)
=| A(n)� | 2−n(H(X)−�)2−n(H(Y )−�) (3.57)
≤ 2n(H(X,Y )+�)2−n(H(X)−�)2−n(H(Y )−�) (3.58)
= 2−n(I(X:Y )−3�) (3.59)
por el segundo inciso y por definición de A
(n)
� . Ahora, para probar la
desigualdad de la izquierda, supongamos que n es lo suficientemente
grande para cumplir que
P ((Xn, Y n) ∈ A(n)� ) ≥ 1− �. (3.60)
42CAPÍTULO 3. PROPIEDAD DE EQUIPARTICIÓN ASINTÓTICA Y TIPICALIDAD
Entonces
1− � ≤ P ((Xn, yn) ∈ A(n)� ) (3.61)
=
∑
(xn,yn)∈A(n)�
p(xn, yn) (3.62)
≤
∑
(xn,yn)∈A(n)�
2−n(H(X,Y )−�) (3.63)
=| A(n)� | 2−n(H(X,Y )−�), (3.64)
y por lo tanto
| A(n)� |≥ (1− �)2n(H(X,Y )−�). (3.65)
Entonces para n grande se cumple que
P ((X̂n, Ŷ n) ∈ A(n)� ) =
∑
(xn,yn)∈A(n)�
p(xn)p(yn) (3.66)
≥
∑
(xn,yn)∈A(n)�
2−n(H(X)+�)2−(H(Y )+�) (3.67)
=| A(n)� | 2−n(H(X)+�)2−n(H(Y )+�) (3.68)
≥ (1− �)2n(H(X,Y )−�)2−n(H(X)+�)2−n(H(Y )+�)
(3.69)
= (1− �)2−n(I(X:Y )+3�). (3.70)
Caṕıtulo 4
Capacidad de canales
Definición 63. (Canal de comunicación discreto) Sean X y Y conjuntos
finitos (que llamaremos alfabetos de entrada y salida respectivamente). Sea
Q : X × Y → [0, 1] una función tal que para cada x ∈ X , Q(x, ·) es una
medida de probabilidad en (Y ,P(Y)). A la terna (X , Q,Y) le llamaremos
canal de comunicación discreto. A la función Q se le conoce comunmente
como kernel de probabilidad discreto.
Definición 64. (v.a.s comunicadas) Sea (X , Q,Y) un canal discreto. Sea
(X, Y ) : Ω → X → Y vector aleatorio en (Ω,F , PX,Y ). Ya observamos
(ver Nota 6) que X y Y son v.a.s, con distribuciones respectivas pX(x) =∑
x pX,Y (x, y) y pY (y) =
∑
y pX,Y (x, y). Decimos que las v.a.s X y Y están
conectadas por el canal (X , Q,Y) si y sólo si
Q(x, y) =
pX,Y (x, y)
pX(x)
(4.1)
para todo (x, y) ∈ X ×Y. Aqúı asumimos sin perder generalidad que pX(x) 6=
0 para toda x ∈ X , pues si existen elementos en el alfabeto de entrada con
probabilidad cero de ocurrencia, pueden considerarse como no pertenecientes
a dicho alfabeto. A X y a Y les llamamos variables de entrada y salida
respectivamente.
Definición 65. (Canal sin memoria discreto) Sea (X1, Y1), (X2, Y2), · · · :
Ω → X × Y una sucesión de vectores aleatorios en (Ω,F , P ). Supongamos
que para cada i = 1, 2, . . . las v.a.s Xi y Yi están conectadas por el canal
de comunicacióndiscreto (X , Q,Y). Decimos que (X , Q,Y) es un canal sin
43
44 CAPÍTULO 4. CAPACIDAD DE CANALES
memoria si para cualesquiera n entero y y1, . . . , yn ∈ Y se cumple la igualdad
P (Y1 = y1, . . ., Yn = yn | Xn = xn)
= P (Y1 = y1 | X1 = x1) . . . P (Yn = yn | Xn = xn),
(4.2)
donde Xn = (X1, . . . , Xn) y x
n = (x1, . . . , xn).
Nota 66. A partir de este punto, siempre que hablemos de un canal de
comunicación, nos estaremos refiriendo a un canal sin memoria discreto.
Definición 67. (Capacidad de un canal) Sea (X , Q,Y) un canal de comu-
nicación. Sea (X, Y ) : Ω → X × Y una función medible en (Ω,F), y consi-
deremos la familia de medidas
pX,Y (x, y) = Q(x, y)pX(x) (4.3)
definida por cada distribución de probabilidad pX en X . Aqúı tomamos pY (y) =∑
x∈X Q(x, y)pX(x) para cada pX . Definimos la capacidad C de (X , Q,Y) co-
mo
C := sup
pX
I(X;Y ), (4.4)
es decir, el supremo de I(X;Y ) vista como función de la variable pX . Obser-
vemos que esta función es acotada, pues
I(X;Y ) = H(X)−H(X | Y ) (4.5)
≤ H(X) (4.6)
≤ log(| X |). (4.7)
Teorema 68. (Propiedades de C) Sea (X , Q,Y) un canal con capacidad C,
y sean X y Y variables de entrada y salida respectivamente. Entonces
1. C ≥ 0.
2. C ≤ mı́n {log | X |, log | Y |}.
3. I(X : Y ) = D(pX(x) || py(y)) es una función continua de pX .
4. I(X : Y ) es una función cóncava de pX .
45
Demostración. 1. Por el Teorema 23, tenemos que I(X : Y ) ≥ 0. Esto
implica que
0 ≤ sup
pX
I(X;Y ) (4.8)
= C. (4.9)
2. Por los teoremas 23 y 37, tenemos que
I(X;Y ) = H(X)−H(X | Y ) (4.10)
≤ H(X) (4.11)
≤ log | X | . (4.12)
Análogamente,
I(X;Y ) = H(Y )−H(Y | X) (4.13)
≤ H(Y ) (4.14)
≤ log | Y | . (4.15)
Por lo tanto,
I(X;Y ) ≤ mı́n {log | X |, log | Y |}. (4.16)
Tomando supremo, obtenemos que
C ≤ mı́n {log | X |, log | Y |}. (4.17)
3. Observemos que
I(X;Y ) =
∑
x∈X
∑
y∈Y
pX,Y (x, y) log
pX,Y (x, y)
pX(x)pY (y)
(4.18)
=
∑
x∈X
∑
y∈Y
Q(x, y)pX(x) log
Q(x, y)pX(x)
pX(x)
∑
x∈X Q(x, y)pX(x)
(4.19)
=
∑
x∈X
∑
y∈Y
pX(x)Q(x, y) logQ(x, y) (4.20)
−
∑
x∈X
∑
y∈Y
pX(x)Q(x, y) log
(∑
x∈X
Q(x, y)pX(x)
)
. (4.21)
46 CAPÍTULO 4. CAPACIDAD DE CANALES
Esta es una función continua de pX , donde consideramos que el con-
junto V ⊂ Rn de todas las distribuciones de probabilidad en X con
la topoloǵıa euclidiana es cerrado y acotado, con n =| X |. Es decir,
pX = (p1, . . . , pn) con pi = pX(i) ≥ 0 para i = 1, . . . , n y
∑n
i=1 pi = 1.
En este caso la función es continua en un conjunto compacto V , por lo
cuál podemos escribir C = máxpX I(X;Y ).
4. Por el Teorema 16 y tenemos que
I(X;Y ) = H(Y )−H(Y | X) (4.22)
= H(Y ) +
∑
x,y
pX,Y (x, y) logQ(x, y) (4.23)
= H(Y ) +
∑
x,y
Q(x, y)pX(x) logQ(x, y) (4.24)
= H(Y ) +
∑
x,y
[Q(x, y) logQ(x, y)]pX(x). (4.25)
Por el Teorema 44, H(Y ) es convexa. Como
pY (y) =
∑
x∈X
Q(x, y)pX(x), (4.26)
pY (y) es función lineal de pX . Q es el kernel que define al canal, y por
lo tanto es una función constante respecto de pX . Por lo tanto, H(Y )
es función cóncava de pX . Por otro lado, el sumando∑
x,y
[Q(x, y) logQ(x, y)]pX(x) (4.27)
es lineal con respecto de pX , pues de nuevo el kernel Q es constante
respecto de pX por ser la función que define al canal. Esto prueba que
I(X;Y ) es función cóncava de pX .
Lema 69. Sea (Xn, Y n) : Ω → X n × Yn función medible en (Ω,F). Sea
P medida en (Ω,F) tal que las entradas de Xn, digamos X1, ..., Xn, son
independientes, y que además cumple con la definición 65. Entonces
P ((Xn, Y n)−1(xn, yn)) = Q(x1, y1) . . . Q(xn, yn)pX(x1) . . . pX(xn), (4.28)
47
donde PX ∈M y (Q,M) es un canal de comunicación para X y Y (es decir,
P es función de PX y de Q).
Demostración.
P ((Xn, Y n)−1(xn, yn)) (4.29)
=P (Y1 = y1, . . . , Yn = yn, X1 = x1, . . . , Xn = xn) (4.30)
=P (Y1 = y1. . . . , Yn = yn | X1 = x1, . . . , Xn = xn)P (X1 = x1, . . . , Xn = xn)
(4.31)
=P (Y1 = y1 | X1 = x1) . . . P (Yn = yn | Xn = xn)P (X1 = x1, . . . , Xn = xn)
(4.32)
=P (Y1 = y1 | X1 = x1) . . . P (Yn = yn | Xn = xn)pX(x1) . . . pX(xn) (4.33)
=Q(x1, y1) . . . Q(xn, yn)pX(X1) . . . pX(xn), (4.34)
donde usamos la Definición 65 en la tercera igualdad.
La prueba del Teorema General de Shannon para canales discretos sin
memoria requiere de conceptos y resultados de la Teoŕıa Ergódica que no son
tratados en este trabajo. Sin embargo, podemos probar este teorema para
una subclase de este tipo de canales:
Definición 70. (Canal Binario Simétrico de parámetro p) Sea p ∈ [0, 1].
El Caanal Binario Simétrico de parámetro p, que denotaremos BSCp, es un
canal de comunicación (X , Q,Y) tal que X = {0, 1} = Y, y
Q(1, 1) = p = Q(0, 0), (4.35)
Q(0, 1) = 1− p = Q(1, 0). (4.36)
Lema 71. (Capacidad del BSCp) La capacidad del canal BSCp es C = 1−
H(p), donde denotaremos en adelante H(p) := −p log(p)− (1−p) log(1−p).
Demostración. Sean X y Y v.a.s comunicadas por el canal BSCp. Observe-
mos que
48 CAPÍTULO 4. CAPACIDAD DE CANALES
H(Y | X) = −
∑
x,y
pX,Y (x, y) logQ(x, y) (4.37)
= −
∑
x,y
pX(x)Q(x, y) logQ(x, y) (4.38)
=
∑
x
pX(x)
[
−
∑
y
Q(x, y) logQ(x, y)
]
(4.39)
=
∑
x
pX(x)H(p) (4.40)
= H(p). (4.41)
Entonces,
I(X;Y ) = H(Y )−H(Y | X) (4.42)
= H(Y )−H(p). (4.43)
Además, si pX(x) =
1
2
para x = 0, 1, entonces
pY (y) =
∑
x
Q(x, y)pX(x) (4.44)
=
1
2
∑
x
Q(x, y) (4.45)
=
1
2
[Q(0, y) +Q(1, y)] (4.46)
=
1
2
(4.47)
para y = 0, 1. Entonces para el BSCp, si pX(x) es uniforme en {0, 1} enton-
ces pY (y) lo es. Por el Teorema 37, si pX(x) es uniforme entonces H(Y ) =
log(2) = 1. Por lo tanto, I(X;Y ) = 1 − H(p) si pX(x) es uniforme. Con-
clúımos que
máx
pX
I(X;Y ) = 1−H(p), (4.48)
pues H(p) es constante y H(Y ) está acotada por 1 y vaŕıa con pX .
49
Lema 72. (Desigualdad de Chernoff) Sea Y : Ω→ R una v.a. en (Ω,F , P )
y s ≥ 0 una constante. Entonces para todo número real a,
P (Y ≥ a) ≤ 2−saEY [2sY ], (4.49)
y
P (Y ≤ a) ≤ 2saEY [2−sY ]. (4.50)
Demostración. Probaremos primero la primera desigualdad. Sea u : R → R
definida por
u(y) :=
{
1 si y ≥ 0
0 si y ≤ 0.
(4.51)
Es claro que para s ≥ 0, u(y − a) ≤ 2s(y−a). Entonces
EY [u(Y − a)] ≤ EY [2s(Y−a)] (4.52)
= 2−saEY [2sY ]. (4.53)
Como
EY [u(Y − a)] = P (Y ≥ a) · 1 + P (Y < a) · 0 (4.54)
= P (Y ≥ a), (4.55)
tenemos que
P (Y ≥ a) ≤ 2−saEY [2sY ]. (4.56)
La segunda desigualdad se obtiene de aplicar la primera a −Y y a −a.
Definición 73. (Distancia de Hamming) Llamaremos distancia de Hamming
a la función ∆ : {0, 1}n → Z definida por
∆(x, y) :=| {i : xi 6= yi} |, (4.57)
donde x = (x1, . . . , xn), y = (y1, . . . , yn). Llamaremos Bola abierta de Ham-
ming con centro x y radio r > 0 al conjunto
B∆(x, r) := {y ∈ {0, 1}n : ∆(x, y) < r}, (4.58)
y Bola cerrada de Hamming con centro x y radio r > 0 aal conjunto
50 CAPÍTULO 4. CAPACIDAD DE CANALES
B∆(x, r) := {y ∈ {0, 1}n : ∆(x, y) ≤ r}. (4.59)
Observemos la dependencia en n de estos conceptos. Definimos el Volumen
de B∆(x, r) como
V ol(x, r) :=| B∆(x, r) |=
dre∑
j=0
(
n
i
)
. (4.60)
Lema 74. (Desigualdad de Hamming) Sea ∆ la distancia de Hamming en
{0, 1}n, y sea 0 ≤ p ≤ 1
2
. Entonces
V ol(x, np) ≤ 2nH(p). (4.61)
Demostración. Primero probaremos la siguiente afirmación:
(1− p)n
( p
1− p
)dnpe
≥ 2−nH(p). (4.62)
Para probar esto, observemos que
2−nH(p) = 2n[log(p)+log(1−p)] (4.63)
= 2log(p
n)2log((1−p)
n) (4.64)
= pn(1− p)n. (4.65)
Además, al ser dnpe ≤ n y p ≤ 1
2
, tenemos que pn ≤ pdpne y (1−p)dnpe ≤ 1.
Entonces
(1− p)n
( p
1− p
)dnpe
− 2−nH(p) = (1− p)n
( p
1− p
)dnpe
− pn(1− p)n (4.66)
=
(1− p)n
(1− p)dnpe
(pdnpe − pn(1− p)dnpe) (4.67)
≥ (1− p)n(pdnpe − pn(1− p)dnpe) (4.68)
= (1− p)n(pdnpe − pn + pn+dnpe) ≥ 0. (4.69)
Esto prueba la afirmación. Entonces podemos calcular:
51
1 = (p+ (1− p))n (4.70)
=
n∑
i=0
(
n
i
)
pi(1− p)n−i (4.71)
=
dnpe∑
i=0
(
n
i
)
pi(1− p)n−i +
n∑
i=dnpe+1
(
n
i
)
pi(1− p)n−i (4.72)
≥
dnpe∑
i=0
(
n
i
)
pi(1− p)n−i (4.73)
=
dnpe∑
i=0
(
n
i
)
(1− p)n
( p
1− p
)i
(4.74)
≥
dnpe∑
i=0
(
n
i
)
(1− p)n
( p
1− p
)dnpe
(4.75)
= (1− p)n
( p1− p
)dnpe
V ol(x, np) (4.76)
≥ 2−nH(p)V ol(x, np), (4.77)
donde la última desigualdad es cierta por la afirmación. En la segunda de-
sigualdad usamos que p
(1−p) ≤ 1. De aqúı se concluye directamente el resul-
tado.
Lema 75. Sean X1, . . . , Xn v.a.s independientes a valores en el alfabeto finito
X y con distribuciones pX1(x1), . . . , pXn(xn). Sean fi : X → R funciones para
i = 1, . . . , n. Entonces
EX
[
n∏
i=1
fi(xi)
]
=
n∏
i=1
EXi [fi(xi)], (4.78)
donde X = (X1, . . . , Xn).
Demostración. Por la independencia de X1, . . . , Xn, la distribución del vector
X es
∏n
i=1 pXi(xi). Entonces
52 CAPÍTULO 4. CAPACIDAD DE CANALES
EX
[
n∏
i=1
fi(Xi)
]
=
∑
x1,...,xn
[
n∏
i=1
fi(xi)
]
n∏
i=1
pXi(xi) (4.79)
=
n∏
i=1
[∑
xi
fi(xi)pXi(xi)
]
(4.80)
=
n∏
i=1
EXi [fi(xi)]. (4.81)
Nota 76. Si f es función real definida en la imagen de una v.a X con
distribución pX(x) y g es función real definida en la imagen de f , entonces
tenemos que
Ef(X)[g(f(X))] =
∑
i
g(i)Pf(X)(f(X) = i) (4.82)
=
∑
x
g(f(x))PX(X = x) (4.83)
= E[g(f(X))]. (4.84)
Lema 77. Si X1, . . . , Xn son v.a.s independientes con valor esperado finito
y X̂ =
∑n
i=1 Xi, entonces
EX̂ [2
sX̂ ] =
n∏
i=1
EXi [2sXi ], (4.85)
para s ∈ R.
Demostración. Aplicando el Lema 75, tenemos que
EX̂ [2
sX̂ ] = EX̂
[
n∏
i=1
2sXi
]
(4.86)
=
n∏
i=1
EXi [2sXi ]. (4.87)
Observemos que podemos cambiar EX , donde X = (X1, . . . , Xn), por EX̂ ,
pues X̂ es función de X.
53
Lema 78. Sea Y : Ω → {0, 1} v.a. tal que PY (Y = 1) = p, y PY (Y = 0) =
1− p, para p ∈ [0, 1], y sea s ∈ R. Entonces
EY [2sY ] ≤ 2p(2
s−1). (4.88)
Demostración.
EY [2sY ] = p2s + (1− p) · 1 (4.89)
= 1 + p(2s − 1) (4.90)
≤ 2p(2s−1), (4.91)
usando que 1 + x ≤ 2x, con x = p(2s − 1).
Lema 79. (Desigualdad aditiva de Chernoff) Sea X̂ =
∑n
i=1Xi con X1, . . . , Xn
v.a.s independientes que se distribuyen como Y en el Lema 78 con parámetros
p1, . . . , pn. Sea µ = EX̂ [X̂] =
∑n
i=1 pi. Entonces
PX̂(X̂ ≥ (1 + δ)µ) ≤ 2
−( δ
2
2+δ
)µ, (4.92)
para toda δ > 0.
Demostración. Tenemos que
PX̂(X̂ ≥ (1 + δ)µ) ≤ 2
−s(1+δ)µEX̂ [2
sX̂ ] (4.93)
= 2−s(1+δ)µ
n∏
i=1
EXi [2sXi ] (4.94)
≤ 2−s(1+δ)µ
n∏
i=1
2pi(2
s−1) (4.95)
= 2−s(1+δ)µ2(2
s−1)µ (4.96)
=
(
2δ
(1 + δ)1+δ
)µ
, (4.97)
tomando s = log(1 + δ), donde la primera desigualdad se da aplicando la
Desigualdad dde Chernoff (Lema 72), la primera igualdad por el Lema 77 y
la segunda desigualdad por el Lema 78. Observemos que
54 CAPÍTULO 4. CAPACIDAD DE CANALES
log
(
2δ
(1 + δ)1+δ
)µ
= µ log
(
2δ
(1 + δ)1+δ
)
(4.98)
= µ[δ − (1 + δ) log(1 + δ)] (4.99)
≤ µ
[
δ − (1 + δ)
(
δ
1 + δ
2
)]
(4.100)
= µ
(
−δ2
2 + δ
)
, (4.101)
usando que log(1 + x) ≥ x
1+x
2
. Por lo tanto,(
2δ
(1 + δ)1+δ
)µ
≤ 2−(
δ2
2+δ
)µ. (4.102)
Concluimos que
PX̂(X̂ ≥ (1 + δ)µ) ≤ 2
−( δ
2
2+δ
)µ. (4.103)
Lema 80. Sean α1, . . . , αn reales no negativos y sean p1, . . . , pn reales no
negativos tales que
∑n
i=1 pi = 1. Entonces
1. mı́ni αi ≤
∑n
i=1 piαi.
2. mı́ni αi ≤ 1n
∑n
i=1 αi.
Demostración. 1. Sea αj = mı́ni αi. Entonces
n∑
i=1
piαi − αj =
n∑
i=1
piαi −
(
n∑
i=1
pi
)
αj (4.104)
=
n∑
i=1
piαi −
n∑
i=1
piαj (4.105)
=
n∑
i=1
pi(αi − αj) (4.106)
≥ 0. (4.107)
55
2. Sea sigue del inciso anterior, con pi =
1
n
para i = 1, . . . , n.
Definición 81. (Variable de error) Consideremos el canal BSCp. Sean X1, . . . , Xn :
Ω → {0, 1} v.a.s independientes e idénticamente distribuidas en (Ω,F , PX),
donde
PX(X = x) :=
{
p si x = 0
1− p si x = 1.
(4.108)
Definimos la variable de error de BSCp como la v.a e : Ω → {0, 1}n con
distribución
Pe(e = x
n) =
n∏
i=1
PX(Xi = xi), (4.109)
donde xn = (x1, . . . , xn). Obsérvese que e depende de n.
Teorema 82. (Teorema de Capacidad de Shannon para BSCp) Para cua-
lesquiera p, ε tales que 0 ≤ p < 1
2
y 0 ≤ ε ≤ 1
2
− p y n suficientemente grande
existen δ = δ(p, ε) > 0 y
1. una función de codificación E : {0, 1}k → {0, 1}n,
2. una función de decodificación D : {0, 1}n → {0, 1}k,
donde k ≤ b(1−H(p+ ε))nc, tales que para cada m ∈ {0, 1}k se cumple
que
Pe(D(E(m) + e) 6= m) ≤ 2−δn. (4.110)
e es la v.a. de error de BSCp. La cantidad de arriba es comunmente conocida
como la Probabilidad de Error en la decodificación.
Demostración. Fijemos n, k y p. Los procedimientos que seguiremos para
encontrar a E y a D son los siguientes:
1. Para E: Sea En,k := {E : {0, 1}k → {0, 1}n}. Sea W : Ω → En,k una
v.a. en (Ω,F , PW ), donde
PW (W = E) :=
1
| En,k |
. (4.111)
56 CAPÍTULO 4. CAPACIDAD DE CANALES
Observemos que | En,k |= (2n)2
k
= 2n2
k
. Podemos asumir sin perder
generalidad que W y e son independientes. Posteriormente usaremos a
la v.a. W y al operador EW para probar la existencia de una función
E que cumple la condición del enunciado. A este procedimiento se le
conoce como ”Método Probabiĺıstico”.
2. Para D: Para cada E ∈ En,k sea DE : {0, 1}n → {0, 1}k dada por
DE(y) := arg mı́n
m
∆(y, E(m)), (4.112)
donde ∆ es la distancia de Hamming en {0, 1}n. Identificamos a las
m ∈ {0, 1}k que minimizan para una misma y (i.e los empates) en la
misma clase de equivalencia. De esta forma, al probar la existencia de E
tenemos de forma inmediata a D = DE. Observemos que esta función
defina a la v.a. DW (y) para cada y.
Ahora fijemosm ∈ {0, 1}k, y seaBW (m)0 := B∆(W (m), (p+ε)n), y para ca-
da E sea B
E(m)
0 := B∆(E(m), (p+ε)n). Analizaremos la v.a. Pe(DW (W (m)+
e) 6= m), que es función de W :
EW [Pe(DW (W (m) + e) 6= m)] (4.113)
=
∑
E
Pe(DE(E(m) + e) 6= m)PW (W = E) (4.114)
=
1
| En,k |
∑
E
Pe(DE(E(m) + e) 6= m) (4.115)
=
1
| En,k |
∑
E
∑
y∈{0,1}k
Pe(E(m) + e = y)I{y:DE(y)6=m}(y). (4.116)
Para cada E tenemos que
57
∑
y∈{0,1}k
Pe(E(m) + e = y)I{y:DE(y)6=m}(y) (4.117)
=
∑
y/∈BE(m)0
Pe(E(m) + e = y)I{y:DE(y)6=m}(y) (4.118)
+
∑
y∈BE(m)0
Pe(E(m) + e = y)I{y:DE(y)6=m}(y) (4.119)
≤ 2−ε2n +
∑
y∈BE(m)0
Pe(E(m) + e = y)I{y:DE(y)6=m}(y), (4.120)
donde la desigualdad se sigue de que I{y:DE(y)6=m}(y) ≤ 1 y de la desigual-
dad de Chernoff aditiva (Lema 79), pues
∑
y/∈BE(m)0
Pe(E(m) + e = y) = Pe(∆(E(m) + e, E(m)) > (p+ ε)n) (4.121)
= Pe(∆(e, 0) > (p+ ε)n) (4.122)
= Pe(∆(e, 0) > np(1 +
ε
p
)), (4.123)
observando que ∆(e, 0) =
∑n
i=1 Xi en Ω, donde X1, . . . , Xn son las v.a.s
de la Definición 81, y que EX̂ [
∑n
i=1Xi] = np, podemos aplicar la Cota Aditiva
de Chernoff con δ = ε
p
, y obtenemos que
Pe(∆(e, 0) > np(1 +
ε
p
)) ≤ 2
−(
ε2
p2
2+ εp
)np
(4.124)
≤ 2−ε2n, (4.125)
pues como ε ≤ 1
2
− p, tenemos que 2p ≤ 1− 2ε, y por lo tanto
58 CAPÍTULO 4. CAPACIDAD DE CANALES
ε2
p2
2 + ε
p
np =
ε2
(2p+ ε)p
np (4.126)
=
ε2n
2p+ ε
(4.127)
≥ ε
2n
1− 2ε+ ε
(4.128)
≥ ε
2n
1− 2ε+ 2ε
(4.129)
= ε2n. (4.130)
Por lo tanto,
EW [Pe(DW (W (m) + e) 6= m)] (4.131)
≤
∑
E
2−ε
2n
| En,k |
+
∑
E
∑
y∈BE(m)0
Pe(E(m) + e = y)I{y:DE(y)6=m}(y)
1
| En,k |
(4.132)
= 2−ε
2n +
∑
y∈BW (m)0
∑
E
Pe(E(m) + e = y)PW (W = E)I{y:DE(y)6=m}(y)
(4.133)
= 2−ε
2n + EW
[ ∑
y∈BW (m)0
Pe(W (m) + e = y)I{y:DW (y)6=m}(y)
]
(4.134)
≤ 2−ε2n + EW
[ ∑
y∈BW (m)0
I{y:DW (y) 6=m}(y)
]
. (4.135)
Observemos que
∑
y∈BW (m)0
I{y:DW (y)6=m}(y) =
∑
y∈{0,1}n
I{y:DW (y)6=m}∩{y:y∈BW (m)0 }. (4.136)
Entonces
59
EW
[ ∑
y∈{0,1}n
I{y:DW (y)6=m}∩{y:y∈BW (m)0 }(y)
]
(4.137)
=
∑
y∈{0,1}n
EW [I{y:DW (y)6=m}∩{y:y∈BW (m)0 } (4.138)
=
∑
y∈{0,1}n
PW (DW (y) 6= m, y ∈ BW (m)0 ) (4.139)
=
∑
y∈{0,1}n
PW
( ⋃
m′ 6=m
{DW (y) = m′} ∩ {y ∈ BW (m)0 }
)
(4.140)
≤
∑
y∈{0,1}n
∑
m′ 6=m
PW (DW (y) = m
′, y ∈ BW (m)0 ) (4.141)
=
∑
y∈{0,1}n
∑
m′ 6=m
PW (W (m
′) ∈ B∆(y, (p+ ε)n)) (4.142)
=
∑
y∈{0,1}n
∑
m′ 6=m
V ol(y, (p+ ε)n)
| En,k |
(4.143)
= 2n
∑
m′ 6=m
V ol(y, (p+ ε)n)
| En,k |
(4.144)
≤ 2n+kV ol(y, (p+ ε)n)
| En,k |
(4.145)
≤ 2n+k 2
H(p+ε)n
| En,k |
(4.146)
=
2n+k2H(p+ε)n
2n2k
(4.147)
= 2n+k+H(p+ε)n−n2
k
(4.148)
≤ 2n+k+H(p+ε)n−n2 (4.149)
= 2k−n+H(p+ε)n (4.150)
= 2k−[1−H(p+ε)]n, (4.151)
donde usamos el Lema 74 en la tercera desigualdad, y el hecho de que
PW es distribución uniforme en la sexta igualdad. Por lotanto,
60 CAPÍTULO 4. CAPACIDAD DE CANALES
EW [Pe(DW (W (m) + e) 6= m)] ≤ 2−ε
2n + 2k−[1−H(p+ε)]n. (4.152)
Por lo tanto existe una pareja (E,DE) tal que
Pe(DE(E(m) + e) 6= m) ≤ 2−ε
2n + 2k−2[1−H(p+ε)]n, (4.153)
pues podemos tomar (E,DE) que satisface
Pe(DE(E(m) + e) 6= m) = mı́n
m
Pe(DE(E(m) + e) 6= m), (4.154)
pues de esta forma el Lema 80 garantiza que
Pe(DE(E(m) + e) 6= m) ≤ EW [Pe(DW (W (m) + e) 6= m)]. (4.155)
Esto prueba el Teorema para m ∈ {0, 1}k fijo. Es decir, para cada m ∈
{0, 1}k existe una pareja (Em, DEm) tal que
Pe(DEm(E
m(m) + e) 6= m) ≤ 2−ε2n + 2k−[1−H(p+ε)]n. (4.156)
Ahora contruimos una pareja (E,DE) que sirva para toda m: Sea A el
conjunto de aquella mitad de las m ∈ {0, 1}k tales que Pe(DEm(Em(m)+e) 6=
m) es más grande. Observemos que | A |= 2k−1. Definimos E : {0, 1}k →
{0, 1}n por E(m) := Em(m), y DE : Im(E) → {0, 1}k por DE(E(m)) :=
DEm(E
m(m)), donde Im(E) ⊂ {0, 1}n es la imagen de E. Entonces para
cada m̄ ∈ {0, 1}k \ A,
Pe(DE(E(m̄) + e) 6= m̄) ≤
1
2k−1
∑
m∈A
Pe(DEm(E
m(m) + e) 6= m) (4.157)
≤ 1
2k−1
∑
m∈A
(2−ε
2n + 2k−[1−H(p+ε)]n) (4.158)
= 2−ε
2n + 2k−[1−H(p+ε)]n, (4.159)
por el Lema 80. Obsérvese que la cantidad 1−H(p + ε) es la capacidad
del canal BSCp+ε, que aproxima a BSCp si hacemos ε→ 0.
61
Nota 83. El papel que juega la distancia de Hamming en la prueba del Teo-
rema anterior es el mismo que juega el concepto de Tipicalidad en la prueba
de la versión general del Teorema de Shannon para canales discretos. Véase
[1].
62 CAPÍTULO 4. CAPACIDAD DE CANALES
Parte II
Teoŕıa de la Información
Cuántica
63
Caṕıtulo 5
Conceptos Fundamentales de la
Teoŕıa Cuántica
Notación 84. (de Dirac) En general trabajaremos con espacios de Hilbert
(complejos y finitos) con producto interior 〈 , 〉. A los elementos de este
espacio los denotaremos con el śımbolo ket, | x〉 ∈ H. El śımbolo bra 〈x |
denota al vector transpuesto conjugado de | x〉, y al producto interior en H
de | x〉 y | y〉 lo denotaremos con el bracket 〈x | y〉. Usaremos el śımbolo
| x〉〈y | para denotar tanto a la matriz que resulta de multiplicar a estos
vectores, como a su operador asosciado.
Notación 85. Sean HA y HB espacios de Hilbert. Al conjunto de operadores
lineales en HA lo denotamos por L(HA), y al conjunto de transformaciones
lineales de HA en HB lo denotamos por L(HA,HB).
Definición 86. (Base completa) Sea H un espacio de Hilbert. Decimos que
una base {| x〉}x∈X de H es completa si satisface la condición∑
x∈X
| x〉〈x |= I, (5.1)
donde I es el operador identidad en H. En el caso de los espacios de Hilbert
de dimensión finita, todas las bases ortonormales son completas.
Definición 87. (Sistema Cuántico) Un sistema cuántico A es una pareja
ordenada (HA, {| x〉}x∈X ), donde HA es un espacio de Hilbert finito de di-
mensión dA =| X |, y {| x〉}x∈X es una base ortonormal de HA. A HA se le
65
66CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
llama espacio de estados. En adelante, sólo consideraremos espacios de esta-
dos isomorfos a Cd, con d un número entero positivo, pero se puede trabajar
con espacios de Hilbert más generales.
Definición 88. (Estado puro) Sea A un sistema cuántico. Un estado puro
es un vector | φ〉 ∈ HA tal que ‖ | φ〉‖2 := 〈φ | φ〉 = 1, es decir, es un vector
de norma unitaria.
Definición 89. (Ensamble de estados) Sea pX(x) una distribiución de pro-
babilidad en el alfabeto finito X . Sea {| φx〉}x∈X un conjunto de estados en
H. A la lista
ε := {pX(x), | φx〉}x∈X (5.2)
le llamamos ensamble de estados, y en este caso decimos que el estado del
sistema es | φx〉 con probabilidad pX(x). En adelante, asumiremos que el
conjunto de estados es una base ortonormal de H.
Definición 90. (Traza) Sea A un operador en un espacio de Hilbert H. La
traza de A es la cantidad
Tr{A} :=
∑
i
〈i | A | i〉, (5.3)
donde {| i〉}i es una base ortonormal de H.
Nota 91. Es elemental ver que la traza es una función lineal en L(H).
Observemos que la traza de un operador A no depende de la base, siempre
que ésta sea ortonormal. Sea {| φj〉}j otra base ortonormal de H. Entonces
67
Tr{A} =
∑
i
〈i | A | i〉 (5.4)
=
∑
i
〈i | A
(∑
j
| φj〉〈φj |
)
| i〉 (5.5)
=
∑
i,j
〈i | A | φj〉〈φj | i〉 (5.6)
=
∑
i,j
〈φj | i〉〈i | A | φj〉 (5.7)
=
∑
j
〈φj |
(∑
i
| i〉〈i |
)
A | φj〉 (5.8)
=
∑
j
〈φj | A | φj〉. (5.9)
Nota 92. Si A, B y C son operadores en un espacio de Hilbert finito H,
entonces Tr{ABC} = Tr{CAB} = Tr{BCA}. Para probar esta afirmación,
consideremos dos bases ortonormales completas de H, digamos {| i〉} y {|
φj〉}. Entonces
Tr{ABC} =
∑
i
〈i | ABC | i〉 (5.10)
=
∑
i,j
〈i | AB | φj〉〈φj | C | i〉 (5.11)
=
∑
i,j
〈φj | C | i〉〈i | AB | φj〉 (5.12)
=
∑
j
〈φj | CAB | φj〉 (5.13)
= Tr{CAB}. (5.14)
La otra igualdad es análoga. A esta propiedad se le conoce como ciclicidad
de la Traza.
Definición 93. (Operador de densidad, o estado mezclado) Sea ε = {pX(x), |
φx〉}x∈X un ensamble finito de estados de H. El operador de densidad asos-
68CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
ciado a ε es
ρ :=
∑
x∈X
pX(x) | φx〉〈φx | . (5.15)
El operador de densidad es una generalización cuántica de la distribución de
probabilidad pX(x) en el alfabeto finito X , como ilustramos en el siguiente
teorema. Obsérvese que ρ = EX(| φX〉〈φX |).
Teorema 94. (Propiedades de ρ) Sea ρ el operador de densidad asosciado
al ensamble ε = {pX(x), | φx〉}x∈X . Entonces
1. ρ tiene traza unitaria, es decir, Tr{ρ} = 1.
2. ρ es hermitiano, es decir ρ = ρ∗, donde ρ∗ es el operador addjunto de
ρ.
3. ρ es positivo definido, es decir, 〈ψ | ρ | ψ〉 ≥ 0 para todo | ψ〉 ∈ H.
Abreviadamente, ρ ≥ 0.
Demostración. 1.
Tr{ρ} = Tr
(∑
x∈X
pX(x) | φx〉〈φx |
)
(5.16)
=
∑
x∈X
pX(x)Tr(| φx〉〈φx |) (5.17)
=
∑
x∈X
pX〈φx | φx〉 (5.18)
=
∑
x∈X
pX(x) = 1. (5.19)
2.
ρ∗ =
(∑
x∈X
pX(x) | φx〉〈φx |
)∗
(5.20)
=
∑
x∈X
pX(x)(| φx〉〈φx |)∗ (5.21)
=
∑
x∈X
pX(x) | φx〉〈φx |= ρ. (5.22)
69
3.
〈ψ | ρ | ψ〉 = 〈ψ |
(∑
x∈X
pX(x) | φx〉〈φx |
)
| ψ〉 (5.23)
=
∑
x∈X
pX(x)〈ψ | φx〉〈φx | ψ〉 (5.24)
=
∑
x∈X
pX(x) | 〈ψ | φx〉 |2≥ 0. (5.25)
Nota 95. Dado un operador ρ en H que cumple las tres propiedades del Teo-
rema 94, podemos usar la descomposición espectral de ρ (que existe porrque
ρ es hermitiano) para recuperar un ensamble ε para el cual ρ es operador de
densidad:
ρ =
∑
x∈X
λx | φx〉〈φx | . (5.26)
Es fácil ver que los eigenvalores λx son probabilidades usándo el Teorema 94:
1 = Tr{ρ} (5.27)
=
∑
x∈X
λxTr({| φx〉〈φx |) (5.28)
=
∑
x∈X
λx. (5.29)
Además,
0 ≤ 〈φx | ρ | φx〉 = λx. (5.30)
El ensamble asosciado seŕıa {λx, | φx〉}x∈X .
Definición 96. (Medición Cuántica) Sea H un espacio de estados de un
sistema cuántico. Una medición cuántica es un conjunto de operadores {Mj}j
en H tales que ∑
j
M∗jMj = IH. (5.31)
Definimos una v.a. J que toma valores en el conjunto de ı́ndices de la medi-
ción; el valor que tome ésta se interpreta como el resultado de la medición.
Definios la probabilidad del evento {J = j} como
pJ(j) := 〈φ |M∗jMj | φ〉 (5.32)
70CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
si el sistema se encuentra en un estado puro | φ〉. Al estado Mj |φ〉√
pJ (j)
se le
llama estado post-medición. Si el estado del sistema es un estado mezclado
ρ, definimos
pJ(j) := Tr{M∗jMjρ}, (5.33)
y el estado
MjρM
∗
j√
pJ (j)
es el estado post-medición.
Definición 97. (Medida a valores en operadores positvos, o POVM) Una
POVM en un espacio de Hilbert H es una colección de operadores {Λj}j en
H tales que
1. Λj ≥ 0 para toda j,
2.
∑
j Λj = IH .
Si el sistema está en un estado puro | ψ〉, la probabilidad de obtener el resul-
tado j al realizar la medición (la POVM) es
pJ(j) = 〈ψ | Λj | ψ〉. (5.34)
Si el sistema está en un estado mezclado ρ, la probabilidad de obtener el
resultado j es
pJ(j) = Tr{Λjρ}. (5.35)
El formalismo de las POVM es útil en situaciónes en las que no se hace
uso del estado post-medición, como sucede a menudo en el contexto de la
transmición de información por canales cuánticos.
Nota 98. Denotamos porD(H) al conjunto de operadores de densidad en H.
La definición 97 nos permite interpretar a los operadores de densidad como
estados del sistema, pues éstos nos ayudan a calcular las probabilidades de
que el sistema esté en un estado del ensamble asosciado. Por esta razón, los
operadores de densidad captan la idea de que en la práctica, es dif́ıcil preparar
un sistema cuántico en un estado particular con presición, y en general el
estado real del sistema sólo se conoce estad́ısticamente (según la distribución
del ensamble).
Definición 99. (Producto tensorial de vectores) Sean HA y HB espacios de
Hilbert finitos con dimensiones dA y dB respectivamente. Sean u ∈ HA y
v ∈ HB. Definimos el producto tensorial de u y v como
u⊗ v := uvT , (5.36)
71
donde vT es el vecotr transpuesto de v. En notación de Dirac,
| φ〉⊗ | ψ〉 :=| φ〉〈ψ | . (5.37)
Observemos que la operación ⊗ entre vectores cumple la relación de bilinea-
lidad, es decir, f(u, v) := u⊗ v es una función bilineal.
Definición 100. (Producto tensorial de espacios) Sean HA y HB espa-
cios de Hilbert finitos con dimensiones n y m respectivamente. Sean EA :=
{e1, . . . , en} y EB := {f1, . . . , fm} bases ortonormales para HA y HB respec-
tivamente. Consideremos el espacio vectorial
V := span{u⊗ v : u ∈ HA y v ∈ HB}. (5.38)
Podemos inducir un producto interior en este espacio como sigue:
〈u⊗ v, x⊗ y〉 := 〈u, x〉A〈v, y〉B. (5.39)
Es fácil ver que éste es un producto interior bien definido, y que el conjunto
EA⊗EB := {e1⊗ f1, . . . , en⊗ fn} es una base ortonormal para éste espacio.
Obsérvese que por bilinealidad, si EA y EB son bases completas, también lo
es EA ⊗ EB.
Definición 101. (Producto tensorial de operadores) Sean HA y HB espacios
de Hilbert finitos. Sean S ∈ L(HA) y T ∈ L(HB) operadores. Definios el
producto tensorial de S y T como la función S ⊗ T ∈ L(HA⊗HB) dada por
la relación
(S ⊗ T )(u, v) := (Su)⊗ (Tv), (5.40)
para u ∈ HA y v ∈ HB. Denotamos por D(HA ⊗HB) al conjunto de oopera-
dores de densidad en HA ⊗HB.
Nota 102. Las definiciones de producto tensorial se extienden de manera
directa a productos de n componentes. Por ejemplo, si u, v y w son vectores
finitos, podemos usar la definición de producto tensorial de dos operadores
(matrices) para definir
u⊗ v ⊗ w := (u⊗ v)⊗ w = u⊗ (v ⊗ w), (5.41)
y seguimos de manera inductiva las mismas construcciones. A los operadores
de densidad en HA ⊗HB les llamamos operadores bipartitas, a los de HA ⊗
HB ⊗HC, tripartitas, etc.
72CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
Notación 103. Cuando sea conveniente, denotaremos al producto de n es-
tados puros por
| 0〉⊗ | 1〉 ⊗ · · · ⊗ | n〉 =| 0〉 | 1〉 · · · | n〉 (5.42)
o por
| 0〉⊗ | 1〉 ⊗ · · · ⊗ | n〉 =| 01 . . . n〉. (5.43)
Además, si estamos trabajando con un espacio conjunto HA ⊗ HB, deno-
taremos frecuentemente a los estados en HA con sub́ındice correpondiente,
digamos | ψ〉A, y a los de HB por | φ〉B. Al operador de densidad | ψ〉A〈ψ |A
lo denotaremos por | ψ〉〈ψ |A, y análogamente para B. Ésta notación la ex-
tendemos a productos tensoriales finitos.
Definición 104. (Estado separable) Decimos que un operador de densidad
bipartita σAB ∈ D(HA ⊗HB) es un estado separable si se puede escribir de
la forma
σAB =
∑
x∈X
pX(x) | ψx〉〈ψx |A ⊗ | φx〉〈φx |B, (5.44)
para alguna distribción de probabilidad pX(x) y conjuntos de estados puros
{| ψx〉A} y {| φx〉B} en los sistemas A y B respectivamente. Obsérvese que
HA y HB se toman con la misma dimensión. Cuando esto sucede decimos
que σAB es un operador cuadrado.
Definición 105. (Estado Entrelazado) Deimos que un estado bipartita (cua-
drado) está entrelazado si no es separable. Esta definición (y su negación) se
extiende directamente a productos tensoriales finitos.
Definición 106. (Traza Parcial) Sea XAB un operador cuadrado en el es-
pacio de Hilbert HA ⊗HB. Sea {| i〉B} base ortonormal completa de HB. La
traza parcial de XAB sobre HB es
TrB{XAB} :=
∑
i
(IA ⊗ 〈i |B)XAB(IA⊗ | i〉B). (5.45)
De forma abreviada,
TrB{XAB} =
∑
i
〈i |B XAB | i〉B. (5.46)
Por un argumento similar al de la observación 91, es fácil ver que la tra-
za parcial es invariante bajo la elección de bases ortonormales completas.
73
La definición de TrA es completamente análoga. Esta definición se extiende
directamente a operadores cuadrados sobre un producto tensorial finito de
espacios de estados. En adelante, sólo consideraremos operadores cuadrados,
es decir, los productos tensoriales de espacios de estados serán productos
tensoriales de un número finito de copias del mismo espacio.
Lema 107. La traza parcial cumple que Tr{XAB} = TrA{TrB{XAB}} =
TrB{TrA{XAB}}.
Demostración. Sean {| i〉A} y {| j〉B} bases ortonormales completas en los
sistemas A yB. Entonces
Tr{XAB} =
∑
i,j
〈i |A 〈j |B XAB | i〉A | j〉B (5.47)
=
∑
i,j
(〈i |A ⊗IB)(IA ⊗ 〈j |B)XAB(IA⊗ | j〉B)(| i〉A ⊗ IB) (5.48)
=
∑
i
(〈i |A ⊗IB)
[∑
j
(IA ⊗ 〈j |B)XAB(IA⊗ | j〉B)
]
(| i〉A ⊗ IB)
(5.49)
= TrA{TrB{XAB}}. (5.50)
La prueba para TrB{TrA{·}} es análoga.
Definición 108. (Operador de densidad local) Sea ρAB ∈ D(HA ⊗ HB).
Definimos el los operadores locales del sistema compuesto AB (con espacio
de estados HA ⊗HB) como
ρA := TrB{ρAB} y ρB := TrA{ρAB}. (5.51)
Esta definición se extiende directamente a productos tensoriales finitos. El
concepto de operador de densidad local capta la idea de que, si se tiene un
sistema compuesto formado por varios sistemas que comparten un estado
conjunto, los estados de cada uno de ellos están directamente relacionados
con (de hecho, están en función de) el estado conjunto.
Nota 109. Es fácil ver que el operador de densidad local es de hecho un
operador de densidad en su sistema, pues
Tr{ρA} = TrA{ρA} (5.52)
= TrA{TrB{ρAB}} (5.53)
= Tr{ρAB} = 1 (5.54)
74CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
por el lema 107. Además, sea | φ〉 ∈ HA ⊗HB. Entonces
〈φ | ρA | φ〉 = 〈φ | TrB{ρAB} | φ〉 (5.55)
= 〈φ |
∑
i
(IA ⊗ 〈i |B)ρAB(IA⊗ | i〉B) | φ〉 (5.56)
=
∑
i
〈φ | (IA ⊗ 〈i |B)ρAB(IA⊗ | i〉B) | φ〉 ≥ 0 (5.57)
pues
〈φ | (IA ⊗ 〈i |B)ρAB(IA⊗ | i〉B) | φ〉 ≥ 0 (5.58)
para cada i. Finalmente, tenemos que
ρ∗A =
[∑
i
(IA ⊗ 〈i |B)ρAB(IA⊗ | i〉B)
]∗
(5.59)
=
∑
i
[ρAB(IA⊗ | i〉B)]∗(IA ⊗ 〈i |B)∗ (5.60)
=
∑
i
(IA ⊗ 〈i |B)ρ∗AB(IA⊗ | i〉B) (5.61)
=
∑
i
(IA ⊗ 〈i |B)ρAB(IA⊗ | i〉B) (5.62)
= TrB{ρAB} (5.63)
= ρA, (5.64)
pues ρ∗AB = ρAB al ser operador de densidad.
Teorema 110. (Operadores de densidad) Sean A y B sistemas cuánticos
finitos. Entonces,
1. Sean | x1〉, | x2〉 ∈ HA y | y1〉, | y2〉 ∈ HB Entonces
TrB{| x1〉〈x2 |A ⊗ | y1〉〈y2 |B} =| x1〉〈x2 | 〈y1 | y2〉. (5.65)
La iguadad análoga para TrA también es válida.
2. Sean ρA ∈ D(HA) y σB ∈ D(HB). Entonces
TrB{ρA ⊗ σB} = ρA. (5.66)
la igualdad análoga para TrA taambién es válida.
75
3. Sea X un alfabeto finito, sea pX(x) una distribución de probabilidad en
este alfabeto, y sean ρxA ∈ D(HA) y σxB ∈ D(HB) para toda x. Entonces
TrB
{∑
x
pX(x)ρ
x
A ⊗ σxB
}
=
∑
x
pX(x)ρ
x
A. (5.67)
La igualdad análoga para TrA también es válida.
4. Sean {| x〉}x∈X y {| y〉}y∈Y bases ortonormales completas de HA y
HB respectivamente, con dA =| X | y dB =| Y |. Sea p(x, y) una
distribución en X × Y, y sea
ρ =
∑
x,y
p(x, y) | x〉〈x | ⊗ | y〉〈y | . (5.68)
Entonces
TrB{ρ} =
∑
x
pX(x) | x〉〈x | . (5.69)
La igualdad análoga para TrA también es válida.
Demostración. 1. Sea {| i〉}i base ortonormal completa de HB. Entonces
TrB{| x1〉〈x2 |A ⊗ | y1〉〈y2 |B} (5.70)
=
∑
i
(IA ⊗ 〈i |B) | x1〉〈x2 |A ⊗ | y1〉〈y2 |B (IA⊗ | i〉B) (5.71)
=
∑
i
| x1〉〈x2 |A ⊗〈i |B| y1〉〈y2 | i〉B (5.72)
=| x1〉〈x2 |A ⊗
∑
i
〈i | y1〉〈y2 | i〉B (5.73)
=| x1〉〈x2 |A ⊗
∑
i
〈y1 | i〉〈i | y2〉B (5.74)
=| x1〉〈x2 |A ⊗〈y1 |
∑
i
| i〉〈i || y2〉B (5.75)
=| x1〉〈x2 |A ⊗〈y1 | y2〉B (5.76)
=| x1〉〈x2 |A 〈y1 | y2〉B. (5.77)
La prueba para TrA es análoga.
76CAPÍTULO 5. CONCEPTOS FUNDAMENTALES DE LA TEORÍA CUÁNTICA
2. Sea {| i〉}i base ortonormal completa de HB. Entonces
TrB{ρA ⊗ σB} =
∑
i
(IA ⊗ 〈i |B)ρA ⊗ σB(IA⊗ | i〉B) (5.78)
=
∑
i
ρA ⊗ 〈i | σB | i〉B