Teoria_da_Informacao_slides_de_curso_Lec

Prévia do material em texto

Curso: Teoria da Informação
Lectures: Information Theory
 H.M. de Oliveira
Departmento de Estatística, CCEN Universidade Federal de Pernambuco http://www.de.ufpe.br/~hmo/TI.html
Recife, 2017, Brazil 
Este é um curso introdutório sobre a Teoria da Informação (Shannon theory) destinado 
aos estudantes de graduação em Estatística, ministrado no Centro de Ciências Exatas e 
da Natureza (CCEN) da Universidade Federal de Pernambuco, Recife. Grosso modo, 
trata-se de uma tentativa de fornecer uma janela panorâmica focada em algumas das 
técnicas clássicas do assunto, apresentar resultados e as linhas gerais sobre algumas das 
aplicações desta potente teoria, através de uma seleção particular de tópicos. O 
conteúdo está longe de ser razoavelmente integralizado: mesmo alguns assuntos como 
criptografia ou teoria da distorção de taxa sequer foram tratados. O ponto mais relevante 
a destacar nesta apresentação, a fim de não causar expectativas frustradas ou má 
interpretação, é que a abordagem não é bem sintonizada com aquela corriqueira na 
Estatística (correlata com o rigor exigido na Matemática). Com uma formação de 
Engenharia, a visão adotada permite omitir muitas das provas, e não haver uma 
preocupação maior com o rigor. Cursos e livros de Teoria da Informação por Matemáticos 
e/ou Estatísticos costumam ser "um pouco áridos", densos e rigorosos, perdendo-se no 
formalismo -- com ênfase menor no significado, ou em interpretações. O objetivo é um 
compêndio exordial apresentando a área aos principiantes. Há um espaço particular para 
tal enfoque: espera-se que os usuários possam aproveitar ou até mesmo apreciar.
	 	 Bom uso,
	 	 !
DE- CCEN 
TEORIA DA INFORMAÇÃO 
Prof. Hélio Magalhães de Oliveira, DE 
2017.2
1
http://ufpe.academia.edu/hmdeoliveira
Bem-vindos! (1o slide)
H. Magalhães de Oliveira, DE - UFPE 
http://www.de.ufpe.br/~hmo/TI.html 
https://en.wikipedia.org/wiki/Information_theory 
http://ufpe.academia.edu/hmdeoliveira
TEORIA DA INFORMAÇÃO
Código: ET647 
carga horária: 60 h
reponsável: Hélio Magalhães de Oliveira
Objetivos: entender o significado de informação e 
entropia; compreender dois aspectos da informação: 
compressão, controle de erros.
 
Os objetivos deste curso são apresentar os princípios 
e aplicações da teoria da informação. No curso 
estuda-se como a informação é medida em termos de 
probabilidade e entropia; Como elas são usadas para 
calcular a capacidade de um canal de comunicação, 
com e sem ruído. Entender suas ligações com a 
estatística. 
http://ufpe.academia.edu/hmdeoliveira
Como interfere o acaso?
• Vida biológica (Evolução & Seleção) 
• Matéria do universo (Mecânica Quântica) 
• Informação (TI) 
• Inteligência artificial (AI) 
– alea 
 
 (tudo o que fazemos...)
http://ufpe.academia.edu/hmdeoliveira
H.M. de Oliveira (1959-) nasceu em Arcoverde, 
Pernambuco, em 1959. Ele recebeu os graus de 
Engenheiro e Mestre em Engenharia Elétrica da 
Universidade Federal de Pernambuco em 1983. Ingressou 
na UFPE como Docente em 1983, e em 1992 recebeu o 
grau de Docteur de l’École Nationale Supérieure des 
Télécommunications, Paris. Atua no DE da UFPE desde 
2015.
http://ufpe.academia.edu/hmdeoliveira
http://www.de.ufpe.br/~hmo/deOliveira.html
«O acaso é um conceito mais fundamental que a causalidade», 
 Max Born, Nobel 1954
Origens históricas e contribuições importantes:
Ludwig Boltzmann (1844-1906), físico, mostrou em 1877 
que a entropia termodinâmica (definida como a energia de um conjunto 
estatístico [como um gás] dividido pela sua temperatura: ergs / grau) está 
relacionada à distribuição estatística das configurações moleculares. Com 
crescente entropia correspondente ao aumento da aleatoriedade. Ele tornou 
este relacionamento preciso com sua famosa fórmula S=k log W em que S 
define a entropia, W é o número total de possíveis configurações 
moleculares, e k é a constante que tem o nome de Boltzmann: k=1.38x10-16 
ergs por grau centigrado. (A fórmula acima aparece como um epitáfio na 
lápide de Boltzmann). Isto é equivalente à definição das informações 
("negentropia") em um conjunto, todos cujos possíveis estados são 
equiprováveis, mas com um sinal de menos na frente (e quando o 
Logaritmo é base 2, k=1). As conexões profundas entre a Teoria da 
Informação e o ramo da física em relação à termodinâmica e à mecânica 
estatística, dependem do trabalho de Boltzmann.
http://ufpe.academia.edu/hmdeoliveira
 
 Leo Szilard (1898-1964) em 1929 identificou a entropia com 
informações. Ele formulou conceitos chave da teoria da 
informação para resolver o paradoxo termodinâmico 
conhecido como "Demônio de Maxwell" (um experimento 
sobre as moléculas de gás em uma caixa particionada) ao 
mostrar que a quantidade de informação exigida pelo 
demônio sobre as posições e as velocidades das moléculas 
era igual (negativamente) ao incremento de entropia do 
demônio.
http://ufpe.academia.edu/hmdeoliveira
 Ralph V. Hartley (1888-1970) em 1928 fundou a 

teoria da comunicação com o seu papel de 
transmissão de informações. Ele propôs que um canal 
de comunicação com largura de banda Ω durante uma 
duração T tenha um número limitado de graus de 
liberdade, ou seja, 2ΩT, e, portanto, pode comunicar 
ao máximo essa quantidade de informação. Ele 
também definiu o conteúdo de informação de um 
conjunto equiprovável com N estados possíveis como 
igual a log2N.
http://ufpe.academia.edu/hmdeoliveira
 Norbert Wiener (1894-1964) unificou a teoria da informação e 
análise de Fourier, derivando uma série de relações entre as 
duas. Ele inventou a "análise de ruído branco" de sistemas 
não-lineares e contribuiu definitivamente para modelar e 
descrever o conteúdo de informações de processos 
estocásticos conhecidos como séries temporais. Criou a área 
que chamou de cibernética e foi um dos pioneiros de modelos 
de processos estocáticos. Estudou e estabeleceu os principios 
de preditores lineares estocásticos e suavizadores.
http://ufpe.academia.edu/hmdeoliveira
 Dennis Gabor (1900-1979) cristalizou a visão de Hartley 
formulando um Princípio geral de incerteza para obter 
informações, expressando o trade-off para resolução entre 
largura de banda e tempo. (Os sinais que estão bem 
especificados no conteúdo de freqüência devem estar mal 
localizados no tempo, e aqueles que estão bem localizados no 
tempo devem ser mal especificados no conteúdo de freqüência). 
Ele formalizou o "Diagrama de Informações" para descrever 
esse trade-off fundamental e derivado A família de funções 
contínua que otimiza (minimiza) a relação de incerteza conjunta. 
Em 1974 Gabor ganhou o Prêmio Nobel de Física por seu 
trabalho em óptica de Fourier, incluindo a invenção da 
holografia.
http://ufpe.academia.edu/hmdeoliveira
Vladimir Kotelnikov (1908-2005) foi um pioneiro em 
teoria da informação e astronomia de radar. Ele é 
conhecido por descobrir, antes de Nyquist e Shannon, 
o teorema da amostragem. Ele também foi pioneiro 
no uso da teoria de sinais na modulação e comunicações. 
Foi criador da teoria da imunidade ao ruído. 
Kotelnikov esteve também envolvido em criptografia, 
provando a segurança absoluta do sistema one-time-pad.
http://ufpe.academia.edu/hmdeoliveira
 Claude Shannon (1916-2001) em 1948 escreveu o trabalho 
definitivo, clássico, na teoria da informação: A Teoria 
Matemática da Comunicação. Dividido em tratamentos 
separados para sinais, sistemas e canais de tempo contínuo e 
discreto, apresentou todos os conceitos chave que definem o 
campo. Em particular, ele provou o famoso Teorema de 
Codificação de fontes e o Teorema de Codificação de Canal 
Ruidoso. Estabeleceu todos os fundamentos de segurança de 
dados/criptografia. Criador da Eletrônica Digital, foi pioneiro 
em inteligencia artificial, em máquinas inteligentes...
http://ufpe.academia.edu/hmdeoliveira
 S. Kullback e R. A. Leibler (1951) definiram 

a entropiarelativa (também chamada de 
discriminante, ou K-L Distance.)
http://ufpe.academia.edu/hmdeoliveira
 E. T. Jaynes (1922 - 1998) desenvolveu métodos de 
entropia máxima para inferência, teste de hipóteses e 
tomada de decisão. Outros investigaram se esses princípios 
impõem limites físicos fundamentais à própria computação. 
http://ufpe.academia.edu/hmdeoliveira
 A. N. Kolmogorov (1903-1987) em 1965 propôs 
que a complexidade de uma série de dados pode ser 
definida pelo comprimento do programa binário 
mais curto para computar a sequencia. Assim, a 
complexidade dos dados é o comprimento da 
descrição mínima, e isso especifica sua 
compressibilidade máxima. A "complexidade 
Kolmogorov" K é aproximadamente igual à sua 
entropia Shannon H, unificando assim a teoria da 
complexidade descritiva e da teoria da informação.
http://ufpe.academia.edu/hmdeoliveira
 Gregory Chaitin (1947-), argentino-eua, na 
Coppe, UFRJ, contribuiu de forma definitiva 
para a teoria da informação algorítmica e a 
metamathematics, em particular um resultado 
computacional equivalente ao teorema de 
incompletude de Gödel. Ele é considerado 
um dos fundadores do que hoje se conhece 
como complexidade de Kolmogorov (ou 
Kolmogorov-Chaitin), juntamente com 
Andrei Kolmogorov e Ray Solomonoff. 
http://ufpe.academia.edu/hmdeoliveira
Claude Elwood Shannon



C. E. Shannon (1916-2001) 

IEEE S´36 - M´48 - SM´49 - F´50
Seus prêmios e títulos incluem, pelo menos, os seguintes: 
The National Medal of Science 
The Medal of honor of the IEEE 
The Harvey prize 
The Mervin J. Kelly Award 
The Morris Liebmann Memorial Award 
The Stuart Balantine Medal (of the Franklin Institute) 
The Jacquard Award 
The Harold Pender Award 
The Research Coorporation Award 
The Medal of Honor of Rice University 
John Fritz Medal 
Golden plate Award 
Kyoto prize, entre vários outros.
Obituário
http://ufpe.academia.edu/hmdeoliveira
Contribuições C.E. Shannon
• Eletrônica Digital 
• Teoria da Informação 
– hoje, uma das áreas da matemática 
• Pioneiro em 
– Computadores digitais 
– Inteligência artificial 
– Evolução genética de populações (e informação genética) 
Leiam: interview ** Assistam: juggling 
https://www.youtube.com/watch?v=pHSRHi17RKM 
http://ufpe.academia.edu/hmdeoliveira
TEORIA DA INFORMAÇÃO
Ramo da Matemática
http://ufpe.academia.edu/hmdeoliveira
Algebra (elementary linear multilinear abstract) 
Arithmetic / Number theory 
Calculus / Analysis 
Category theory 
Combinatorics 
Group theory 
Computation 
Control theory 
Differential equations / Dynamical systems 
Functional analysis 
Game theory 
Geometry (discrete algebraic analytic differential finite) 
Graph theory 
History of mathematics 
Information theory 
Lie theory 
Mathematics and art 
Mathematics education 
Mathematical logic 
Mathematical physics 
Mathematical statistics 
Numerical analysis 
Optimization 
Order theory 
Philosophy of mathematics 
mathematics education 
Probability 
Recreational mathematics 
Representation theory 
Set theory 
Statistics 
Topology 
Trigonometry 
Áreas da matemática
http://ufpe.academia.edu/hmdeoliveira
ATIVIDADES
 Grau duplo em Matemática e 
Engenharia Elétrica, aos 20 
anos.
 Tese Mestrado: A symbolic 
analysis of Relay and switching 
circuits inaugurou o uso de 
lógica boolena em circuitos.
 Tese de doutorado: An algebra 
for theoretical genetics
 Ele colheu um ganho financeiro 
considerável usando a teoria da 
informação e dos jogos. 

Ele co-desenvolveu o que agora é 
referido como o critério de Kelly para 
otimizar apostas e investimentos com 
John Kelly, Jr. no início da década de 
1950; A aplicação desta estratégia ao 
mercado de ações fez deu ganhos 
substanciais a Shannon. 
 

Fora de suas pesquisas acadêmicas, 
Shannon estava interessado em 
malabarismo, monociclo, 

e xadrez. Ele também inventou 
diversos dispositivos (gadgets). 
http://ufpe.academia.edu/hmdeoliveira
Juggling
http://www.de.ufpe.br/~hmo/shannon_juggling.mov 
http://ufpe.academia.edu/hmdeoliveira
 Inspirado pelo pioneiro de 
inteligência artificial, Marvin 
Minsky, ele projetou o que foi 
apelidado de Ultimate Machine
 Ele construiu um dispositivo que 
poderia resolver o Cubo de 
Rubik
 
https://www.youtube.com/watch?v=Maiqnr2TZks 
http://www.kugelbahn.ch/sesam_e.htm
https://www.youtube.com/watch?v=G5rJJgt_5mg
http://ufpe.academia.edu/hmdeoliveira
Playing machines
http://www2.ee.ufpe.br/codec/Programming_a_computer_for_playing_chess.shannon.062303002.pdf
1936 1997 (game over)
http://ufpe.academia.edu/hmdeoliveira
Theseus (AI)
Apresentação (link) por Shannon
http://ufpe.academia.edu/hmdeoliveira
diorama
Cyrus Field
zoetrope
Massachusetts Institute of Jugglology
http://ufpe.academia.edu/hmdeoliveira
Opinion:
 I keep asking myself: 

How would you do this? Is it possible to make a machine to 
do that? 

Can you prove this theorem?

These are my kind of problems. Not because I am going to 
do something useful. 




"My mind wanders around, and I conceive of different 
things day and night. 

Like a science-fiction writer, I'm thinking, 

What if it were like this? Or, 

Is there an interesting problem of this type? 

And I'm not caring whether someone is working on it or 
not" 
 I visualize a time when we will be to robots 

 what dogs are to humans, and I'm rooting for the machines. 
Claude Shannon
interview
http://ufpe.academia.edu/hmdeoliveira
links
http://www2.ee.ufpe.br/codec/shannon.pdf 
Obituário 
http://www2.ee.ufpe.br/codec/Shannon_interview.pdf 
Omni 
http://www2.ee.ufpe.br/codec/Programming_a_computer_for_playing_chess.shannon.
062303002.pdf Chess 
https://www.youtube.com/watch?v=sBHGzRxfeJY 
juggling 
http://www.de.ufpe.br/~hmo/shannon_juggling.mov 
juggling 
http://www.de.ufpe.br/~hmo/ClaudeElwoodShannon.html 
Biografia 
https://vimeo.com/98345492 
Paper Into Pixels 
http://www.kugelbahn.ch/sesam_e.htm 
http://www.de.ufpe.br/%7Ehmo/useless.gif 
https://www.youtube.com/watch?v=G5rJJgt_5mg 
http://ufpe.academia.edu/hmdeoliveira
�
informação, entropia e codificação de fontes
tentativas prévias...

If you can not measure it, you can not improve it. Lord Kelvin
como medir a quantidade de informação? texto, fala, imagem, vídeo...
�


Ralph V. Hartley 
 A quantidade de informação depende fundamental-
mente do número de escolhas possíveis. 
 Como na maioria das unidades de engenharia um sistema 
com base logarítmica é apropriado (ex. dB), para uma 
situação com N escolhas possíveis, ele propos: 
I=log N 
 

�
Uma tentativa similar foi proposta por Alan Turing (the ban and the 
deciban were invented by 1940): I=10 log10N decibans. 
Se você tem apenas uma única escolha, N=20, então não há nada a informar (já se sabe).
Se você tem duas escolhas possíveis, N=21, então há uma unidade a informar (qual a escolha).
Se você tem quatro escolhas possíveis, N=22, e há dois códigos para informar a escolha.
 Comunicação analógica � Comunicação Digital* 



Eletrônica analógica � Eletrônica Digital* 
Conversão a/d � d/a*
×
×
×
�
 

Até o meio do Século XX, os sistemas analógicos eram 
reconhecidos como superiores aos sistemas digital. 
Evolução: 
 Telegrafia (digital), 
 Telefonia, Rádio, TV (analógicos) 
* criadas por Shannon, hoje são padrão universal. 



A toria da informação se consolidou com um importante ramo da teoriaestatística, com um conjunto de conceitos próprios e mostrando uma 
aplicabilidade e fertilidade em muitos ramos da ciência além da teoria da 
comunicação e, na minha opinião, em todos os ramos da ciência.
�
Medida de informação 
 Definição: [Shannon, 1948] 
 Um evento aleatório E com probabilidade de ocorrência P(E) tem 
associado um conteúdo de informação 
! . 
 NB. por sugestão de Tukey, Shannon batizou a unidade por bit (bit 
de informação), sendo hoje adotada Shannon como unidade de 
medida. 
I(E) := log2 1/P(E) = − log2 P(E)
�
Unidades de medida 
Bit= binary digit 
Bit= binary unit (of information) 
 Unidade de informação 
● log tomado em base 2, Shannon 
● log tomado em base 10, Hartley 
● log neperiano em base e, Nat. 
1 bit = 1 Sh ≈ 0.693 nat ≈ 0.301 Hart.
iso https://www.iso.org/standard/31898.html
https://en.wikipedia.org/wiki/Nat_(unit)
https://en.wikipedia.org/wiki/Hartley_(unit)
https://www.iso.org/standard/31898.html
�


Semântica versus incerteza 
 Não há conotação semântica na interpretação de Shannon 
(apenas ligada à incerteza). 
Sequência binária (Bernoulli) 
 Bit 0 ou 1, de igual probabilidade, carrega -log2 (½) =1 Sh 
 Bit 0 (0.9) carrega 0.952 Sh 
 Bit 1 (0.1) carrega 3.322 Sh 
 Converter o problema em "lançamentos de Bernoulli 
equivalentes"... 
�
Eventos & Informação 
 Ouvindo Adágio de Albinoni ou Canon de Pachelbel em Ré maior pela primeira 
vez… Ou pela trilionésima!
 Assistindo a um novo filme: esperado, inesperado, detalhes mínimos…
 Jogo de futebol: Flamengo (RJ) versus Ibis (PE). Quais as chances? Se fosse 
evento certo, nem adiantaria jogar. A zebra é um resultado possível…
– Se é certo que o placar final será de 9 × 0, basta “desligar”: não 
efetuar o jogo. Para que? (A quoi bom?)
 Informação vital (sua vida dependendo dela), por exemplo, pode ter conteúdo 
muito pequeno de informação de Shannon!
 Importância do incerto, inesperado, do improvável na vida...
�
Lembranças do passado 

(algo inexistente no presente...) 
�
Qual das imagens possivelmente possui maior conteúdo 
de informação? [ordem&desordem] 
Interpretando e entendendo… 
Associe também com o conceito 
de complexidade de Kolmogorov
�
BASES PARA DEFINIÇÃO DE INFORMAÇÃO MARGINAL 
modelo: Fonte 
 

 “letras" oriundas de um alfabeto discreto, com rótulos inteiros {k} 
Considere uma fonte que produz mensagens rotuladas por {k} 
 mensagem:= vista como uma sequência aleatória de saída da fonte com 
letras de um “alfabeto fonte”. 
Fonte
�
Proposta: ! 
 informação é uma função APENAS da probabilidade da ocorrência do 
símbolo " deve ser determinada. 
Condições impostas (lembre-se dos axiomas de Kolmogorov): 
 C1) não negatividade 
 C2) evento certo não tem informação 
 C3) monotonicidade f(pk)>f(pl), se pk<pl. 
Ik = f(pk)
⇒ f( ⋅ )
f ( pk )≥0 ,se 0≤ pk ≤1
lim
pk→ 1
f (pk )= 0
�
 Muitas funções obedecem 1-3, e a ideia final vem da consideração da 
transmissão de eventos independentes (play the role of mutually 
exclusive events in Kolmogorov axioms...). 


Independência 
 Se uma mensagem k tem conteúdo de informação Ik e outra mensagem l 
independente tem conteúdo de informação Il (ex. provindo de fontes 
independentes), 
 podemos falar da mensagem conjunta k;l em que pk;l=pk.pl 
independentes Ik;l=Ik+Il ou f(pk;l)=f(pk.pl)=f(pk)+f(pl). 
�


Equação funcional de Cauchy 
 1) f(x)>f(y) se x>y>0. 
 2) f(x.y)=f(x)+f(y). 
Solução única: f(x)=k log x (qualquer base). 
para C1, k<0, Cologaritmo, como pH 
https://en.wikipedia.org/wiki/Cologarithm 
https://en.wikipedia.org/wiki/Cologarithm
�
 
 I(k):=-log2 pk =log2 1/pk 
 Shannon definiu a unidade de medida de informação (sugestão de 
Tukey) como bit 
 bit= binary unit of information 
 bit= binary digit 
fonte binária = alfabeto {0,1} 
�
 um bit pode transportar mais (ou menos) que 1 bit de informação.
 bit 0, com p(0)=1/2 bit 0 transporta I0= 1 bit 
 
 bit 1, com p(1)=1/2 bit 1 transporta I1= 1 bit. 
Mas
 bit 0, com p(0)=1/4 bit 0 transporta I0= 2 bit 
 bit 1, com p(1)=3/4 bit 1 transporta I1= 0.42 bit. 
�
Esquema mais simples de transmissão de informação: 
símbolos p-ários, cada com duração t seg. 
 --- --- --- ... --- p-1 
 --- --- --- ... --- p-2 
 --- --- --- ... --- ... 
 . . . . 
 . . . . 
 . . . . 
 --- --- --- ... --- 1 
 --- --- --- ... --- 0 
 t seg t seg ... t seg 
 <------------------------> duração total T seg. 
�


Limitação na quantidade de informação: 
tempo para transmissão de um símbolo (aumentar velocidade) 
no de níveis diferentes possíveis (potência e ruído) 
no de intervalos n=T/t 
Teorema da contagem: 
p.p.p...p =pT/t sequências distintas possíveis 
�
 Se as sequências possíveis tem a mesma probabiliade de ocorrência 
(equiprováveis), uma sequência S arbitrária tem 
p(S)=1/ pT/t => I(S)=- log2 p(S)= . 
T maior tempo transmitindo 
 t símbolos mais rápidos I 
p mais opções no alfabeto de símbolos 


=Eis a razão por que se fala tanto hoje em redes de alta velocidade 
T
t
. log2 p
t ↓
�


Lidando com probabilidades... 
dificuldade em se lidar com valores extremos de probabilidades:
 p→0 e p →1
são consequências da evolução. 
Precisamos “entender/interpretar” apenas a faixa do meio, 
para uso eficiente da sobrevivência – seleção natural.
p →1 (evento certo, ignorar a incerteza)
p → 0 (o tal do “milagre"…)
http://www.de.ufpe.br/~hmo/alguns_grandes_numeros.pdf
http://www.de.ufpe.br/~hmo/alguns_grandes_numeros.pdf
�
número estimado de Homo sapiens que já viveram no planeta =100 billion=10^11 





(Wolframalpha: World population) 
�
 Pensemos em um evento que chamamos de raro: 

algo impar, fato que só aconteceu com um único homem na história 
da humanidade:
 P(raríssimo)=10-11.
 O que diachos seria um evento de probabilidade 10-60 ? 

As pessoas, com hábito de uso de calculadoras, escrevem coisas 
assim sem ter atenção ao significado... 
�


UMA CONVERSA SOBRE O NASCER DO SOL 

E SUAS IMPLICAÇÕES
Vamos examinar o conteúdo de informação dos eventos: 
 E ={o sol nascerá amanhã pela manhã} e 

 EC={o sol não nascerá amanhã} 
 Sabemos que o evento E é praticamente um evento certo, i.e. Pr(E) =1. 
Mas de fato, não se tem Pr(E)=1. 
�
Alguns ensaios: 
usemos este link http://www.de.ufpe.br/~hmo/alguns_grandes_numeros.pdf 
a) Digamos que P(E)=1-10-30
b) Digamos que P(E)=1-10-60 
c) Digamos que P(E)=1-10-120
Em cada caso, podemos usar a expansão de Taylor
como uma boa aproximação:
log(1-x) ≈-x e � 
I(E) ≈-log (1-10-30)/log(2)=1.4427*10-30≈10-30 Sh. 
De qualquer forma, I(E) ≈ 0 Sh como esperado.
log(1 + x) ≈ x −
x2
2
+
x3
3
−
x4
4
+ ⋯
http://www.de.ufpe.br/~hmo/alguns_grandes_numeros.pdf
�
Examinemos agora o evento complementar. 

A quantidade de informação associada ao evento EC 

seria aproximadamente:
 a) -log2(10-30) =1.4427*30*ln(10) = 100 Sh
 b) -log2(10-60) =1.4427*60*ln(10) = 200 Sh
 c) -log2(10-120) =1.4427*120*ln(10) = 400 Sh
 
A “surpresa" de o sol não nascer amanhã seria praticamente 
idêntica àquela de se jogar uma moeda 400 vezes (?) seguidas e 
observar "Ca" em todos os eventos!!
�
Qual o conteúdo de informação da seguintes 
mãos de Poker: 
~1.25 Sh
~4.4 Sh
~9.0 Sh
�
Poker probabilities(veja wolframalpha)
https://en.wikipedia.org/wiki/Poker_probability 
http://www.wolframalpha.com/input/?i=poker+probabilities 
https://en.wikipedia.org/wiki/Poker_probability
http://www.wolframalpha.com/input/?i=poker+probabilities
�


Jogadas raras... 
	 A informação associada à saída de um Royal flush é cerca de 
I(royal flush) = -log2(1/649740) ~19.3 Sh 
 Interpretar Shannons de informação associado a um evento equivalente de 
sequências de variável de Bernoulli X~Ber(0.5) Next slide... 
�
Mega sena 
Distribuição hipergeométrica X~Hiper(100,6,6) 
A probabilidade de se ganhar na mega sena com um único 
volante de 6 números é P(X=6)=0,00000008%
O conteúdo de informação associado a ganhar na mega sena 
com um único volante de 6 números é, portanto, cerca de 30 Sh.
Compare isso com efetuar 30 jogadas sucessivas de uma moeda 
honesta e obter 30 caras...
�
Dennis Gabor
 Gabor provou seu princípio de incerteza aplicando para sinais 
arbitrários a mesma técnica matemática usada na dedução de 
Heisenberg-Weyl do princípio da incerteza na mecânica 
quântica. 
 O PRINCÍPIO DA INCERTEZA DE SINAIS 
 Vale citar também uma formulação para o Princípio da Incerteza de 
Heisenberg (tempo × freqüência), desenvolvida por Gabor [1946]. 

 Trata-se de uma relação entre a duração efetiva de um sinal e sua banda 
passante efetiva, obtida no contexto de sinais determinísticos. 
�
 
 

Seja f(t) um sinal de energia finita, não necessariamente real, possuindo 
transformada F(w). 
Definem-se os momentos temporais e freqüenciais pelas seguintes relações: 
 
Werner Heisenberg (1901-1976) Dennis Gabor (1900-1978)
�
Considere a seguinte analogia com a teoria das Probabilidades:
 O integrando |f(t)|2/E denotando uma densidade de energia no tempo, em 
que a energia E é um fator de normalização para que a integral da 
densidade seja unitária. 
 É usual se trabalhar com a densidade espectral de energia ψ(w)=|F(w)| " , 
cuja integral definida em dado intervalo de freqüências fornece a energia 
do sinal nesta faixa do espectro. 
2
�
 A duração (banda passante) efetiva de um sinal f(t) 
(F(w)) pode ser definida via:
 Duração rms 
 
 Banda rms
�
 Δt e Δf correspondem aos desvios padrões 

(raiz quadrada da variância), medidas clássicas de espalhamento. 
 Aplicando argumentos típicos da mecânica quântica, Gabor provou uma 
relação de incerteza do tipo:
 estabelecendo que t e f não podem ser simultaneamente definidos de 
forma exata. Os valores de Δt e Δf são freqüentemente referidos como 
largura de pulso equivalente e banda passante equivalente, 
respectivamente. 
Δt . Δf ≥ 1/2,
�
 

Claramente, α≤1 e β≤1. Sem perda de generalidade, pode-se 
considerar sinais de energia normalizada E=1. Então: 
 
 O princípio da incerteza estabelece que, fixada uma das duas 
quantidades α ou β, a outra deve ser mantida abaixo de certo valor 
máximo, dependendo do produto T.Ω. 
�
 

Fixado α, há um sinal para o qual um máximo β é obtido. Alterna-
tivamente, fixado β, a um sinal para o qual um máximo valor de α é 
atingido. Se o sinal é banda limitada em Ω, então β=1 e α<1. 
 Qual o maior valor de α, e para que função ele é atingido? 
 Em termos de otimização (f(t)↔F(w)), o problema é colocado sob a 
forma: 
 ⇔ 
�
 A resposta para sinais com limitação foi encontrada por Slepian e 
Pollack [SLE&POL 1961] e são as funções de onda prolate esferoidais. 
 Elas obedecem a equação integral (são as autofunções da transformação 
envolvendo a função " ): Sa( ⋅ )
�
Essas funções são relacionadas com soluções da equação diferencial:
 t∈ [-1,1]. 
 Considerando a possibilidade de atingir a cota inferior da 
desigualdade, a menor área de um retângulo (quantum de sinal) de 
informação seria
Δt . Δf = 1/2
�
 Gabor definiu este retângulo Δt.Δf no plano tempo-frequência de 
Fourier para ser um quantum básico da informação e chamou-o 
de um logon.
	 Assim, para medir a quantidade de informação associada a um 
sinal arbitrário, calcular-se-ia quantas unidades de logon vale a 
sua área no plano tempo × freqüência.
�


Viva a Gaussiana! 
O sinal contínuo que atinge esta cota (melhor preenchimento do 
plano t-f, mais compacto) é um pulso de formato gaussiano.
 Está em todas! 
● Vide teorema central do limite…
● Vide autofunções da transformada Fourier
● Vide capacidade de canal com ruído branco
�
Teoria da Informação é um ramo da matemática que trata de 
três conceitos básicos:
a) a medida de informação 
b) a capacidade de um canal de informação em transferir informação 
 (de um ponto ao outro) 
c) codificação como uma maneira de utilizar canais (e memórias) com 
 capacidade plena 
�
Reconhecimento do problema 
 Se a informação a ser transmitida é conhecida com exatidão e 
certeza pelo receptor, pode-se desligar o transmissor 
(desnecessário).
 Como o ruído (através da limitação em precisão) limita a 
capacidade de armazenamento ou transmissão?
 
�
Teoria Estatística da Comunicações 
 Anterior a 1940, poucos passos foram dados no 
sentido de construir uma Teoria das comunicações. 
(investigações telegráficas, Nyquist, Hartley). Após a 
II Guerra, Claude Shannon & Norbert Wiener 
estabeleceram os novos conceitos os quais continuam 
a ter impacto. “Juntas”, estas ideias estabeleceram a 
TEORIA MODERNA DAS COMUNICAÇÕES 
�


Apenas como uma referência (sem muito sentido), no Google Scholar,
um reprint do trabalho original de Shannons feita em 2001 (reprint of 1948 paper)
ACM SIGMOBILE Mobile Computing and Communications Review 5 (1), 3-55
tem mais de 100.000 citações...
Para enfatizar a relevância, vale lembrar da citação de Gergor Cantor:
In re mathematica ars proponendi questionem pluris facienda est quam solvendi 
(Na matemática, a arte de propor questões é mais relevante do que resolvê-las) 
�
ENTROPIA
	 	 
Fonte discreta de alfabeto " 
j=0 p0 I0=-log2 p0 
j=1 p1 I1=-log2 p1
... ... ...
j=J-1 pJ-1 IJ-1=-log2 pJ-1 


qual a informação média fornecida? (quanto?)
H(X) := − ∑
x∈χ
p(x)log2 p(x) .
j ∈ {0,1,2,⋯, J − 1}
�


X é v.a. discreta, X=j com probabilidade pj 
" 
 Esta é a quantidade de informação necessitada, em média, para 
remover totalmente a incerteza associada a X.
O nome entropia e o símbolo � foram emprestados da 
mecânica estatística.
𝔼{I(X = j)} =
J−1
∑
j=0
P(X = j)I(X = j) = −
J−1
∑
j=0
p( j)log2 p( j) .
H( ⋅ )
�
Entropia é uma invenção de físicos. 
Aparece na termodinâmica macroscópica como uma necessidade 
teórica: o segundo princípio da termodinâmica só expressa sua 
existência (Clausius 1854). Existe uma fórmula para sua variação 
durante algumas transformações, mas nenhuma expressão direta.

A física estatística (Boltzmann) deu novas bases, microscópicas, à 
termodinâmica e, finalmente, fornece uma expressão analítica para 
a entropia de um sistema: é o logaritmo do número de possíveis 
configurações microscópicas para o sistema.
�
Quando Shannon derivou sua famosa fórmula para definir 
informação, ele perguntou a von Neumann como deveria ser 
chamada e von Neumann respondeu: 
"Você deve chamá-la de entropia por dois motivos: primeiro 
porque isso é a fórmula aparece em mecanização estatística, 
mas segundo e mais importante, como ninguém sabe o que é 
entropia, sempre que você usar o termo, você estará em 
vantagem!”
�
A Termodinâmica destina-se a explicar e desenvolver as máquinas 
térmicas, ponto central da Revolução Industrial. 
Nesse contexto, a entropia aparece com o intuito de distinguir 
processos reversíveis e irreversíveis, estando assim intimamente 
ligada com a questão da direção da chamada “seta do tempo”.
na última metade do SéculoXX ganharam importância a noção de 
taxa de criação de entropia em sistemas dinâmicos, bem como 
surgiu o conceito de entropia não-extensiva, devido a 
Constantino Tsallis (1943- ). 
�
A VIDA E A MORTE --- LIGAÇÃO COM A TERMODINÂMICA
1a lei da termodinâmica
a energia não pode ser criada nem destruída e a energia total em 
um sistema fechado permanece a mesma (o universo é fechado 
ou aberto?)
2a lei da termodinâmica
qualquer processo real só pode prosseguir na direção de um 
aumento da ENTROPIA.
�
As ideias de Boltzmann foram exploradas por Schrödinger, o qual 
notou que alguns sistemas, como a vida, parecem desafiar a 2a 
lei da termodinâmica. 

Um organismo permanece vivo no seu estado de organização ao 
“importar” energia de fora de si e ao degradá-la para sustentar 
sua estrutura organizacional. 

Ou como disse Schrödinger, a única maneira de um sistema vivo 
permanecer vivo, longe da entropia máxima ou da morte é
“retirando continuamente entropia negativa do seu ambiente… 
portanto, o estrategema que o roganismo usa para se manter 
estacionário (baixa entropia) consiste em continuamente “sugar” 
ordenação do seu ambiente (Schödinger, 1949)”
�
Considere o seguinte texto de Feynman:
“In fact, the science of thermodynamics began with an analysis, by 
the great engineer Sadi Carnot, of the problem of how to build the 
best and most efficient engine, and this constitutes one of the few 
famous cases in which engineering has contributed to fundamental 
physical theory. Another example that comes to mind is the more 
recent analysis of information theory by Claude Shannon. These two 
analyses, incidentally, turn out to be closely related”. 
Richard Feynman – Lectures on Physics 
�
Arrow of Time 
A Seta do Tempo (Arrow of Time) é um conceito desenvolvido em 1927 
pelo astrônomo britânico Arthur Eddington envolvendo a "direção 
unidirecional" ou "assimetria" do tempo. 
Isto está diretamente ligado à lei da termodinâmica e ao conceito de entropia.
information is not simply a physical property of a message: 
it is a property of the message and your knowledgement about it R. Feynman.
�
No lançamento de uma moeda honesta, associa-se automaticamente um 
conteúdo de informação de 1 Shannon. As coisas são mais sutis: veja o exemplo 
do lanámento de uma moeda honesta com entropia de Shannons. A 
esquerda, um resultado do tipo ‘coroa, quadrante II’, enquanto que a moeda do 
lado direito resulta ‘cara, quadrante I’.


log2 8 = 3
�
EXEMPLO
X1 j p(j) X2 j p(j)
0 1/8 0 1/4
1 1/8 1 1/4
2 1/8 2 1/4
3 1/8 3 1/8
4 1/8 4 1/32
5 1/8 5 1/32
6 1/8 6 1/32
7 1/8 7 1/32
�
Adiante veremos que H(X) nos fornece um limite inferior para o 
número médio de digitos binários necessários para codificar X 

(1o Teorema de Shannon).
A entropia é máxima para eventos equiprováveis.
�
Teorema. Dado um conjunto X de possíveis ocorrências, em que 
X assume valores no alfabeto � com 
distribuição de probabilidade � , tem-se :
� ,
em que a desigualdade à direita é satisfeita sss as ocorrências 
são equiprováveis e à esquerda sss � .
prova.
�
j ∈ {0,1,2,⋯, J − 1}
{p( j)}
0 ≤ H(X) ≤ log2 J
∃j0 |p( j0) = 1
H(X) = −
J−1
∑
j=0
p( j) . log2 p( j) .
�
a) como � , logo � e � 
Se existe j0 tal que p(j0)=1, então p(j)=0 (Kolmogorov) 
Logo � 
Avaliando-se: 
 " . 
Então H(X)=0 se j0 tal que p(j0)=1. 
∀j 0 ≤ p( j) ≤ 1 −log2 p( j) ≥ 0 H(X) ≥ 0.
∀j ≠ j0
H(X) = − 1. log2 1 − ∑
j≠j0
0. log2 0
lim
ϵ→0
− ϵ log2 ϵ = lim
ϵ→0
−
log2 ϵ
1/ϵ
= lim
ϵ→0
−
−1/ϵ
−1/ϵ2
= 0
�
b) Vamos usar a desigualdade fundamental da Teoria da Informação 
� 
inspeção gráfica 
ln x { < x − 1 x > 0, x ≠ 1= x − 1 x = 1.
�
inspeção analítica 
seja � . �
y’=0 em x=1(ponto crítico). Além disso, � máximo.
y := ln(x) − x + 1 dy
dx
=
1
x
− 1
d2y
dx2
= −
1
x2
≤ ⇒
�
vamos considerar apenas os valores de j estritamente positivos.
 
 De � , segue-se � . 
 Verificando que a igualdade é verdadeira somente quando os 
eventos são equiprováveis:
� 
 Para eventos equiprováveis, p(j)=1/J para todo j, donde H(X)-
log2J=0 Q.E.D.
H(X) − log2 J ≤ 0 H(X) ≤ log2 J
H(X) − log2 J =
J−1
∑
j=0
p( j) . log2
1
p( j)J
.
�
ENTROPIA DE VARIÁVEIS ALEATÓRIAS 
Denotemos por � o valor esperado. Assim, se X ∼ p(x), o valor 
esperado da variável aleatória g(X) é 
� ,
no caso particular em que g(X)=log 1/p(x), tem-se a entropia H(X).
Lema 1. �
prova. Como � então � .
logo �
𝔼
𝔼p g(X) = ∑
x∈χ
g(x)p(x)
H(X) ≥ 0.
0 ≤ p(x) ≤ 1 log
1
p(x)
≥ 0
H(X) ≥ 0.
�
Lema 2. �
prova. mudança de base. �
Entropia binária. Bernoulli.
a entropia de X vale:
 " 
Hb(X) = (logb a)Ha(X) .
Hb(X) = (logb a)loga p .
H(X ) = − p . log p − (1 − p) . log(1 − p) := H2(p)
�
 
Exemplo.
 
�
Entropia de uma fonte: uma introdução informal
Sejam saídas independentes de uma fonte (eventos) � 
{podem ser amostras aleatórias de uma v.a. X}
definidas com símbolos sobre um alfabeto finito, � com 
cardinalidade � . Qual a probabilidade de uma sequência típica? Entenda-se 
por sequência típica TODAS as sequências possíveis, excetuando-se uma 
fração de medida nula, i.e., que tem probabilidade que tende a se anular 
quando � .
X := (X1, X2, ⋯, Xn)
𝔸 = {a1, a2, ⋯, aK}
K
n → ∞
�
Considerando uma distribuição � sobre os símbolos (independentes) da 
fonte, � .
Ora, � prob. de uma sequência
� sendo � a frequência relativa de aparecimento do 
símbolo � na sequência � .
Pela Lei dos Grandes Números, para � suficientemente grande
�
{pk}Kk=1
P(ak) = pk, ∀k
P( X) = P(X1) . P(X2) . P(X3)⋯P(Xn)
P( X) =
K
∏
k=1
P(ak)Nk, Nk
ak X := (X1, X2, ⋯, Xn)
n
p lim
n→∞
Nk = n . P(ak) = n . pk
�
Na maioria das sequências (na maioria das amostras), com � grande
� e chega-se a
� em que definiu-se a entropia da fonte � como
�
Veremos a seguir que (AES) há assintoticamente � sequências 
típicas que são praticamente equiprováveis...
n
P( X) =
K
∏
k=1
P(ak)nP(ak) = (
K
∏
k=1
ppkk )
n
p lim
n→∞
P( X) ≈ 2−nH𝔸 H𝔸
H𝔸 := −
K
∑
k=1
p(ak)log2 P(ak) = −
K
∑
k=1
pk log2 pk
Mn ≈ 2nH𝔸
�
Exemplo: entropia de fotos
entropias 7.62 Sh/pix 7.48 Sh/pix 6.92 Sh/pix 3.35 Sh/pix 1.39 Sh/pix

 ++sal e pimenta +ruído 256 níveis 16 níveis 4 níveis
O. Le Meur, Université of Rennes
�
Entropia conjunta e Entropia condicional
Definição. (entropia conjunta de duas v.a’s)
" 
então
" 
H(X, Y ) := − 𝔼 log p(X, Y ) .
H(X, Y ) = − ∑
x∈χ
∑
y∈Υ
p(x, y)log p(x, y) .
�
Definição. (entropia condicional entre v.a’s).
Se � 

" 
" 
(X, Y ) ∼ p(X, Y ),
H(Y |X ) = ∑
x∈χ
p(x)H(Y |X = x) = − ∑
x∈χ
∑
y∈Υ
p(x, y)log p(y |x)
H(Y |X) = − 𝔼 log p(Y |X) .
�
Teorema (regra da cadeia)
�
prova.
� 
logo
� 
e a prova segue.
H(X, Y ) = H(X) + H(Y |X) .
H(X, Y ) = − ∑
x∈χ
∑
y∈Υ
p(x, y) . log p(x, y) = − ∑
x∈χ
∑
y∈Υ
p(x, y) . log p(x)p(y |x)
H(X, Y ) = − ∑
x∈χ
∑
y∈Υ
p(x, y) . log p(x) − ∑
x∈χ
∑
y∈Υ
p(x, y) . log p(y |x)
�
corolário.
" 
Nota (assimetria).
	 � 

	 		 	 	 	 	 � 
H(X, Y |Z ) = H(X |Z ) + H(Y |X, Z ) .
H(X |Y ) ≠ H(Y |X )
H(X ) − H(X |Y ) = H(Y ) − H(Y |X ) .
�
Entropia relativa
A entropia relativa é uma medida de distância entre duas 
distribuições de probabilidade.
(em estatística, aparece como o valor esperado do log da razão 
de verossimilhança)
 
 Se sabemos que a “verdadeira" distribuição de probabilidade é p, 
mas usamos uma outra distribuição q (por exemplo, distribuição 
aproximada), será necessário, em média, H(p)+D(p||q) Sh para 
descrever a variável aleatória.
�
Definição. A entropia relativa (ou distância de Kullback-Leibler, 
denotada por D(p||q) ou H(p||q)) entre duas distribuições 
discretas de probabilidade p(x) e q(x) é definida por 
 " 
 nota: por convenção, aqui 0.log(0/0)=0.
Observação: em geral
 " . 
D(p ∥ q) := ∑
x∈χ
p(x) . log
p(x)
q(x)
.
D(q ∥ p) ≠ D(p∥ q)
�
Axiomas de Kinchine para entropia
Aleksandr Khinchin, Matemático russo
A definição de entropia pode ser decorrente de uma série de 
axiomas, como proposto por Kinchine (lembre-se do teorema de 
Wiener-Kinchine para avaliar a importância do autor...).
�
AX1. Para � fixo e uma distribuição discreta de probabilidades 
� , a função � é máxima no caso equiprovável, 
i.e, para � .
AX2. �
AX3. � 



(ao se juntar um evento de probabilidade nula, a entropia não se 
altera).
n
{pi}n1 H(p1, p2, ⋯, pn)
pi = 1/n, ∀n
H(X, Y ) = H(X) + H(Y |X)
H(p1, p2, ⋯, pn,0) = H(p1, p2, ⋯, pn)
�
Consequências.
Proposição. A única função � contínua com relação 
a cada das variáveis que satisfaz AX1...AX3 é da forma:
� .
Isto "justifica" a definição de entropia de Shannon.
H(p1, p2, ⋯, pn)
H(p1, p2, ⋯, pn) =
n
∑
i=1
pi log
1
pi
�


Prova.
Seja � De AX1 e AX3, 
�
Logo � .
Se � são v.a.’s independentes associadas a r 
eventos equiprováveis, AX2 implica em
� .
l(n) := H(1/n,1/n, ⋯,1/n) .
l(n) = H(1/n,1/n, ⋯,1/n,0) ≤ H(
1
n + 1
,
1
n + 1
, ⋯,
1
n + 1
= l(n + 1)
{l(n)} ↓
{X1, X2, ⋯, Xm}
H(X1, X2, ⋯, Xm) = m . l(r)
�
Mas se definimos � uma v.a. com � eventos elementares que são 
o produto cartesiano dos espaços amostrais, então
� .
� . 
Em particular, escolhendo-se � chega-se a:
� .
Y rm
l(rm) = m . l(r)
(∀s, n), l(sn) = n . l(s)
rm ≤ sn < rm+1
m
n
≤
log(s)
log(r)
<
m
n
+
1
n
�
A função � é monotona não-decrescente, e 
� , ou seja
� e isso significa que 
 �
l( . )
m . l(r) ≤ n . l(s) ≤ (m + 1) . l(r)
m
n
≤
l(s)
l(r)
<
m
n
+
1
n
l(s)
l(r)
−
log(s)
log(r)
≤
1
n
�
Para � arbitrariamente grande � e
� sendo � , pois � é decrescente.
Agora considere � discreta, associada a � ,
probabilidades racionais, � . 
n
l(s)
l(r)
−
log(s)
log(r)
= 0
l(s) = λ log(s) λ > 0 l(s)
X pk =
gk
g
∀k = 1,2,⋯, n
∀k com gk ∈ ℕ
�
Claro que � . Seja � uma v.a. discreta que depende de � , 
contendo � grupos.
� e � .
Do AX2, 
� .
Válida para � racionais e por extensão, usando a 
continuidade, para qualquer � .
g =
n
∑
k=1
gk Y X
g
H(Y |X = ak) = − log gk H(Y |X) =
n
∑
k=1
pk log gk
H(X, Y ) = log g = H(X) + H(Y |X) ⇒ H(X) = −
n
∑
k=1
pk log pk
pk = gk /g
pk
�
Definição (informação mútua entre v.a.’s). I(X;Y)
A informação mútua é a entropia relativa entre a distribuição 
conjunta p(X,Y) e a distribuição produto p(X).p(Y) (caso de 
independência) 
	 		 	 	 	 � 


Observação: �
I(X; Y ) := ∑
x∈χ
∑
y∈Υ
p(x, y) . log
p(X, Y )
p(X)p(Y )
.
I(X; Y ) = I(Y; X) .
�


Relações entre entropia e informação mútua:
mostre que
" . 
" . 
Finalmente, mostremos que 
" 
I(X; Y ) = H(X ) − H(X |Y )
I(X; Y ) = H(Y ) − H(Y |X )
I(X; Y ) = H(X ) + H(Y ) − H(X, Y ) .
�
Analise também o caso de informação mútua de X com X 
(autoinformação I(X,X)). Temos o seguinte resumo:


�
EXEMPLO
Consideremos um baralho tradicional com 52 cartas. 
Seja X ∈ {1 ,. . . , 10, J, Q, K} × {♥, ♦, ♠, ♣} 
X é o vetor aleatório do par (valor da carta, naipe) de uma carta retirada aleatoriamente 
Seja Y ∈ {♥, ♦, ♠, ♣} 
Y é a variável aleatória "ensina" qual carta Jogada. 
Se a lei sobre X for uma lei uniforme, então 
� Sha.I(X; Y ) = H(Y ) = log2 4 = 2
�
Informação Mútua entre variáveis conjuntamente Gaussianas 
Considere � duas variáveis aleatórias conjuntamente gaussianas.
X, Y
�
� 
Mostra-se que
	 	 	 	 	 � ,
em que � é o coeficiente de correlação de Pearson.
I(X1; X2) = ∫
+∞
−∞ ∫
+∞
−∞
fX1,X2(x1, x2)log2
fX1,X2(x1, x2)
fX1(x1) . fX2(x2)
dx1dx2
I(X1; X2) = −
1
2
log2(1 − ρ2)
ρ
�
Teorema (relações entre informação mútua e entropia)
 
�


Regras da cadeia 
• Regra da cadeia para entropia 
• Regra da cadeia para entropia relativa 
• Regra da cadeia para informação mútua 
�


 Teorema (regra da cadeia para a entropia)
 Sejam X1,X2,...Xn variáveis com distribuição conjunta 
p(X1,X2,...Xn). 
 " . 
 prova. 
i) para duas variáveis:
�
H(X1, X2, ⋯, Xn) =
n
∑
i=1
H(Xi |Xi−1, ⋯, X1)
H(X1, X2) = H(X1) + H(X2 |X1),
�
ii) para três variáveis:


�
então:
" 
passando ao caso n variáveis:
" . 
Q.E.D. 
H(X1, X2, X3) = H(X1) + H(X2, X3 |X1),
H(X1, X2, X3) = H(X1) + H(X2, X3 |X1) = H(X1) + H(X2 |X1) + H(X3 |X2, X1),
H(X1, X2, ⋯, Xn) = H(X1) + H(X2 |X1) + H(X3 |X2, X1) + ⋯ + H(Xn |Xn−1, ⋯, X1)
�
Definição (informação mútua condicional).
A informação mútua entre duas variáveis X e Y condicionada a Z é
�
então 
Teorema (regra da cadeia para a informação)


�
I(X; Y |Z ) := H(X |Z ) − H(X |Y, Z )
I(X1, X2, ⋯, Xn; Y ) = ∑
i=1
I(Xi; Y |Xi−1, Xi−2, ⋯, X1) .
�
prova.
" 
e, portanto, 
" 
Q.E.D.
I(X1, X2, ⋯, Xn; Y ) = H(X1, X2, ⋯, Xn) − H(X1, X2, ⋯, Xn |Y )
I(X1, X2, ⋯, Xn; Y ) =
n
∑
i=1
H(Xi |Xi−1, Xi−2, ⋯, X1) −
n
∑
i=1
H(Xi |Xi−1, Xi−2, ⋯, X1 |Y )
�
conceito de entropia de um processo estocástico
Seja � um processo estocástico estacionário.
A entropia do processo é
�
resultando em
� .
X := {Xn}∞n=1
H(X) := lim
n→∞
H(Xn |Xn−1, Xn−2, ⋯, X2, X1)
H(X) = lim
n→∞
H(X1, X2, ⋯, Xn−1, Xn)
n
�


convexidade �
 seja uma énupla no espaço vetorial euclidiano " : 
� .
�
�
�


Definição. Uma região convexa � é dita ser convexa, se 
dados dois pontos quaisquer � e dado um número real 
� , então
�
∪ & ∩
ℝn
(x1, x2, ⋯, xn)
∀ x, y ∈ ℝn, ∀c ∈ ℝ
x + y := (x1 + y1, x2 + y2, ⋯, xn + yn)
c . x := (cx1, cx2, ⋯, cxn) .
S ⊂ ℝn
α, β ∈ S
0 ≤ θ ≤ 1
θα + (1 − θ)β ∈ S .
�


interpretação
S é convexa se a reta que une quaisquer pontos interiores de S, 
tem todos os seus pontos também pertencentes a S.
exemplo:
o conjunto � de vetores de probabilidade no � é uma região 
convexa.
ℙ ℝn
�
� e � com
� �
verificação.
veremos se � é também um vetor de 
probabilidades para todo e qualquer � , �
Ora, � , logo � e
� .
α = (α1, α2, ⋯, αn) β = (β1, β2, ⋯, βn)
n
∑
i=1
αi = 1, αi ≥ 0 ∀i = 1,n .
n
∑
i=1
βi = 1, βi ≥ 0 ∀i = 1,n .
γ := θα + (1 − θ)β
θ 0 ≤ θ ≤ 1.
γk = θαk + (1 − θ)βk γk ≥ 0 ∀k = 1,n
n
∑
k=1
γk = θ
n
∑
k=1
αk + (1 − θ)
n
∑
k=1
βk = 1
�
Desigualdade de Jensen & suas consequências
 seja f uma função de valores reais definida em uma região 
convexa do espaço euclidiano.
Definição. 

Uma função f(x) é dita ser convexa � no intervalo (a,b) se para 
cada � e � , tem-se
 " . 
 ela é dita estritamente convexa se a igualdade só é atingida nos 
valores extremos de � .
∩
x1, x2 ∈ (a, b) 0 ≤ λ ≤ 1
f(λx1 + (1 − λ)x2) ≤ λf(x1) + (1 − λ)f(x2)
λ
�
�


Propriedades da funções convexas �
P1- sejam � funções convexas definidas numa região S.
Sejam � constantes reais positivas. Então a 
combinação linear de funções � também é uma função 
convexa em S.
prova.
� 
�
∩
f1, f2, ⋯, fl
c1, c2, ⋯, cl
l
∑
i=1
ci fi
α, β ∈ S,  com f convexa .
θf(α) + (1 − θ)f(β) ≤ f(θα + (1 − θ)β) .
�
Se � , dados � , 
provar que � é convexa, i.e.
�
Ora 
�
multiplicando por � constante positiva
 �
h(α) :=
l
∑
i=1
ci fi(α) ∀α ∈ S α, β,  e 0 ≤ θ ≤ 1
h( ⋅ )
θh(α) + (1 − θ)h(β) ≤ h(θα + (1 − θ)β) .
θfi(α) + (1 − θ)fi(β) ≤ fi(θα + (1 − θ)β)∀i = 1,l
ci
θci fi(α) + (1 − θ)ci fi(β) ≤ ci fi(θα + (1 − θ)β)
�
escrevendo as desigualdades para i=1,l e somando-se membro a 
membro...
� 
Q.E.D.
P2- Se f for uma função convexa � definida em um intervalo da reta 
real, então 
� (f admite um máximo).
θ
l
∑
i=1
ci fi(α) + (1 − θ)
l
∑
i=1
ci fi(β) ≤
l
∑
i=1
ci fi(θα + (1 − θ)β)
∩
∂2f
∂x2
≤ 0 ∀x ∈ I
�
Aplicação
Seja X uma v.a. discreta com entropia �
Note que � é uma combinação linear de funções 
� com coeficientes reais positivos.
Examinando: � � 
�
H(X) = −
K−1
∑
k=0
pk log2 pk .
H( ⋅ )
h(pk) := − pk log2 pk
h(pk) := − pk log2 pk ⇒
∂h(pk)
∂pk
= −
∂
∂pk
pk . ln pk
ln 2
�
donde �
como � , usando � , � ou seja, 
� é � Q.E.D.
∂2h(pk)
∂p2k
= −
1
ln 2
.
∂
∂pk
{1 + ln pk} = − 1ln 2 .
1
pk
0 ≤ pk ≤ 1 pk ≠ 0
∂2h
∂p2k
≤ 0,
H(X) =
K−1
∑
k=0
h(pk) ∩
�
Teorema. se uma funçãotem segunda derivada que é não-
negativa (positiva) no intervalo, então a função é convexa 
(estritamente convexa).
prova. Usando a expansão de Taylor em torno de um ponto 
interno do intervalo 
�
sendo x* entre x0 e x.
f(x) = f(x0) + f′�(x0)(x − x0) +
f′�′�(x*)
2
(x − x0)2,
�
Por hipótese, f’’(x0)>0 e assim o último termo é não negativo para 
qualquer valor de x no intervalo.
Seja �
 e avaliando a expressão no ponto x=x1, e em x=x2 

" 
" 
 combinando as duas expressões (eq1� e eq2 � ), o 
resultado segue. Q.E.D. 
x0 = λx1 + (1 − λ)x2
f(x1) ≥ f(x0) + f′ �(x0)(1 − λ(x1 − x2)) .
f(x2) ≥ f(x0) + f′ �(x0)(λ(x1 − x2)) .
* λ * (1 − λ)
�
 Teorema (Desiguladade de Jensen). 

Se f é uma função convexa e X é uma variável aleatória, então
� .
OBS. se a função for estritamente convexa, então
� com probabilidade 1.
prova.
por indução. Para distribuição com valores não nulos em apenas 
2 pontos, � .
𝔼f(X) ≥ f(𝔼X)
𝔼f(X) > f(𝔼X)
p1 f(x1) + p2 f(x2) ≥ f(p1x1 + p2x2)
�


Suponha que o teorema é verdadeiro para k-1 pontos de massa 
na distribuição. Vamos mostrar que também será para k pontos.

 
 
 
em que 
Q.E.D.
�
Teorema (desigualdade de informação). 
Sejam p(x), q(x) duas distribuições discretas de probabilidade.
 Então: � com igualdade iff � . 
 prova. 
Seja � o suporte de p(x). Então:
 " 

 e portanto, via desigualdade de Jensen:

� 

(a condição sss deve ser verificada...)	 	 Q.E.D. 
D(p ∥ q) ≥ 0 p(x) = q(x)∀x
A := {x |p(x) > 0}
−D(p ∥ q) = − ∑
x∈A
p(x)log
p(x)
q(x)
∑
x∈A
p(x)log
q(x)
p(x)
≤ log∑
x∈A
p(x) .
q(x)
p(x)
≤ log∑
x∈A
q(x) = log 1 = 0
�


Corolário (não-negatividade da informação mútua).
Para quaisquer duas variáveis aleatórias X e Y,
� ,
com igualdade sss X e Y são independentes.
prova.
� , com igualdade apenas quando 
p(x,y)=p(x).p(y).
corolário. � ,
com igualdade sss as v.a.’s X e Y são condicionalmente independentes 
de Z.
I(X; Y ) ≥ 0
I(X; Y ) = D(p(x, y) | |p(x) . p(y)) ≥ 0
I(X; Y |Z) ≥ 0
�


Teorema (já provado; uma prova alternativa). A entropia de uma 
v.a. X é máxima para variável uniformemente distribuída,
� .
prova.
seja � a distribuição uniforme e p(x) outra arbitrária.
� 

Claro que D é não-negativa, donde o resultado.
� . Q.E.D.
H(X) ≤ log | χ |
u(x) :=
1
| χ |
D(u | |p) = ∑ p(x)log
p(x)
u(x)
= log | χ | − H(X ) .
0 ≤ D(p ∥ u) = log | χ | − H(X)
�


Teorema (informação não machuca ninguém). 
 � , com igualdade sss X e Y são independentes.
prova.
Decorre de � Q.E.D.
Teorema (cota da entropia por independência).
�
com igualdade sss todos os Xi's são mutuamente independentes.
H(X |Y ) ≤ H(X)
0 ≤ I(X; Y ) = H(X) − H(X |Y )
H(X1, X2, ⋯, Xn) ≤
n
∑
i=1
H(Xi)
�
prova.
�
com igualdade atingida na independência. Q.E.D.
H(X1, X2, ⋯, Xn) =
n
∑
i=1
H(Xi |Xi−1, ⋯, X1) ≤
n
∑
i=1
H(Xi)
�
DESIGUALDADE DE PROCESSAMENTO DE DADOS
X, Y e Z formam um cadeia markoviana nesta ordem 
( � ) se a distribuição condicional de Z depende apenas 
de Y e é independente condicionalmente em X.
Definição. Cascata markoviana
Conjunto de v.a.’s X,Y, Z com H(Z|X,Y)=H(Z|Y).
A incerteza sobre Z conhecida apenas Y em nada altera pelo 
conhecimento suplementar de X, pois que Z só depende de (X,Y) 
por intermédio de Y.
X → Y → Z
�
Proposição. �
A igualdade (cascata markoviana) ocorre sss
� com �


Prova. 
�
 = �
isto pode ser escrito como:
H(Z |X, Y ) ≤ H(Z |Y ) .
P(Z |X, Y ) = P(Z |Y ), ∀x, y, z p(x, y, z) ≠ 0.
H(Z |X, Y ) − H(Z |Y ) = 𝔼 {−log P(Z |X, Y ) + log P(Z |Y )}
∑
x
∑
y
∑
z
P(x, y, z) log
P(Z |Y )
P(Z |X, Y )
.
�
=�
o somatório em z é uma entropia relativa � , logo não 
negativa.
Então � Q.E.D.
Corolário. Uma condição necessária e suficiente para que X,Y,Z 
forme uma cadeia markoviana é que I(X,Z |Y)=0.
∑
x
∑
y
P(x, y)∑
z
P(Z |X, Y ) . log
P(Z |Y )
P(Z |X, Y )
.
D( ⋅ )
H(Z |X, Y ) − H(Z |Y ) ≥ 0
�
O seguinte teorema (des igualdade fundamenta l de 
processamento de dados) prova que nenhum procedimento 
sobre Y, de natureza determinística ou aleatória, pode 
aumentar a informação que Y contém sobre X.
Teorema. Se � , então � .
prova:
Pela regra da cadeia, �
e também �
Como X e Z são condicionalmente independentes dado Y, 
� 

X → Y → Z I(X; Y ) ≥ I(X; Z)
I(X; Y, Z) = I(X; Z) + I(X; Y |Z)
I(X; Y, Z) = I(X; Y ) + I(X; Z |Y ) .
I(X; Z |Y ) = 0.
�
Lembrando a não-negatividade � temos:
� 
Igualdade sss � Q.E.D.
Corolário. Se Z=g(Y), tem-se � 
I(X; Y |Z) ≥ 0,
I(X; Y ) ≥ I(X; Z)
I(X; Y |Z) = 0.
I(X; Y ) ≥ I(X; g(Y ))
�
Algumas outras definições de entropia em TI
entropia de Rényi
Alfréd Rényi, matemático húngaro 
"Um matemático é um dispositivo que transforma café em teoremas.",
A entropia de Rényi de ordem , é definida como
 com ≥0 e ≠1
α
Hα(X ) :=
1
1 − α
log (
n
∑
i=1
pαi ) α α
�
entropia binária de Rényi (compare com a entropia H2)
�
casos limites
.
 (entropia de Shannon)
 (min-entropy)
lim
α→0
Hα(X ) = H0(X ) = max-entropy(X ) = log2 ∥ X ∥
lim
α→1
Hα(X ) = H(X )
lim
α→∞
Hα(X ) = H∞(X ) = min
i
(−log2 pi)
�
Examinemos a aproximação para a entropia de Shannon.
.
Seja . 
Logo . Mas e 
podemos usar o desenvolvimento em série de Taylor:
Hα(X) :=
1
1 − α
log (
n
∑
i=1
pαi )
α = 1 − ϵ
Hα(X) :=
1
ϵ
log2 (
n
∑
i=1
p1−ϵi ) p1−ϵi = pip−ϵi
p−ϵi = exp[−ϵ ln(pi)] = 1 − ϵ ln(pi) + O(ϵ
2) .
�
Tem-se então
.
Separando os termos
, donde
n
∑
i=1
p1−ϵi = ∑
i
pi [1 − ϵ ln(pi) + O(ϵ2)]
n
∑
i=1
p1−ϵi = 1 − ϵ∑
i
pi [ln(pi) + O(ϵ)]
log2 (
n
∑
i=1
p1−ϵi ) = 1ln 2 ln{1 − ϵ∑i pi[ln(pi) − O(ϵ)]}
�
ou, finalmente,
.
Dividindo por e passando ao limite,
.
Q.E.D.
log2 (
n
∑
i=1
p1−ϵi ) = − ϵ 1ln 2 ∑i pi ln(pi) + O(ϵ
2)
ϵ
lim
α→1
Hα(X) = −
1
ln 2 ∑
i
pi ln(pi) = ∑
i
pi log(pi) = H(X)
�
entropia de von Neumann
János Neumann, gênio Húngaro-Americano
� ,
definida em mecânica quântica! 
� é a matriz de densidade e � denota o traço da matriz
S := − tr (ρ ln ρ)
ρ tr( ⋅ )
�
entropia de Tsallis (1988)
Constantino Tsallis, matemático grego 
 
� .
q real, chamado de índice entrópico.
No limite � , transforma-se na entropia de Boltzmann.
Sq(pi) :=
k
q − 1 (1 − ∑i p
q
i )
q → 1
�
A Entropia diferencial de Shannon
Shannon também lidou com o caso contínuo, propondo a 
definição de entropia diferencial
abordagem heurística: X, com densidade de probabilidade �
Separação com uma partição.
�
fX(x)
H([X]π) = −
+∞
∑
j=−∞
fX(xj)Δxj . log2[ fX(xj)Δxj]
�
�
no limite de refinamento da partição:
� .
o 2o termo diverge e não tem sentido físico.
= −
+∞
∑
j=−∞
fX(xj) . log2[ fX(xj)] +
+∞
∑
j=−∞
fX(xj) . log2[
1
Δxj
] . Δxj
H(X) = − ∫
+∞
−∞
fX(x) log2 fX(x)dx + ∫
+∞
−∞
fX(x) log2{
1
dx
}dx
�
Definição. A entropia diferencial de Shannon de uma variável 
aleatória X contínua com densidade de probabilidade � é
� .
Notas:
a) não é invariante a uma transformação afim
b) pode resultar em quantidade negativas (valores negativos)
fX(x)
H(X) := − ∫
+∞
−∞
fX(x) log2 fX(x)dx = 𝔼 − log fX(x)
�
Generalizando: Definir uma informação mútua no caso contínuo:
� .
Modernamente, esta definição é estabelecida através da derivada 
de Radon-Nikodym:
� .
****************************************************************************
I(X; Y ) := − ∫
+∞
−∞ ∫
+∞
−∞
fX,Y(x, y) log2
fX,Y(x, y)
fX(x) . fY(y)
dxdy
H(X) := 𝔼 − log ( dμXdμ )
�
uma tentativa de redefinição da entropia no caso contínuo
Uma proposta para entropia de "de oliveira” (tentativa)
�
a ideia não é particionar o intervalo � da abscissas, 
como na integral de Riemann, mas sim as ordenadas, como 
ocorre na integral de Lebesgue. O que interessa são os pontos 
em que � assume valores maiores que a unidade, sendo 
associados a um conteúdo de informação “negativo”.
Note que há um isomorfismo (one-to-one) entre os intervalos:
� via o mapeamento � . 
HdeO(X) := − ∫{x|fX(x)≤1} fX(x) log2 fX(x)dx− ∫{x|fX(x)>1}
1
fX(?)
log2
1
fX(?)
d ( 1x )
(−∞, + ∞)
fX(x)
[0,1], (1, + ∞) ⊂ ℝ+
1
x
← x
�
Estatística Suficiente
a desigualdade de processamento de dados em TI está ligada ao 
conceito de estatística suficiente.
Seja � uma família de distribuições discretas indexada por 
um parâmetro � . Seja X uma amostra desta família.
Seja T(X) uma estatística. Então: � donde
� .
Se a igualdade é atingida, nenhuma informação é perdida.
{fθ(x)}
θ
θ → X → T(X),
I(θ; T(X)) ≤ I(θ; X)
�
Definição. Uma estatística T(X) é dita ser uma estatística 
suficiente relativa à família � se X é independente de � 
dado T(X) para qualquer distribuição sobre � .
� forma uma cascata markoviana.
Estatística suficiente preserva a informação mútua...
Aqui segue também o conceito de estatística suficiente mínima ... 

(não apresentado, vide livro texto)
{fθ(x)} θ
θ
θ → T(X) → X
�


Aproximação de coeficientes binomiais
Para � , tomando a fração � ,
� em que
�
Pode ser usada a cota
�
0 < k < n q := k /n
2nH2(q)
n + 1
≤ (nk) ≤ 2nH2(q)
H2(q) := − q log2 q − (1 − q)log2(1 − q)
( nλn) ≈ 2nH2(λ)[1−ϵ(n)]
�


Fórmula de Stirling e entropia de Shannon 


A distribuição de Poisson é totalmente caracterizada pelo parâmetro � (que é 
igual a sua média e sua variância): � 
λ
P(N ) =
λN
N!
e−λ
�
Para N suficientemente grande, esta distribuição tende para uma normal de 
mesma média e variância (ver figura para � =15). 
Podemos então escrever � para N perto da 
média � . Em particular para N=� , obtém-se: � , ou seja, a 
fórmula de Stirling � .
Ainda para N suficientemente grande, tomando-se o logaritmo, deriva-se:


� .
� 
λ
λN
N!
e−λ ≈
1
2πλ
exp (− −(N − λ)
2
2λ )
λ λ
NN
N!
e−N ≈
1
2πN
N! ≈ NN exp (−N ) 2πN
log2(N!) = N log2 N − N + 0.5 log2(2Nπ) ≈ N . log2 N − N
log2(N!) ≈ N . log2 N
�
Modelos para Fontes de Texto
1. Alfabetos
	 conjunto de letras maiúsculas A,B,C,D,E,...,X,Y,Z
	 
	 conjunto de letras e numerais	A,B,C,D,...,Y,Z,0,1,2,...9
	 conjunto de maiúsculas, minúsculas, espaço, pontuação
	 conjunto A,T,C,G
	 conjunto de palavras do 
	 	 	 	 	 Grande dicionário Houaiss 270.000 verbetes
	 ...
�
n-gramas 
� � 
� 		 	 � 
� 
digramas 		 	
� 
trigramas
� 
...
A = {a1, a2, a3, ⋯, am−1} ∥ A ∥= m
ℤm := {0,1,2,⋯, m − 1} ∥ ℤm ∥= m
A ↔ ℤm
A2 = A × A = {a0a0, a0a1, ⋯, a0am−1, ⋯, am−1am−1}
A3 = A × A × A = {a0a0a0, a0a0a1, ⋯, a0a0am−1, ⋯, am−1am−1am−1}
�
mensagens (textos) são n-gramas sobre � � 
A saída da fonte é modelada via um processo estocástico discreto, 
uma sequência de v.a’s contendo elementos de 
� ou � 
Sobre os n-gramas:
1) normalização � 
2) consistência de Kolmogorov, � 
	
� 
ℤm ⇔ ℤnm
s ∈ {A, A2, A3, A4, ⋯} s ∈ ⋃
k=1
Ak
∑
xn∈ℤm
P (x0, x1, ⋯, xn−1) = 1
s > n
∑
xn∈ℤm
P (x0, x1, ⋯, xn−1) = ∑
xn,xn+1,⋯,xs−1
P (x0, x1, ⋯, xn−1, xn, xn+1, ⋯, xs−1)
�
exemplo. 
3-grama BIO sobre � 
5-grama BIO** sobre � 	 	 � 
MODELO 1: texto de ordem-0 (unigramas)
uniforme em � , � .
Em , A={A,B,C,...,Z,_} 
ℤ3m
ℤ5m
262
∑
k = 1
* *
P(BIO * * ) = P(BIO)
ℤm P(ai) =
1
m
ai ∈ ℤm
ℤ27 P(ai) =
1
27
ai ∈ ℤ27
�
MODELO 2: texto de ordem-1 (unigramas independentes)
Em � , A={A,B,C,...,Z,_}
 � 
� 
ℤ27
P(ai) = freq. relativa ocorrência de ai, ai ∈ ℤ27
P (x0, x1, ⋯, xn−1) =
n−1
∏
k=0
P(xk)
�
	 
Digramas 
	 	 	 	 	 P(QU)=P(Q).P(U)=0.007 x 0.030 =2.1 10-4
	 	 	 	 	 P(QR)=P(Q).P(R)=0.007 x 0.053 =3.7 10-4
MODELO 3: texto de ordem-2 (digramas independentes)
� 
	 	 	 	 	 � 
	 	 	 	 	 � 
P (x0, x1, . . . , x2n−1) = P(x0, x1) . P(x2, x3) . ⋯ . P(x2n−2, x2n−1)
P(s, t) ≥ 0 0 ≤ s, t ≤ m
∑
s
∑
t
P(s, t) = 1
�
Digramas 
	 	 	 	 	 P(QU)= 0.0072 
	 	 	 	 	 P(QR)= 0.0000
MODELO 4: fonte markoviana (modelo com memória)
cadeia de Markov com matriz de probabilidades de transição
� 
Para cadeia ergódica, a distribuição estacionária de equilíbrio:
	 	 	 	 	 	 � 
{P(s | t)} 0 ≤ t, s < m
π = {π0, π1, ⋯, πm−1}
�
Distribuição de equilíbrio segue da matriz de transição
� 
� 
...
� 
ou � .
π0 = π0P(0 |0) + π1P(0 |1) + π2P(0 |2) + ⋯ + πm−1P(0 |m − 1)
π1 = π0P(1 |0) + π1P(1 |1) + π2P(1 |2) + ⋯ + πm−1P(1 |m − 1)
πm−1 = π0P(m − 1 |0) + π1P(m − 1 |1) + π2P(m − 1 |2) + ⋯ + πm−1P(m − 1 |m − 1)
π = π[P]
�
� 
Simulando:
	 	 1) abra texto de referência em página aleatória
	 	 	 1o caractere é x1
	 	 2) abra texto de referência em página aleatória
	 	 	 procure x1; o próximo caractere é x2
	 	 3) abra texto de referência em página aleatória
	 	 	 procure x2; o próximo caractere é x3
	 	 ...
P =
P(A |A) P(B |A) ⋯ P(Z |A) P(_ |A)
P(A |B) P(B |B) ⋯ P(Z |B) P(_ |B)
⋯ ⋯ ⋯
P(A |Z) P(B |Z) ⋯ P(Z |Z) P(_ |Z)
P(A |_) P(B |_) ⋯ P(Z |_) P(_ |_)
�
Considere um modelo markoviano de ordem-n mais elevada � 

	 n=1 	 monograma-a-monograma	 	 � 	
	 n=2 	 digrama-a-diagrama 	 	 	 	 � 
	 n=3 	 trigrama-a-trigrama		 	 	 	 � 
... 


com alfabeto maiúsculas, minúsculas e números, � :
Para tetragramas, 
	 	 a matriz P de probabilidades de transição tem dimensão:

	 	 	 	 	 	 � 
ℤ27
m × m → 27 × 27
m2 × m2 → 272 × 272
m3 × m3 → 273 × 273
ℤ63
15.752.961 × 15.752.961
�
Entropia da língua inglesa (Claude Shannon)




Zero-order approximation. 



(The symbols are independent and equiprobable.)

XFOML RXKHRJFFJUJ ZLPWCFWKCYJ
FFJEYVKCQSGXYD QPAAMKBZAACIBZLHJQD

The entropy of zeroth-order model = log 27 = 4.76 Sh per letter. 
�




First-order approximation. 



(The symbols are independent. 

The frequency of letters matches English text.)
OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI
ALHENHTTPA OOBTTVA NAH BRL

The first order model gives an estimate of the entropy of 4.03 Sh 
per letter
�
Second-order approximation. 



(The frequency of pairs of letters matches English text.)

ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY
ACHIN D ILONASIVE TUCOOWE AT TEASONARE FUSO
TIZIN ANDY TOBE SEACE CTISBE


EXT OR SYMAD RES FUN PLUDEFOLY FOR ORY THER CURSOR 
STEME TO OU ANNINPUT
�
Third-order approximation. 



(The frequency of triplets of letters matches English text.)

IN NO IST LAT WHEY CRATICT FROURE BERS GROCID
PONDENOME OF DEMONSTURES OF THE REPTAGIN IS
REGOACTIONA OF CRE
MAJORIZONTAL IS ZEROUS COMPUT COPY OF AND THE 
LIMILABLESPOT LEVE AVE MODE IS DEALINE OF 
PERMINORMATION
�










Fourth-order approximation. 

(The frequency of quadruplets of letters matches English text.)

THE GENERATED JOB PROVIDUAL BETTER TRAND THE 
DISPLAYED CODE, ABOVERY UPONDULTS WELL THE CODERST 
IN THESTICAL IT DO HOCK BOTHE MERG. (INSTATES CONS 
ERATION. NEVER ANY OF PUBLE AND TO THEORY. EVENTIAL 
CALLEGAND TO ELAST BENERATED IN WITH PIES AS IS WITH 
THE )


fourth-order model gives an estimate of 2.8 Sh per letter.
�




Entropy of English using Shannon guessing game. 
Shannon 1950: entropy rate for English using a human gambler to 
estimate probabilities. 1.34 Sh per letter.
entropia modelo
4.60 Sh fonte simétrica sem memória com 27 símbolos
4.13 Sh fonte de 1a ordem, frequência de letras estimada
3.34 Sh fonte de 2a ordem
2.80 Sh fonte de 4a ordem
1.30 Sh Shannon guessing game
�
A entropia de um texto "representativo" em inglês com alfabeto de 27 letras 
(nenhuma distinção de pontuação ou minúscula/maiúscula: 26 letras e mais um 
caractere "espaço") foi estimada em aproximadamente H = 1,3 bits por letra.
Interpretação
 A redundância é cerca de � . 
 um livro com 300 páginas pode ser reduzido para 300(1 - 0,73) = 81 páginas 
sobre o mesmo alfabeto ou 

 um livro com 300 páginas pode ser reduzido para conter apenas 27(1-0.73) = 
2.43 (i.e., pelo menos 3) símbolos.
R = 1 −
1.3
log2 27
= 0.73
�
First-order word model. 
(The words are chosen independently but with frequencies as in English.)

REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN
DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO
EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.
(The word transitionprobabilities match English text.) 

THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER
THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER
METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD
THE PROBLEM FOR AN UNEXPECTED



�
Fontes de Markov
caracterizada por estados 1,2,...,J
letras do alfabeto �
sequência da fonte: �
sequência de estados: �
Denota-se por Qji a probabilidade condicional de ir ao estado i quando o estado anterior é j
� PROB. TRANSIÇÃO DE ESTADOS
Fonte Markov: Propriedade: � .
a1, a2, ⋯, aK
u = (u1, u2, ⋯)
s = (s1, s2, ⋯)
Qji = Pr(sl = i |sl−1 = j)
Pr(sl |sl−1, sl−2, sl−2, ⋯) = Pr(sl |sl−1)
�
Cadeia de Markov discreta
Seja � 
a probabilidade da letra ak ser emitida quando a fonte está no estado j.
Exemplo.
ramos rotulados pelos símbolos de saída � ; probabilidade � .
Pj(ak) = Pr[ul = ak |sl = j]
ak Pj(ak)
�
Cadeias de Markov homogêneas
um estado s é transitório se há outro estado que pode ser alcançado a partir dele, mas 
que do mesmo é impossível retornar a s.
vide ESTADO 1
um conjunto de estados é irredutível se, de cada dos estados, nenhum estado fora do 
conjunto pode ser atingido e cada estado do conjunto pode ser atingido em uma ou 
mais transições.
vide ESTADOS {2,3} e ESTADOS {4,5}
transitórios + irredutíveis
com probabilidade 1 a cadeia vai para um dos conjuntos irredutíveis e estaciona lá
�
período de estados irredutíveis:
maior inteiro m tal que todas as recorrências para os estados são 
múltiplos de m.
ESTADOS {2,3} período m=1
ESTADOS {4,5} período m=2.
Se uma cadeia é homogenea com estados irredutíveis de período 
m=1, ela é chamada ergódica.
�
Probabilidade limite de estados ergódicos E
Há probabilidades estacionárias � para cada estado, soluções de:
�
� .
Além disso, as probabilidades assintóticas de estados � verificam:
�
se a fonte iniciou em um estado ergódico há infinitamente muito tempo atrás
�
q( j)
∑
j∈E
q( j)Qji = q(i)
∑
j∈E
q( j) = 1
i ∈ E
lim
l→∞
Pr(sl = i |s1 = j) = q(i) .
Pr(sl = i) = q(i) ∀l .
�
Outro Exemplo
�
Os estados 1,2 e 3 são transitórios (não essenciais)
Duas cadeias irredutíveis: {estados 4 e 5, aperiódica} e {estados 6,7 e 8, de período m=2)


Teorema. Para uma cadeia de Markov finita, irredutível e aperiódica, existem os limites
� e são independentes de i.lim
n→∞
pnij = πj
�


Entropia de uma fonte de Markov
� .
Teorema. A entropia por letra de uma fonte ergódica markoviana é dada por 
� , em que � .
(o limite sempre existe). Se a cadeia só possui um conjunto de estados irredutíveis, então
� , as probabilidades estacionárias dos estados.
prova. vide Robert Gallager (book).
H(U |s = j) = −
K
∑
k=1
Pj(ak)log Pj(ak)
H∞(U ) :=
J
∑
i=1
q(1,∞)H(U |s = i) q(1,∞) = lim
L→∞
1
L
L
∑
l=1
P(sl = i)
q(1,∞)(i) = q(i)
�


TEOREMA DA CODIFICAÇÃO DE FONTES
(teorema da codificação para canais sem ruído)
(1o Teorema de Shannon)
Fontes DMS - discretas e sem memória; emitem símbolos 
sucessivos independentes.
�
Estamos interessados em codificar a saída da fonte usando um 
novo alfabeto de “D" letras. A codificação deve ser tal que:
1) Dada um sequência emitida pela fonte, queremos que a 
sequência código transmitida seja tal que de posse da 
mesma, possamos recuperar a sequência da fonte com um 
probabilidade tão alta como se queira.
2) o número de letras código “gasto" por letras fonte deve ser o 
mínimo possível (compressão de dados).
�
Entender compactação como “retirada” da informação redundante
POXM LIT ST ISNVE N IT
A PROXM LITA EST ISPNIVE N SIT
A PROXMA LITA EST ISPNIVE NO SIT
A PROXIMA LISTA ESTÁ DISPONIVEL NO SITE
Como achar a sequência mais curta tal que possamos recuperar 
toda a mensagem??
�
Seja � uma sequência de tamanho L, com 
letras de um alfabeto de cardinalidade K. O número de possíveis 
sequências distintas é � .
Suponha que desejamos codificá-la em uma sequência de 
tamanho N com letras oriundas de um alfabeto de cardinalidade 
D. Há, naturalmente, � delas.
uL := (u1, u2, . . . , uL)
KL
DN
�
Devemos impor, vista a condição 1, que � ou seja
� .
N/L é o 
número de letras do alfabeto código/número de letras do alfabeto fonte
podemos fazer melhor? 
É possível se escolher � e ainda assim satisfazer 1.
Mas há um limite em quanto reduzir N/L.
DN ≥ KL
N
L
≥
log2 K
log2 D
N
L
<
log2 K
log2 D
�


veja que em geral o codificador converte sequências de 
comprimento L de letras da fonte em sequências de comprimento 
N de letras do código.
O caso mais simples é L=1, em que desejamos codificar as letras 
da fonte (monogramas) em letras-código binárias D=2. 
No caso de texto com K=27 letras {A,B,C,...,X,Y,Z, space}, se a 
codificação é binária, �DN ≥ KL → 2N ≥ 271 → N ≥ 5.
�
sequências-código sequências-fonte
 --- ---
--- ---
--- ---
...
--- ---
---
---
 � implica em “sobras”: há uma distinta para cada 
sequência-fonte e as vermelhas não são usadas.
DN > KL
�
� significa que há mais sequências-código e pode ser 
feito um mapeamento biunívoco de todas as sequências-fonte (e 
“sobram" ainda sequências-código). � 

00000 A
00001 B
00010 C
...
11001 Y
11010 Z
11011 SPACE 11100 ... 11111 não são usadas.
DN ≥ KL
25 ≥ 271
�
Exemplos de códigos: Braille
L. Braille (1829): 
código de 6 bits permite 63 códigos possíveis (plano ou ponto elevado).
- 	 26 são usados para codificar letras romanas
- 	 o resto para codificar palavras de comando (e, para, de, com) 
- 	 e combinações comuns de duas letras (ch, gh, sh, th, wh, ed, er, ou, ow)
�
Usando dicionário, decodifique o seguinte texto Braille:
�
1o Teorema de Shannon codificação de fontes com comprimento fixo.
Teorema. Seja uma fonte DMS de entropia H(U), com alfabeto de 
cardinalidade K e C um código de comprimento N sobre um 
alfabeto de cardinalidade D. Se Pe denota a probabilidade de 
uma sequência de comprimento L da fonte não coberta pela 
código, então para qualquer � :
mensagem direta.
Se , então Pe pode ser fe i ta 
arbitrariamente pequena fazendo-se L suficientemente grande.

δ > 0
N
L
≥
H(U) + δ
log2 D
�


mensagem inversa.
Se , então Pe se tornará arbitrariamente 
próxima de 1 a medida que L cresce.
prova.



Vejamos
� .
N
L
≤
H(U) − δ
log2 D
I(uL) = − log2 P(uL) = − log2
L
∏
i=1
p(ui) = −
L
∑
i=1
log2 p(ui)
�
Assim, 
� para fonte sem memória.
Portanto, � é uma soma de v.a.’s iid.
Versão fraca da lei dos grandes números
Se � são v.a.’s i.i.d. com média comum � , então
� .
(média amostral converge para a média estatística).
I(uL) =
L
∑
i=1
I(ui)
I(uL)
{Xi}Li=1 X̄
lim
L→∞
1
L
L
∑
i=1
Xi → X̄ em probabilidade
�
------
A média de � é igual à entropia da fonte, denotada por H(U).
� .


Então 
� .
I(ui) ∀i
H(U) := −
K
∑
k=1
P(ak)I(ak)
lim
L→∞
1
L
L
∑
i=1
I(ui) → H(U) em probabilidade
�
significado grosseiro
� , ou seja, �
� .
A probabilidade de uma sequência típica de comprimento L 
emitida pela fonte é � e o número de sequências-típicas 
será grosseiramente igual a:
� .

Pela condição 1, impõe-se � .
1
L
L
∑
i=1
I(ui) →
?
H(U) I(uL) →
?
LH(U) .
−log2 P(uL) →
?
LH(U) ∴ P(uL) →
?
2−LH(U)
2−LH(U)
ML ≈ 2LH(U)
DN ≥ ML ≈ 2LH(U)
�
Esta condição conduz a � . Caso binário, D=2 e
� .
Procedendo agora de modo rigoroso [prova].
� significa:
N
L
≥
H(U)
log2 D
N
L
≥ H(U)
lim
L→+∞
1
L
L
∑
i=1
I(ui) → H(U) em probabilidade
�
Dado � 
� ,
em que �
Denominemos por T o conjunto de todas as sequências � da 
fonte tais que
� (*TIPICAS)
(chamaremos esta sequências de típicas).
δ > 0 ∃ϵ(δ, L) |
P[ |
1
L
L
∑
i=1
I(ui) − H(U) | > δ] ≤ ϵ(δ, L)
lim
L→+∞
ϵ(δ, L) = 0.
uL
|
I(uL)
L
− H(U) | < δ
�
Logo � .
De (*), � , donde
�
e usando a definição de � , 
�
Para L suficientente grande � .
P(T ) = 1 − P[ |
I(uL)
L
− H(U) | ≥ δ] ≥ 1 − ϵ(δ, L)
−δ ≤
I(uL)
L
− H(U) ≤ δ
L [H(U) − δ] ≤ I(uL) ≤ L [H(U) + δ]
I( ⋅ )
2−L [H(U)−δ] > P(uL) > 2−L [H(U)+δ]
P(uL) ≈2−L [H(U)]
�
a) podemos afirmar que 

� ou seja,



 �
de modo que o número de sequências típicas é limitado por 
�
P(T ) = ∑
u∈T
P(u)
1 ≥ P(T ) ≥ ML.2−L[H(U)+δ]
ML ≤ 2L[H(U)+δ]
�
b) Por outro lado, 
�


de modo que o número de seq. típicas é limitado por



�
COMBINANDO-SE a) e b) chega-se ao número de seq. típicas
� . (AES)
1 − ϵ(δ, L) ≤ P(T ) ≤ ML.2−L[H(U)−δ]
ML ≥ [1 − ϵ(δ, L)].2L[H(U)−δ]
[1 − ϵ(δ, L)].2L[H(U)−δ] ≤ ML ≤ 2L[H(U)+δ]
�
i) Mensagem direta do teorema.



Suponha que as sequências típicas sejam codificadas de tal 
modo que 



� � 



Logo, a cada sequência típica poderá corresponder uma 
sequência código e
� 

DN ≥ 2L[H(U)+δ] ≥ ML
N
L
≥
H(U) + δ
log2 D
Pe ≤ P(T̄, não ser codificada) ≤ P(T̄ )
�
Mas a probabilidade de sequências atípicas vai a zero:
� ,
assim

� .
ii) Mensagem inversa do teorema.
Codificando a sequência fonte de modo que �
� .
P(T̄ ) = 1 − P(T ) ≤ 1 − {1 − ϵ(δ, L)} ≤ ϵ(δ, L)
lim
L→+∞
P(T̄ ) = 0
DN < 2L[H(U)−2δ]
N
L
<
H(U) − 2δ
log2 D
�
�
com
�
�
Finalmente,
� ,
ou seja,
�
1 − Pe = P(T, ser codificada) + P(T̄, ser codificada)
P(T, ser codificada) = ∑
uL∈T
P(uL) ≤ DN max
uL
P(uL)
P(T̄, ser codificada) ≤ P(T̄ ) ≤ ϵ(δ, L)
1 − Pe ≤ 2L[H(U)−2δ].2−L[H(U)−δ] + ϵ(δ, L)
Pe ≥ 1 − 2−Lδ + ϵ(δ, L) → 1.
�
Códigos: comprimento fixo vs comprimento variável
K=4 D=2
alfabeto � probabilidades �a1, a2, a3, a4 P(a1), P(a2), P(a3), P(a4)
�
interesse: � , número médio de letras-código/letras-fonte
�
alfabeto comprimento fixo comprimento variável
� 2 bits10
� 2 bits00�a3
� 2 bits11
� 1 bit0�a1
� 3 bits111�a4
� 2 bits01
� 1 bit1�a2
� 2 bits00
n̄
n̄ :=
K
∑
k=1
P(ak) . nk
�
Uma fonte DMS emite 5 símbolos � com 
probabilidade � .
Considere dois códigos binários diferentes para os símbolos da 
fonte:
� 0 � 00
� 10 � 01
� 110 � 10
� 1110 � 110
� 1111 � 111
{a1, a2, a3, a4, a5}
{ 12 , 18 , 18 , 18 , 18 }
a1 → a1 →
a2 → a2 →
a3 → a3 →
a4 → a4 →
a5 → a5 →
�
Estimando o comprimento médio das palavras-código:
código 1
� = 2.125 bits/letra 
código 2
� = 2.250 bits/letra
Há um melhor código? (de menor comprimento, i.e. de 
representação mais compacta da fonte). Como encontrá-lo?
n̄1 = 1.
1
2
+
1
8
[2 + 3 + 2 × 4]
n̄2 = 2.
1
2
+
1
8
[2 × 2 + 2 × 3]
�
 Exemplos de códigos
código I � ; � não é unicamente decodificável
alfabeto código I código II código III código IV
1/2
1/4
1/8
1/8
�a3 �011
�10
�0
�11
�1
�a1
�a4
�0
�0111
�110
�1
�0
�P(ak)
�10
�a2 �01
�0
�111
�00
�0
a1 → 0 a2 → 0
�
código II 

�
logo não é univocamente decodificável.
unicamente decodificável [univocamente decodificável]
Se qualquer sequência fonte distinta de comprimento finito tem 
sequência de letras-código diferentes a ela associadas.
0 0 1 1 1⋯
→ a1 a1 a2 a2 a2⋯
→ a3 a2 a2 a2 . . .
→ a3 a4 a4 ⋯ ⋯
→ a1 a1 a4 a3 a3⋯
�
código com condição de prefixo [códigos instantâneos]
Um código com condição de prefixo é aquele no qual nenhuma 
palavra-código é prefixo de outra palavra-código.
códigos I & II & IV não são.
códigos prefixo � unicamente decodificável
código III 1 1 1 1 0 0 ... 111 | 10 | 0 ... = 
código sem pontuação (comma free code)
código IV 0 0 0 1 0 1 1 1 0 0 | 0 | 01 | 0111 | 0 |...
⇒
⇒ a4 a2 a1 ⋯
⇒
�
código com pontuação (comma code)
representação em árvore.
�


Desigualdade de Kraft
Se os inteiros � satisfazem a desigualdade
�
� então existe um código com alfabeto de cardinalidade D que 
satisfaz a condição de prefixo e tem estes inteiros como 
comprimento das palavras-código.
� Os comprimentos de todos os códigos com condição de prefixo 
satisfazem a desigualdade de Kraft.
necessidade & suficiência
n1, n2, ⋯, nK
K
∑
k=1
D−nk ≤ 1
⇒
⇐
�
prova [esboço]
árvore completa 
árvore completa de ordem n, no alfabeto D � � nós terminais


exemplo: D=2 árvore binária
⇒ Dn
�
exemplo: D=3 árvore ternária
(esboço de prova � )
A fração de nós partindo de um nó terminal na ordem i é �
ao se selecionar um nó como "nó terminal" para alocar uma 
palavra-código, elimina-se esta fração de nós candidatos.
⇒
D−i
�
 
�
Como nó terminal, não haverá nenhuma palavra-código mapeada 
em nós acima dele (garantindo a condição de prefixo).
aloca-se um nó terminal na ordem � � � fração descartada
aloca-se um nó terminal na ordem � � � fração descartada
...
 aloca-se um nó terminal na ordem � � � fração descartada
n1 ⇒ D−n1
n2 ⇒ D−n2
nK ⇒ D−nK
�
como � , ainda há nó disponível na alocação do nó 
terminal para a última letra do alfabeto [cabe alocar terminais]
Exemplo. 
D=2 ( � )=(1 2 3 3) com �
um nó terminal na ordem 1 (cor vermelha)
um nó terminal na ordem 2 (cor laranja)
dois nós terminais na ordem 3 (cores verde e azul)
K
∑
k=1
D−nk ≤ 1
n1, n2, ⋯, nK 2−1 + 2−2 + 2−3 + 2−3 ≤ 1
�
Leon G. Kraft Jr., (and Wilbur B. Davenport Jr.), MIT 1943
(esboço de prova � )
qualquer código com condição de prefixo está incluso na árvore 
completa [vide detalhes da prova]
⇐
�
Teorema (McMillan)
Considere um código cujos comprimentos das palavras-código 
valem � sobre símbolos de um alfabeto de 
cardinalidade D.
Se o código é unicamente decifrável, então a desigualdade de 
Kraft deve ser satisfeita.
prova. [vide livro texto TI]. 
unicamente decodificável � Kraft � código com condição de prefixo.
Consequência: se unicamente decifrável, pode-se construir um 
código com condição de prefixo com os mesmos comprimentos!
n1, n2, ⋯, nK
⇒ ⇔
�
1o Teorema de Shannon codificação de fontes com comprimento variável.
Teorema. Seja uma fonte DMS de entropia H(U), com alfabeto de 
cardinalidade K e C um código sobre um alfabeto de 
cardinalidade D. É possível atribuir palavras-código para as letras 
fonte satisfazendo a condição de prefixo e cujo comprimento 
médio das palavras-código � verifica:
� .
Além disso, para qualquer conjunto de palavras-código 
unicamente decodificáveis, tem-se
� .
n̄
n̄ ≤
H(U)
log D
+ 1
n̄ ≥
H(U)
log D
�
prova.
Sejam � as probabilidades das letras-fonte e 
sejam � os comprimentos das palavras-código 
correspondentes.
�
pondo -nk no logaritmo e combinando termos
� .
P(a1), ⋯, P(aK)
n1, ⋯, nK
H(U) − n̄ log D =
K
∑
k=1
P(ak) . log2
1
P(ak)
−
K
∑
k=1
P(ak)nk . log D
H(U) − n̄ log D =
K
∑
k=1
P(ak) . log2
D−nk
P(ak)
�
Da desigualdade fundamental da TI, 
�
A última desigualdade segue da desigualdade de Kraft que é 
válida para qualquer código univocamente decifrável.
A igualdade se verifica sss � . (**)

parte ii provada.
H(U) − n̄ log D ≤ (log e)[
K
∑
k=1
D−nk − ∑
k
P(ak)] ≤ 0.
P(ak) = D−nk, 1 ≤ k ≤ K
�
Para satisfazer a equação (**), podem ser escolhidos nk tais que
�
Escrevendo cada equação e somando todas membro a membro, 
o lado esquerdo se torna a desigualdade de Kraft (existe código 
com condição de prefixo).


O lado direito, via log, resulta �
Finalmente, 
�
Multiplicando por � e somando, chega-se ao resultado Q.E.D.
D−nk ≤ P(ak) ≤ D−nk+1, 1 ≤ k ≤ K
log P(ak) < (−nk + 1) . log D
nk <
−log P(ak)
log D
+ 1
P(ak)
�
Teorema. Seja uma fonte DMS de entropia H(U) e C um código 
sobre um alfabeto de cardinalidade D. É possível atribuir 
palavras-código para sequência de L letras-fonte satisfazendo a 
condição de prefixo e cujo comprimento médio das palavras-
código � verifica:
� .
Além disso, a desigualdade a esquerda é satisfeita por qualquer 
código unicamente decodificável.
n̄
H(U)
log2 D
≤ n̄ <
H(U)
log2 D
+
1
L
�
prova.
Para codificar sequências de L letras, a entropia é LH(U) e o 
comprimento médio das palavras-código � de modo que 
aplicando o teorema anterior,
� ,
o resultado segue dividindo-se por L todos os membros.
Ln̄
LH(U)
log2 D
≤ Ln̄ <
LH(U)
log2 D
+ 1
�
redundância:= � .
Uma discussão do teorema da codificação para códigos de 
comprimento variável também se aplica para fontes de Markov, 
mostrando o seguinte resultado:
Teorema