Brev ssima introduc˘~ao a teoria da informac˘ao~amoreira/lectnotes/fisinf.pdf · Brev ssima...

Brevıssima introducao a teoria da

informacao

L.J. AmoreiraDept. Fısica, UBI

Dezembro 2010

Conteudo

1 Introducao 2

2 Variaveis aleatorias e probabilidade 32.1 Experiencias aleatorias e variaveis aleatorias . . . . . . . . . . . . 32.2 Probabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Definicao de probabilidade . . . . . . . . . . . . . . . . . . 42.2.2 Variaveis aleatorias. Valor expectavel e variancia . . . . . 5

2.3 A nocao intuitiva de probabilidade . . . . . . . . . . . . . . . . . 72.4 Probabilidade conjunta e probabilidades marginais . . . . . . . . 82.5 Probabilidade condicional e independencia . . . . . . . . . . . . . 102.6 Um exemplo mais elaborado . . . . . . . . . . . . . . . . . . . . . 12

3 Ignorancia e informacao 153.1 Como medir a informacao . . . . . . . . . . . . . . . . . . . . . . 153.2 Como medir a ignorancia . . . . . . . . . . . . . . . . . . . . . . 15

3.2.1 Tres requisitos a satisfazer pela medida da ignorancia . . 163.3 Significado intuitivo da entropia . . . . . . . . . . . . . . . . . . . 203.4 Entropia conjunta e entropia condicional . . . . . . . . . . . . . . 223.5 Algumas propriedades da entropia . . . . . . . . . . . . . . . . . 253.6 Informacao. Informacao mutua . . . . . . . . . . . . . . . . . . . 273.7 Duas aplicacoes recreativas . . . . . . . . . . . . . . . . . . . . . 29

4 Codificacao sem ruıdo 30

A Propriedades elementares dos logaritmos 31

B Demonstracao de algumas proposicoes enunciadas 33B.1 Um teorema auxiliar . . . . . . . . . . . . . . . . . . . . . . . . . 33B.2 −

∑pk log pk e a unica medida aceitavel de ignorancia . . . . . . 34

B.3 −∑pk log pk e maxima se os pk forem todos iguais . . . . . . . . 34

B.4 H(X,Y ) ≤ H(X) +H(Y ) . . . . . . . . . . . . . . . . . . . . . . 34B.5 H(Y |X) ≤ H(Y ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

C “Entropia”?! Porque esta palavra? 36

1

1 INTRODUCAO 2

1 Introducao

A teoria matematica da informacao debruca-se sobre problemas relacionadoscom o armazenamento e o transporte de informacao, de uma forma geral, in-dependente das vantagens e condicionalismos especıficos inerentes a qualquertecnologia particular.

O tipo de problemas estudado fica ilustrado com questoes como as que seseguem: “Como codificar as mensagens de modo a que o tempo medio de trans-missao, a uma taxa de transferencia dada, seja mınimo?”, “Ha limites para acompressao de informacao? Se sim, quais?”, “Como minimizar a probabilidadede ocorrencia de erros na transmissao de informacao?”.

Subjacente a teoria, ha um modelo geral para a transmissao de informacaoque devemos introduzir antes de prosseguir, e que esta esquematizado na Fi-gura 1. Talvez valha a pena uma breve discussao sobre os aspectos menos obvios

Figura 1: Modelo para a comunicacao de informacao.

deste modelo, que sao (1) a necessidade de codificacao (e de descodificacao) damensagem e (2) a presenca do ruıdo no canal de transmissao. Em primeirolugar, na transmissao de informacao ha sempre um processo de codificacao,mesmo que frequentemente nao nos apercebamos disso. A codificcao necessariapara a transmissao pode ser linguıstica (ou seja, a verbalizacao da mensagem),pode consistir na digitalizacao, na transformacao em sinais de modulacao deuma onda portadora, na pela codificacao em codigo morse, na transformacaoda mensagem numa onda de pressao atmosferica (som) ou em desenhos numquadro, etc. A codificacao da mensagem consiste, ao fim e ao cabo, na geracaode um sinal apto para a sua transmissao. E dessa necessidade que os blocos “co-dificador” e “descodificador” na figura dao conta. Em segundo lugar, o canal detransmissao (fibra optica, papel impresso, sinal electromagnetico, pen drive, etc)esta quase sempre sujeito a influencias externas e internas incontrolaveis, maisou menos intensas, pelo que se deve considerar a possibilidade de a mensagemser parcialmente corrompida no processo de transmissao. E esse eventual efeitoque esta contemplado com a introducao de “ruido” no canal de transmissao.

Nestes apontamentos faz-se uma introducao a teoria da informacao. Comeca-se por rever alguns conceitos da teoria das probabilidades, um pre-requisito in-dispensavel para a teoria da informacao, na Seccao 2. Na Seccao 3 introduz-seuma medida de ignorancia (a entropia de Shannon) e define-se a quantidadede informacao. O problema da codificacao optima (sem ruıdo) e, por fim, es-tudado na Seccao 4. Deixa-se para os apendices algumas demonstracoes maiselaboradas.

2 VARIAVEIS ALEATORIAS E PROBABILIDADE 3

2 Variaveis aleatorias e probabilidade

2.1 Experiencias aleatorias e variaveis aleatorias

Ha algumas experiencias ou observacoes cujo resultado nao pode ser determi-nado de antemao. Por exemplo nao sabemos (nem sabemos como calcular)o resultado do lancamento de um dado, nao sabemos, com certeza absoluta,se ira chover numa determinada hora de um dia no futuro, nao sabemos pre-ver quanto tempo um neutrao isolado existira antes de, por decaimento-β, setransformar num protao, num neutrao e num anti-neutrino, nao sabemos quepartido ira ganhar as proximas eleicoes. Experiencias ou observacoes com estacaracterıstica de imprevisibilidade chamam-se experiencias aleatorias. Chama--se resultado ou acontecimento a um resultado particular de uma experienciaaleatoria, espaco de acontecimentos ou espaco de resultados de uma experienciaaleatoria ao conjunto dos seus resultados e variavel aleatoria a qualquer funcaodesses resultados.

Vejamos alguns exemplos. Quando se lanca um dado, e um acontecimento“sair” o 4, “sair” o 1, “sair” um numero par (2, 4 ou 6) ou “sair” um numeroprimo primo (2, 3 ou 5). O espaco de resultados desta experiencia e o conjunto{1, 2, 3, 4, 5, 6}. Relativamente a duracao de um neutrao isolado, sao aconteci-mentos o neutrao existir durante um perıodo inferior a 5 min, o neutrao decairnum intervalo de tempo compreendido entre 3 s e 3,1 s, etc. O espaco de resul-tados e agora o conjunto dos numeros reais positivos. O espaco de resultadosrelativamente aos resultados das proximas eleicoes e o conjunto dos partidos quea ela concorrem, etc.

Dados dois acontecimentos de uma experiencia aleatoria, chamamos uniaoao acontecimento de se dar um ou o outro (ou ambos); chamamos interseccao aoacontecimento de se darem ambos simultaneamente. Por exemplo, considerandoo lancamento de um dado, a uniao dos acontecimentos A=(“sai” o 1) e B=(“sai”o 2) e o acontecimento A ∪ B=(“sai o 1 ou o 2); a interseccao destes doisacontecimentos e, obviamente, nula. Ainda relativamente ao lancamento dodado, a uniao dos acontecimentos A=(“sai” um numero par) (ou seja, “sai” umdos elementos de {2, 4, 6}) e B=(“sai” um numero menor que 3) (ou seja, sai umdos elementos de {1, 2}) e o acontecimento A ∪ B={1,2,4,6}; a sua interseccaoe A ∩B={2}.

Dois acontecimentos dizem-se disjuntos ou incompatıveis se a sua interseccaofor o vazio. Dois ou mais acontecimentos dizem-se uma particao do espaco deresultados se forem incompatıveis e se a sua uniao for o proprio espaco de resul-tados. Voltando ao exemplo do lancamento do dado, sao acontecimentos incom-patıveis “sair” o 1 e “sair” o 2; sao tambem incompatıveis “sair” um numero pare “sair” um numero ımpar, e estes dois acontecimentos formam uma particao doespaco de resultados da experiencia. Por fim, dois acontecimentos X e X dizem--se complementares se forem incompatıveis e formarem uma particao do espacode acontecimentos. Estas definicoes podem ser ilustradas graficamente recor-rendo aos chamados diagramas de Venn. Num diagrama de Venn representa-seo espaco de resultados de uma experiencia aleatoria atraves de um rectangulo eacontecimentos dessa experiencia como porcoes desse rectangulo. As definicoesapresentadas acima ficam ilustradas nos diagramas da Figura 2.


Figura 2: Diagramas de Venn.

2.2 Probabilidade

Quando se repete muitas vezes uma experiencia aleatoria, alguns resultadosocorrem mais frequentemente que outros. A nocao de probabilidade foi desenvol-vida exactamente para dar conta dessa “regularidade irregular” dos fenomenosaleatorios. De um ponto de vista fısico (ou empırico), a probabilidade de umacontecimento e, simplesmente, a frequencia relativa da sua ocorrencia quandose repete mutias vezes a experiencia que o produz. Mas esta definicao de proba-bilidade, chamada definicao empırica, e muito vaga (quantas muitas vezes e quee preciso repetir a experiencia para que a probabilidade de cada acontecimentoseja igual a sua frequencia relativa?) e por isso pouco util, de um ponto devista teorico. Uma definicao mais produtiva e a definicao axiomatica, que seraapresentada ja de seguida. No entanto, como a defnicao empırica e a expressaomais directa da nossa intuicao, e convem mante-la sempre presente no que sesegue.

2.2.1 Definicao de probabilidade

Probabilidade e qualquer funcao P (A) dos acontecimentos de uma experienciaaleatoria com espaco de acontecimentos S que satisfaca os seguintes axiomas:

1. A probabilidade e real e nao negativa:

P (A) ∈ R≥0,∀A ∈ S

2. A probabilidade da uniao de dois acontecimentos disjuntos e a soma dasprobabiliades:

P (A ∪B) = P (A) + P (B), se A ∩B = ∅

3. A probabilidade do espaco de acontecimentos e a unidade

P (S) = 1


Destes axiomas podemos deduzir varias propriedades da probabilidade:

1. P (X) ≤ 1

Demonstracao

Consideremos um acontecimento A qualquer e o seu complementar A. Uma vez quesao acontecimentos, as suas probabilidades sao reais e positivas. Mas uma vez quesao incompatıveis, a probabilidade da sua uniao e a soma das suas probabilidades,de acordo com o Axioma 2:

P (A ∪A) = P (A) + P (A).

Por outro lado, como formam uma particao do espaco de acontecimentos, A∪A =S, logo, pelo Axioma 3,

1 = P (S) = P (A ∪A) = P (A) + P (A).

Como P (A) e P (A) sao ambos positivos, nao pode nenhum deles ser superior aunidade.

2. Numa experiencia que pode produzir N resultados incompatıveis comigual probabilidade, a probabilidade de cada um e P = 1/N

Demonstracao

A probabilidade de que ocorra qualquer um dos N resultados possıveis, uma vezque eles sao incompatıveis, e igual a soma das suas probabilidades, de acordo com oAxioma 2. Mas, nesta soma, todos as N parcelas sao iguais, uma vez que as variaspossibilidades sao equiprovaveis. Por outro lado, a uniao de todas as possibilidadese o espaco de resultados, que tem probabilidade 1. Resulta entao

1 = Np⇔ p =1

N.

3. A soma das probabilidades de dois acontecimentos complementares e aunidade: P (A) + P (A) = 1

Demonstracao

Uma vez que dois acontecimentos complementares sao incompatıveis, a probabili-dade da sua uniao e a soma das suas probabilidades; mas como dois acontecimentoscomplementares formam uma paticao do espaco de resultados, a sua uniao e oproprio espaco de resultados, com probabilidade 1.

2.2.2 Variaveis aleatorias. Valor expectavel e variancia

Uma vez que os resultados das experiencias aleatorias nao sao predeterminados,os valores assumidos por variaveis aleatorias (que sao, recordemos, funcoes doresultado de uma experiencia aleatoria) tambem nao o sao. Podemos, quandomuito, associar a cada valor possıvel de uma variavel aleatoria um certo pesoprobabilıstico.

Variaveis aleatorias sao, por exemplo, o numero de pintas na face de umdado que fica virada para cima apos o lancamento, a soma dos numeros de


pintas em dois dados, o tempo de existencia de um neutrao isolado, a idade deuma pessoa escolhida ao acaso num grupo, etc.

As variaveis aleatorias podem ser discretas (como o numero que “sai” nolancamento de um dado) ou contınuas (como o tempo de existencia de umneutrao). Nos vamos apenas considerar as discretas.

Uma variavel aleatoria fica definida indicando o conjunto de valores possıveise as suas probabilidades. Quando o numero de possibilidades nao e muitogrande, pode usar-se, para especificar completamente a variavel, uma notacaoque apresenta todos os valores possıveis e as suas probabilidades. Por exemplo,

X =

(1 2 3

1/2 1/3 1/6

)(1)

representa uma variavel aleatoria que pode tomar os valores 1, 2 e 3, comprobabilidades 1/2, 1/3 e 1/6, respectivamente. Nestes apontamentos usaremosmuito frequantemente esta notacao.

Chama-se valor expectavel ou valor esperado de uma variavel aleatoria Xque pode tomar qualquer dos valores x1, x2,. . . ,xN , respectivamente com pro-babilidades p1, p2,. . . , pN , a quantidade

〈X〉 =

N∑i=1

pixi. (2)

O valor expectavel e um parametro de localizacao da variavel aleatoria ouseja, com o valor expectavel pretende-se indicar mais ou menos o valor davariavel aleatoria. Define-se tambem um parametro de dispersao (ou seja, umparametro que de uma ideia da amplitude do intervalo definido pelos valoresque a variavel aleatoria pode assumir) chamado variancia, dado por

σ2X =

N∑i=1

(xi − 〈X〉)2 . (3)

ExemploPara a variavel aleatoria da Eq. (1), o valor esperado e a variancia sao

〈X〉 =1

2× 1 +

1

3× 2 +

1

6× 3 =

5

3

σ2X =

1

2×(

1− 5

3

)2

+1

3×(

2− 5

3

)2

+1

6×(

3− 5

3

)2

=5

9

Quando repetimos muitas vezes a observacao de uma variavel aleatoria, ob-temos uma sucessao de resultados r1, r2, . . . , rN , sendo cada um deles um dosvalores que a variavel aleatoria em questao pode tomar. E usual dar-se o nomede amostra a esta sucessao de resultados concretos. Para este conjunto de va-lores, podemos calcular a media amostral, dada por

r =1

N

N∑k=1

rk,


que da uma ideia de localizacao dos valores da amostra, e a variancia amostral,

S2 =1

N − 1

N∑k=1

(rk − r)2,

que e uma medida da dispersao dos resultados obtidos. Note-se bem que estesparametros (media e variancia amostral) nao caracterizam directamente qual-quer variavel aleatoria, caracterizam, sim, amostragens concretas de variaveisaleatorias. Assim, nao devem ser confundidos com o valor esperado e a varianciade uma variavel aleatoria.

2.3 A nocao intuitiva de probabilidade

Os fenomenos aleatorios sao caracterizados por uma certa regularidade, que semanifesta quando se tomam grandes numeros de repeticoes das experiencias queos produzem, mas essa regularidade, por vezes, fica mascarada pelas flutuacoesdo acaso. Num certo sentido, podemos dizer que a irregularidade dos fenomenosaleatorios tem importancia apenas em pequena escala, quando a experienciaaleatoria em questao e repetida poucas vezes.

A nocao de probabilidade mais proxima da nossa intuicao empırica da contadessa regularidade emergente dos fenomenos aleatorios, identificando a probabi-lidade de um acontecimento como o limite para que “tende” a frequencia relativadesse acontecimento, quando se repete muitas vezes a experiencia aleatoria queproduz esse acontecimento. Como ja foi dito, esta propriedade nao serve paradefinir o conceito de probabilidade porque esta expressa de forma muito vaga.Em primeiro lugar, a palavra “tende” aparece aqui num sentido discutıvel (edaı aparecer entre aspas) porque a tendencia que ela refere nao e uma tendenciamonotona, e nem sempre e claramente discernıvel ao inıcio de uma serie de re-peticoes da experiencia; em segundo lugar, nada e dito sobre quantas vezes sedeve repetir a experiencia para que se possa fazer a identificacao da probabili-dade de um acontecimento com a sua frequencia relativa.

Vejamos com um exemplo a emergencia da regularidade estatıstica de umfenomeno aleatorio, quando se repete muitas vezes a experiencia que o produz.

ExemploConsideremos a variavel aleatoria da Eq. (1). Uma experiencia que produz essa variavel epor exemplo, a seguinte:

Lanca-se um dado; se “sair” o 1, o 2 ou o 3, tomamos X = 1; se “sair” o 4ou o 5, tomamos X = 2; se “sair” o 6, tomamos X = 3.

Repetiu-se esta experiencia 100 000 vezes. As frequencias relativas dos varios resultadosforam sendo calculadas e estao estao apresentadas no grafico em baixo. Nota-se, muitoclaramente, a tendencia de aproximacao das frequencias relativas das diferentes possibili-dades aos valores das probabilidades correspondentes.

A medida que as frequencias relativas das diversas possibilidades se regularizando esta-tisticamente, a media dos valores sucessivamente obtidos, r, vai-se aproximando do valoresperado da variavel aleatoria. Ao mesmo tempo, a variancia da amostra vai-se aproxi-mando do valor da variancia da variavel aleatoria. Na serie de repeticoes da observacao davariavel X que produziu os resultados anteriores, a media e a variancia dos resultados queforam sendo obtidos tiveram a evolucao apresentada na figura em baixo. Tambem aqui senota a regularidade estatıstica emergente quando se repete muitas vezes uma experienciaaleatoria.


Freq

uênc

ia re

lativ

a

0

0.2

0.4

0.6

0.8

1

1.2

Número de repetições100 101 102 103 104 105

f(1) f(2) f(3)

0

0.5

1

1.5

2

Número de repetições1 10 100 1,000 1e+04 1e+05

média variância

2.4 Probabilidade conjunta e probabilidades marginais

Sejam X e Y as duas variaveis aleatorias seguintes:

X =

(x1 x2 . . . xNp1 p2 . . . pN

)Y =

(y1 y2 . . . yMq1 q2 . . . qM

).

Chamamos variavel conjunta XY a composicao das duas variaveis. Assim comoos xi, 1 ≤ i ≤ N sao os N resultados possıveis de uma observacao de X e osyj , 1 ≤ j ≤ M sao os M resultados possıveis de uma observacao de Y , osresultados possıveis de uma observacao da variavel conjunta XY sao os NMpares ordenados (xi,yj), 1 ≤ i ≤ N, 1 ≤ j ≤ M . Chamamos probabilidadeconjunta Pij = P (X = xi ∩ Y = yj) a probabilidade de ocorrencia do resultado(xi,yj) numa observacao da variavel conjunta XY . A probabilidade conjuntaPij e entao a probabilidade de se obter o valor particular xi numa observacaode X e, simultaneamente, o valor particular yj numa observacao de Y . Como


uma observacao de X e de Y produz com certeza um dos NM pares (xi,yj), asoma de todas as probabilidades conjuntas deve ser 1, como se exige a qualquerdistribuicao de probabilidade:

N∑i=1

M∑j=1

Pij = 1.

Conhecidas as probabilidades conjuntas Pij de um par de variaveis XY , epossıvel calcular as probabilidades pi e qj de cada variavel do par(1). Com efeito,o resultado particular xi da observacao de X pode vir acompanhado de qualquerdos resultados particulares yj da observacao de Y , e estes sao incompatıveis(isto e, se e observado y1 nao pode ser observado y2, por exemplo). Assim, osresultados da observacao conjunta (xi,yj), para diferentes j, sao mutuamenteincompatıveis. Logo,

P (X = i) = P (X = xi ∩ Y = y1) + P (X = xi ∩ Y = y2) + . . .

+ P (X = xi ∩ Y = yM ),

ou seja,

pi =

M∑j=1

Pij

Do mesmo modo, fixando um valor particular yj de Y e considerando as variaspossibilidades para X, concluimos que

qj =

N∑i=1

Pij . (4)

ExemploNuma sala com 13 mulheres e sete homens, 2 homens e 3 mulheres estao constipados.Uma destas pessoas e escolhida ao acaso. Seja X o sexo da pessoa escolhida (com osvalores “f” e “m”) e Y o seu estado de saude (com os valores “s”, se a pessoa estiver sa,e “c”, se estiver constipada).

A variavel conjunta XY pode tomar qualquer dos valo-res (f,s), (f,c), (m,s) e (m,c). Uma vez que ha 10 mulheressaudaveis neste conjunto de 20 pessoas, a probabilidade dea pessoa escolhida ser mulher e ser saudavel e 10/20=0,5.De igual modo se obtem as restantes probabilidades con-juntas, apresentadas na tabela ao lado. Note-se que a soma

y x f m

s 0,50 0,25c 0,15 0,10

destas quatro probabilidades e a unidade, como nao podia deixar de ser. A probabilidadede a pessoa escolhida ser mulher (esteja ou nao constipada) e 13/20=0,65, justamenteo que se obtem somando as probabilidades conjuntas P (f,s) e P (f,c). Verifica-se nestecaso, portanto, a igualdade da Eq. (4). Verifique o leitor esta igualdade para as restantesprobabilidades marginais P (m), P (s) e P (c).

(1)Neste contexto, estas probabilidades pi e qj sao frequentemente designadas marginais ouapriorısticas, para as distinguirmos mais facilmente das probabilidades conjuntas (e de outrasque iremos referir em breve).


2.5 Probabilidade condicional e independencia

Em certas situacoes, conhecer o valor assumido por uma das variaveis de umpar altera os valores dos varios resultados da outra. Por exemplo, consideremoso lancamento de um dado. Seja X a variavel que representa o numero que “sai”e Y a sua paridade. Estas duas variaveis sao

X =

(1 2 3 4 5 6

1/6 1/6 1/6 1/6 1/6 1/6

)Y =

(par ımpar1/2 1/2

)As probabilidades aqui apresentadas sao probabilidades das variaveis X e Y ,previas a qualquer informacao sobre o resultado do lancamento do dado. Seconhecemos o valor de Y , as probabilidades dos varios resultados de X alteram-se. Por exemplo, se soubermos que “saiu” um numero par, as probabilidadesde X tomar os valores 1, 3 e 5 passam a zero, ao passo que as dos valores 2,4 e 6 passam a 1/3 (sabendo que o resultado e par, restam apenas tres casospossıveis, com iguais probabilidades). De igual modo, mas ao contrario, se nosdizem que no lancamento do dado “saiu” o quatro, a probabilidade de ter saıdoum resultado ımpar passa a zero e a de ter “saıdo” um numero par passa a um.

A probabilidade de ocorrencia de um dado acontecimento, sabendo-se queoutro ocorreu, chama-se probabilidade condicional. Voltando ao exemplo queacabamos de referir, a probabilidade de ter “saıdo” tres no lancamento do dadosabendo que saiu um numero par e uma probabilidade condicional (e que temo valor zero, obviamente).

Por definicao, a probabilidade condicional de um acontecimento Y = yj ,sabendo que outro acontecimento X = xi se deu e igual a probabilidade conjuntados dois acontecimentos, P (X = xi ∩ Y = yj), a dividir pela probabilidade doacontecimento condicionante, P (X = xi), ou seja

P (Y = yj |X = xj) =P (Y = yj ∩X = xj)

P (X = xi). (5)

ExemploConsideremos de novo o exemplo anterior: num grupo constituıdo por 13 mulheres e setehomens, tres mulheres e dois homens encontram-se constipados, os restantes estao saos.Um elemento do grupo e escolhido de forma aleatoria. Seja X o sexo da pessoa escolhida(com os valores “f” ou “m”) e Y o seu estado de saude (com os valores “s” ou “c”). Asprobabilidades conjuntas das ocorrencias dos varios resultados das variaveis X e Y sao,recordemo-lo:

y x f m

s 0,50 0,25c 0,15 0,10

Qual a probabilidade de ter sido escolhida uma mulher (X = f), sabendo que o elementoescolhido nao esta constipado (Y = s)? Como neste grupo ha 15 pessoas saudaveis e,dessas, 10 sao mulheres, deduzimos que essa probabilidade e

P (X = f|Y = s) = 10/15 = 2/3.

Mas esta probabilidade e uma probabilidade condicional, pelo que podemos usar a Eq. (5)para a estimar. Ora, de acordo com os valores apresentados na tabela, a probabilidade


conjunta P (X = f ∩ Y = s) = 0,5; a probabilidade de o elemento escolhido ser saudavele P (Y = s) = 0,75 (ver o exemplo da seccao anterior). Entao

P (X = f|Y = s) =P (X = f ∩ Y = s)

P (Y = s=

0,5

0,75= 2/3,

sendo assim satisfeito o resultado que obtivemos acima por analise directa da situacao.Verifique que a Eq. (5) se aplica para o calculo de outras probabilidades condicionais.

Note que em geral P (A|B) 6= P (B|A). Verifique esta preposicao para este exemplo.

Reescrevendo a Eq. (5), obtemos uma formula para calcular a probabilidadeconjunta de dois acontecimentos A e B:

P (A ∩B) = P (A|B)P (B). (6)

A esta expressao da-se por vezes o nome de regra do produto ou regra da cadeia.Dois acontecimentos A e B dizem-se independentes se o conhecimento da

ocorrencia de um nao altera a probabilidade do outro. Nesse caso, temos, evi-dentemente

P (A|B) = P (A).

Substituindo nesta igualdade a regra do produto, obtemos

P (A ∩B) = P (A)P (B), se A e B forem independentes. (7)

Se todos os resultados possıveis de duas experiencias aleatorias forem indepen-dentes entre si, as duas variaveis dizem-se, igualmente, independentes.

ExemploLanca-se uma moeda e um dado. Seja A o acontecimento de “sair” cara no lancamento damoeda e B o acontecimento de “sair” 6 no do dado. A probabilidade conjunta associadaa este par de acontecimentos e, uma vez que eles sao independentes,

P (“cara” ∩ 6) =1

2× 1

6=

1

12.

Consideremos duas variaveis aleatorias X e Y . Sabendo que X assume umdeterminado valor X = xk, as probabilidades dos varios valores possıveis para Ysao as probabilidades condicionais P (Y |X=xk). Mas, se observarmos Y , algumdos seus valores possıveis ocorrera. Assim, as probabilidades condicionadas,para um dado acontecimento condicionante devem ter soma igual a 1,∑

j

P (Y =yj |X=xk) = 1,

ou seja, as probabilidades condicionais para um dado acontecimento condicio-nante, sao elas proprias, tambem, uma distribuicao de probabilidades.

ExemploVejamos, mais uma vez o exemplo da pagina 10, em que se considera um grupo de 13mulheres e sete homens, dos quais tres mulheres e dois homens estao constipados, estandoos restantes saos. Seja, como antes, X o sexo (“f” e “m”) de um elemento do grupoescolhido ao acaso e seja Y o seu estado de saude (“s” e “c”). Como ja se viu, asprobabilidades condicionais de X conhecido Y sao as apresentadas na tabela


y x f m

s 2/3 1/3c 3/5 2/5

Note que as somas dos valores de cada linha (ou seja, as probabilidades condicionais dosdiferentes valores de X, para um dado valor de Y ) sao iguais a unidade.

2.6 Um exemplo mais elaborado

Consideremos a seguinte situacao. Lanca-se um dado. Se o resultado for 1, 2 ou3 (caso 1), lanca-se uma moeda; se o resultado do lancamento do dado for 4 ou5 (caso 2), lancam-se duas moedas; se for 6 (caso 3), lancam-se 3 moedas. SejaX o ocorrido no lancamento do dado (caso 1, caso 2 ou caso 3) e Y o numero decaras que se obtem nolancamento da ou das moedas. Calcule a distribuicao deprobabiliade da variavel conjunta XY e as probabilidades marginais das duasvariaveis separadamente.

As probabilidades marginais da variavel X sao faceis de calcular: X toma ovalor 1 se, no dado, “sair” 1, 2, ou 3, ou seja, P (X = 1) = 3/6 = 1/2. De igualmodo chegamos a P (X = 2) = 1/3 e P (X = 3) = 1/6. Ou seja, a variavel X e

X =

(1 2 3

1/2 1/3 1/6

).

As probabilidades marginais dos valores possıveis da variavel Y sao mais difıceisde calcular, porque temos que considerar diferentes situacoes conforme o valorde X. Comecemos por constatar que, visto que lancamos uma, duas ou tresmoedas, o numero de caras que obtemos no lancamento pode assumir os valores0, 1, 2 ou 3. Posto isto, consideremos os casos em que X = 1, ou seja, aqueles emque lancamos apenas uma moeda. Nesse caso, Y nao pode tomar os valores 2 ou3 (so lancamos uma moeda, temos zero ou uma cara), com iguais probabilidades;as probabilidades sao entao

P (Y |X = 1) =

(0 1 2 3

1/2 1/2 0 0

).

Vejamos agora o caso X = 2, em que lancamos duas moedas. Y pode agoraassumir os valores 0, 1 ou 2, mas Y = 3 ainda e impossıvel. Os tres casospossıveis nao sao equiprovaveis, uma vez que so ha uma situacao para se obtercada um dos casos zero ou duas caras (respectivamente, essas situacoes sao“coroa, coroa” e “cara, cara”) mas ha duas para se obter Y = 1 (“cara, coroa” e“coroa, cara”). As probabilidades dos varios valores de Y , sabendo que X = 2,sao entao

P (Y |X = 2) =

(0 1 2 3

1/4 1/2 1/4 0

).

Por fim o caso X = 3, em que tres moedas sao lancadas. Y pode agora assumiros quatro valores (0, 1, 2 e 3) referidos acima. Um pouco de analise mostra queas suas probabilidades sao

P (Y |X = 3) =

(0 1 2 3

1/8 3/8 3/8 1/8

)


Agora que dispomos das probabilidades marginais de X e das probabilidadescondicionais de Y para os diferentes valores de X, podemos calcular as proba-bilidades conjuntas usando a regra do produto. Por exemplo,

P (X = 1 ∩ Y = 0) = P (Y = 0|X = 1)P (X = 1) =1

2× 1

2=

1

4

P (X = 1 ∩ Y = 1) = P (Y = 1|X = 1)P (X = 1) =1

2× 1

2=

1

4

P (X = 1 ∩ Y = 2) = P (Y = 2|X = 1)P (X = 1) = 0× 1

2= 0

P (X = 2 ∩ Y = 0) = P (Y = 0|X = 2)P (X = 2) =1

4× 1

3=

1

12,

e assim sucessivamente. Os resultados estao todos resumidos na tabela seguinte:

X Y 0 1 2 31 1/4 1/4 0 02 1/12 1/6 1/12 03 1/48 3/48 3/48 1/48

Ficam assim calculadas as probabilidades da variavel conjunta. Falta agoracalcular as probabilidades marginais da variavel Y , tarefa que levamos a cabousando a Eq. (4). A probabilidade de ocorrencia de cada valor de Y e iguala soma das probabilidades conjuntas correspondendo a esse valor de Y . Ouseja, considerando a tabela acima, essas probabilidades sao as somas, coluna acoluna, dos valores aı apresentados. Obtem-se o seguinte:

Y =

(0 1 2 3

17/48 23/48 7/48 1/48

).

Problemas1. A fraccao de canhotos na populacao geral e de cerca de 1%. Calcula a probabilida-

dede haver quatro ou mais canhotos num grupo de 200 pessoas.

2. De um baralho de 52 cartas, vao-se tirando cartas ao calhas, ate que surja o as decopas. (a) Qual o valor da probabilidade de que “saia” o as de cops logo na primeiratentativa? Qual a probabilidade de que isso so aconteca na segunda? Qual o valorda probabilidade de que sejam necessarias k escolhas? (b) Qual o valor expectaveldo numero de vezes que temos que tirar uma carta do baralho, ate ser escolhido oas de copas?

3. A letra “e”, sem acentos, ocorre no portugues escrito com uma probabilidade de0,1214. (a) Qual o valor expectavel do numero de “e” numa mensagem com 300caracteres? (b) Qual a probabilidade de o numero de “e” efectivamente presentesna mensagem ser, exactamente, o inteiro mais proximo do valor calculado na alınea(a)?

4. Um saco contem na bolas amarelas e nv bolas vermelhas. Uma bola e retirada dosaco de forma aleatoria e aı de novo recolocada, repetindo-se o processo N vezes.(a) Qual a probabilidade de sejam retiradas k bolas vermelhas (0 ≤ k ≤ N) noprocesso? (b) Mostre que a soma das probabilidades dos varios resultados possıveise 1. (c) Calcule o valor expectavel e a variancia da variavel aleatoria “numerode bolas vermelhas obtidas em N escolhas, com reposicao”. (d) Sejam na = 5,nv = 3; Calcule os valores numericos das varias probabilidades, o valor expectavelda variavel em estudo e a sua variancia.


5. A tabela mostra a distribuicao de probabilidade conjunta de duas variaveis aleatoriasx e y:

P (x ∩ y) y = 0 y = 1

x = 0 1/3 1/3

x = 1 0 2/3

(a) (a) Calcule as probabilidades marginais (p(x) e p(y)). (b) Calcule as probabi-lidades condicionadas P (y|x = 0)

6. Uma dada populacao humana foi sujeita a um inquerito em que se tentava averi-guar uma eventual ligacao entre a incidencia de escoliose (uma deformacao lateralda coluna vertebral) e a execucao de violino. Os resultados do inquerito sao osapresentados na tabela de probabilidades conjuntas seguinte

Toca violino Nao toca violino

Tem escolise 5× 10−4 4,95× 10−2

Nao tem escoliose 9,5× 10−3 9,405× 10−1

(a) Determine as probabilidades marginais das variaveis X = “Toca violino” e Y =”Tem escoliose”. (b) Calcule as probabilidades condicionais (X|Y ) (Y |X). (c) Hacorrelacao entre estas duas variaveis?

7. Uma pessoa dispoe de duas moedas. Uma e normal, com face “cara” e face “coroa”,a outra tem a “cara” impressa nas duas faces. Essa pessoa escolhe ao calhas umadas duas moedas e lanca-a duas vezes, registando o numero de vezes que a moedasai “cara”. Seja X a variavel aleatoria que representa a moeda escolhida e Y a querepresenta o numero de vezes que saiu “cara” nos dois lancamentos. (a) Calcule aprobabilidade conjunta das duas variaveis. (b) Calcule as probabilidades marginaisda variavel Y . (c) Calcule as probabilidades condicionais p(X|Y )

8. Um dado e lancado uma vez. Se o resultado for 1,2,3 ou 4, uma moeda e lancada;se o resultado do lancamento do dado for 5 ou 6, sao lancadas duas moedas. (a)Qual o valor expectavel do numero de vezes que sai “cara” no lancamento da oudas moedas? (b) Calcule as probabilidades conjuntas do resultado do lancamentodo dado (considere apenas os dois casos descritos) e do numero de vezes que saicara no lancamento da ou das moedas.

3 IGNORANCIA E INFORMACAO 15

3 Ignorancia e informacao

Antes de continuar devemos comecar por definir uma forma, objectiva e quan-titativa, de medir a informacao.

3.1 Como medir a informacao

A informacao que recebemos sobre um determinado assunto reduz a nossa ig-norancia sobre esse assunto. A quantidade de informacao que recebemos e iguala reducao de ignorancia que dela resulta.

Mais concretamente, imaginemos que partimos com uma quantidade de ig-norancia Hi e que, apos recebermos informacao, a ignorancia se reduz a Hf . Aquantidade de informacao que recebemos foi entao:

I = Hi −Hf . (8)

O problema que agora se poe e, obviamente, o de saber como medir, objectivae quantitativamente, a nossa ignorancia sobre determinado assunto.

3.2 Como medir a ignorancia

Em primeiro lugar, note-se que a nossa ignorancia sobre determinado assuntopode sempre ser representada por uma variavel aleatoria, ou um conjunto devariaveis aleatorias. Por exemplo, o partido que ganhara as proximas eleicoes(obviamente desconhecido, por enquanto) pode ser representado por uma vari-avel aleatoria cujos valores sao os nomes dos partidos a eleger. Que valor e quea variavel tomara, nao sabemos, embora haja possibilidades mais provaveis emenos provaveis, identificadas pelos resultados de anteriores eleicoes, estudosde opiniao, etc. De igual modo, se ignoramos o numero de jogadores de cadaequipa num jogo de futebol, podemos representa-lo atraves de uma variavelaleatoria que toma valores inteiros, e atribuir probabilidades aos varios valorespossıveis(2).

A nossa ignorancia pode nao ser representavel por uma variavel discretacomo as que temos consideramos nestes dois exemplos. Por exemplo, podemosrepresentar atraves de uma variavel aleatoria contınua a nossa incerteza sobre adistancia que poderemos percorrer com o deposito de combustıvel do automovelja na reserva. Ou pode acontecer que uma variavel aleatoria apenas (contınuaou nao) nao seja suficiente para descrever a nossa ignorancia. Por exemplo,para caracterizar a nossa ignorancia face ao resultado das proximas eleicoeslegislativas e presidenciais. Seja como for, deve ser claro destes exemplos quepodemos sempre usar variaveis aleatorias para descrever a nossa incerteza, ouignorancia, relativamente a um dado assunto ou objecto de estudo.

Por isso, vamos daqui em diante considerar o problema da medicao da incer-teza sempre em associacao a variaveis aleatorias abstractas, sem nos referirmosa situacoes concretas e especıficas que estabelecem relacoes entre essas variaveis

(2)Fazendo, por exemplo, um raciocıcio do tipo: “vi um bocado de um jogo na televisao,pareceram-me cerca de vinte jogadores, dez para cada lado... Digamos que as probabilidadespara o numero de jogadores que formam uma equipa de futebol sao p(8) = 0,05, p(9) =0,1, p(10) = 0,25, p(11) = 0,3, p(12) = 0,25, p(13) = 0,05, e todas as outras nulas.”


aleatorias e as limitacoes do nosso conhecimento. O formalismo tem menor difi-culdade tecnica se considerarmos apenas variaveis aleatorias discretas, pelo queapenas essas serao consideradas.

3.2.1 Tres requisitos a satisfazer pela medida da ignorancia

Vamos de seguida estabelecer tres requisitos que devem ser satisfeitos por qual-quer definicao quantitativa de incerteza razoavel.

1. Se forem equiprovaveis, quanto mais possibilidades houver, maior incer-tezaConsideremos, por exemplo, uma eleicao numa associacao recreativa, naassociacao academica ou num orgao administrativo da Universidade, aqual concorra apenas uma lista; e consideremos outra eleicao similar, masna qual concorram duas (ou tres, ou quatro...) listas, com probabilidadessemelhantes de vencerem a eleicao. Em que situacao consideramos maiora incerteza (ou ignorancia relativamente ao resultado da votacao)? Noprimeiro caso, em que ha apenas uma possibilidade (a lista unica vencecom certeza) nem podemos falar de incerteza: ela deve aı ter o valor zero.No caso em que ha duas listas com probabilidades semelhantes, a incertezaface ao resultado da votacao ja nao e nula, mas e menor do que se ouvertres, quatro ou cinco listas, se todas tiverem um numero semelhante deapoiantes.

2. Para um dado numero de possibilidades, e maior a incerteza se elas foremequiprovaveisConsideremos dois dados de seis faces. O primeiro e um dado normal,em que os varios valores “saem” com igual probabilidade; o segundo estaadulterado, de forma que o seis “sai” mil vezes mais frequentemente doque os restantes valores. Associada ao lancamento do primeiro dado haalguma incerteza, pois nao conseguimos prever de antemao o resultadodo lancamento. Em rigor, tambem nao podemos prever com toda a cer-teza o resultado do lancamento do dado adulterado, mas convenhamosque este resultado e muito menos incerto do que o do lancamento do dadoequilibrado. Temos a certeza, quase absoluta, de que no lancamento dosegundo dado obteremos um seis. O lancamento dado equilibrado tem as-sociada uma maior incerteza porque as probabilidades dos seus resultadossao todas iguais, ao contrario do que acontece com as dos do segundo.

3. A incerteza associada a duas variaveis independentes e igual a soma dasincertezas associadas a cada uma delasSejam X e Y duas variaveis aleatorias independentes. Sejam H(X) eH(Y ) as incertezas associadas a cada uma delas e seja H(XY ) a incertezaassociada ao conjunto das duas. Se as duas variaveis sao independentes,saber tudo sobre uma delas nao reduz em nada a incerteza relativamentea outra. Ou seja, subtraindo a incerteza conjunta a incerteza de uma dasvariaveis resta ainda a incerteza relativa a outra: a incerteza conjunta eentao a soma das incertezas.

Pode demonstrar-se (veja no Apendice B) que estes requisitos sao suficientespara definir a medida de incerteza. Aqui, tentaremos apenas “chegar,” portentativas mais ou menos inspiradas, a essa medida.


Tentativa 1: A incerteza e o numero de possibilidades: H1(X) = NX

O numero de valores que uma variavel aleatoria pode assumir satisfaz oprimeiro requisito imposto a uma medida de incerteza (ou seja, que elaaumente com o aumento de possibilidades) mas nao satisfaz os restantes.Em primeiro lugar, nao entra em linha de conta com as probabilidadesde ocorrencia dos varios resultados, logo, nao pode dar conta do segundorequisito (que a entropia seja maxima quando as probabilidades foremiguais). Em segundo lugar, dadas duas variaveis X e Y , se NX e NY

forem os respectivos numeros de possibilidades, a variavel conjunta XYpode assumir NXNY resultados. Se associamos o numero de possibilida-des a incerteza entao a incerteza conjunta de duas variaveis seria o produtodas incertezas e nao a soma, como impoe o terceiro requisito. Esta con-tradicao com o terceiro requisito tem ainda outro aspecto. Do terceirorequisito pode deduzir-se (ver o Apendice B) que a incerteza associadaa um acontecimento certo (ou seja, a uma variavel aleatoria com apenasum resultado possıvel) e nula. Mas nesta primeira tentativa, a funcao deincerteza nao se anula nem para acontecimentos certos.

Parte das insuficiencias desta tentativa podem resolver-se introduzindologaritmos(3), como veremos ja a seguir. Consideremos entao a

Tentativa 2: A incerteza e o logaritmo do numero de possibilidades: H2(X) = logNX

Esta nova tentativa satisfaz ainda o primeiro requisito, uma vez que asfuncoes logaritmo sao monotonas crescentes: quanto mais possibilidades,maior o valor do logaritmo, logo, maior a incerteza. E possıvel tambemsatisfazer o terceiro requisito. Como o logaritmo do produto de doisnumeros e a soma dos logaritmos de cada um, considerando de novo asduas variaveis independentes X e Y a que nos referimos acima, temos

H2(XY ) = log(NXNY ) = logNX + logNy = H2(X) + H2(Y ),

que e justamente o o que se pretende. Alem disso, uma vez que log 1 = 0,resulta nula a incerteza associada a um acontecimento certo. Apesar desatisfazer os requisitos 1 e 3, esta segunda tentativa nao satisfaz o segundorequisito. De facto, e como ja acontecia para a tentativa 1, esta definicaode incerteza considera-a apenas como funcao do numero de possibilidades,nao tendo em conta as suas probabilidades.

Mesmo nao sendo aceitavel como funcao de incerteza, esta segunda su-gestao pode ser escrita numa forma inspiradora para novas tentativas.Consideremo-la nos casos em que as varias possibilidades sao equipro-vaveis. Podemos escrever

H2(X) = logNX = − log1

NX= −NX

1

NXlog

1

NX

= −NX∑k=1

1

NXlog

1

NX

Mas 1/NX e a probabilidade de ocorrencia de cada um dos NX resultadospossıveis. Entao, considerando apenas situacoes associadas a variaveis

(3)Alguns leitores poderao beneficiar de uma leitura do Apendice A, sobre as propriedadesdas funcoes logarıtmicas, antes de continuar.


aleatorias com distribuicoes equiprovaveis, a tentativa 2 para uma de-finicao de incerteza pode escrever-se como

H2(X) = −NX∑k=1

pk log pk.

Sera esta uma forma aceitavel para a medida da ignorancia, mesmo emcasos em que a distribuicao de probabilidades nao e uniforme? Vejamos.

Tentativa 3: H3(X) = −∑pk log pk

Apliquemos esta tentativa para o caso de uma variavel aleatoria com nvalores possıveis equiprovaveis. Entao a probabilidade de cada valor epk = 1/n, de forma que a incerteza se reduz a

H3 = −n∑

k=1

pk log pk = −n∑

k=1

1

nlog

1

n= − log

1

n

= log n.

Assim, vemos que a incerteza aumenta se aumentar o numero de possibi-lidades, conforme o ditado pelo requisito 1.

Relativamente ao requisito 2, consideremos o caso particular de uma vari-avel aleatoria que pode apenas assumir dois valores, com probabilidadesp e q = 1− p. A incerteza associada a esta variavel aleatoria e

H3 = −p log p− (1− p) log(1− p).

O grafico desta funcao e o apresentado na Figura 3. Como se pode ver,a incerteza e maxima quando p = 1/2, ou seja, quando os dois resultadospossıveis tem a mesma probabilidade. Ou seja, no caso de haver apenas

H(p)

0

0.2

0.4

0.6

0.8

1

1.2

p0 0.2 0.4 0.6 0.8 1

Figura 3: Funcao de incerteza associada a uma variavel aleatoria com doisresultados possıveis, como funcao da probabilidade p de um deles.

dois resultados possıveis, esta definicao de probabilidade satisfaz tambem


o requisito 2. E possıvel demonstrar que isso se verifica tambem em ge-ral, para variaveis aleatorias com mais possibilidades, mas deixamos essademonstracao para o Apendice B.

Por fim, verifiquemos a concordancia com o requisito 3. Sejam X e Yduas variaveis aleatorias independentes,

X =

(x1 x2 . . . xNp1 p2 . . . pN

)Y =

(y1 y2 . . . yMq1 q2 . . . qM

).

Sejam pi, 1 ≤ i ≤ N e qj , 1 ≤ j ≤M , respectivamente, as probabilidadesde ocorrencia dos valores particulares X = xi e Y = yj . Seja aindaPij ≡ P (X = xi ∩ Y = yj) a probabilidade conjunta associada as duasvariaveis. Uma vez que as duas variaveis sao independentes, temos

Pij = piqj .

Podemos entao escrever a entropia conjunta das duas variaveis como

H3(XY ) = −N∑i=1

M∑j=1

Pij logPij = −N∑i=1

M∑j=1

piqj log piqj

= −N∑i=1

M∑j=1

piqj [log pi + log qj ]

= −N∑i=1

M∑j=1

piqj log pi −N∑i=1

M∑j=1

piqj log qj

= −

(N∑i=1

pi log pi

) M∑j=1

qj

−( N∑i=1

pi

) M∑j=1

qj log qj

Mas

∑pi =

∑qj = 1, de forma que obtemos

H3(XY ) = −N∑i=1

pi log pi −M∑j=1

qj log qj

= H3(X) + H3(Y ),

que e justamente o exigido pelo requisito 3. A forma H3 satisfaz entaoas tres condicoes impostas a uma medida da incerteza. No Apendice Bprovamos que e a unica funcao que pode satisfazer essas tres condicoes.

Acordemos entao em chamar incerteza, ignorancia, ou entropia associada auma variavel aleatoria X com distribuicao de probabilidades pi, 1 ≤ i ≤ N aquantidade

H(X) = −N∑i=1

pi log pi. (9)

Resta ainda considerar a escolha da base para o calculo dos logaritmos. Aescolha da base corresponde, simplesmente, a escolha das unidades com queexprimimos a incerteza. No contexto da teoria da informacao e praticamente


universal medir-se a incerteza (e, por conseguinte, a informacao, que nao e maisdo que a reducao de incerteza) em bits, opcao que corresponde a utilizacao delogarimos de base 2. Nestes apontamentos, e tambem seguida esta opcao, que,repito, e praticamente universal neste contexto. Assim, expressoes como log xdevem sempre ser entendidas como log2 x.

Problemas1. Calcule a incerteza associada ao resultado do lancamento de uma moeda.

2. Calcule a incerteza associada ao resultado do lancamento de um dado.

3. Calcule a incerteza associada a soma dos resultados do lancamento de dois dados.

4. O boletim meteorologico preve a ocorrencia de chuva num determinda dia com pro-babilidade 0,74. Qual o valor da entropia associada a ocorrencia (ou nao ocorrencia)de chuva nesse dia?

5. O sr. R.I. Caco e CEO de tres grandes empresas: a Macroflops, a SemiPronto e aEsmifros. Por essa razao esta sempre a “saltar” de sede para sede. Analizadoo seu dia-a-dia, constatou-se que ele passa 35% do seu tempo de trabalho naMacroflops, 30% na Semipronto, 20% na Esmifros e ainda 15% do seu tempo laboralnoutros locais, como os ministerios que tutelam as actividades das suas empresas,em reunioes com clientes e fornecedores, etc. Qual o valor da incerteza associadaa localizacao (Macroflops, SemiPronto, Esmifros ou outra) do sr. R.I. Caco numdeterminado instante?

3.3 Significado intuitivo da entropia

O resultado de uma experiencia aleatoria e tanto mais surpreendente quantomais improvavel for. Para dar uma expressao quantitativa ao conceito de sur-presa associado ao resultado de uma experiencia, podemos defini-la como osimetrico do logaritmo da probabilidade desse resultado:

S = − log p.

Quantificar assim a surpresa e razoavel: quanto maior o valor da probabilidadede um evento, menor a surpresa que ele causa; acontecimentos certos (p = 1)causam uma surpresa nula; acontecimentos quase impossıveis geram grandesurpresa (no limite da impossibilidade [p = 0], a surpresa e infinita). Usando estamedida de surpresa, podemos reescrever a incerteza associada a uma variavelaleatoria como

H(X) = −∑k

pk log pk =∑k

pkSk,

onde a soma e extendida a todos os valores possıveis da variavel aleatoria emquestao. Mas reconhecemos no lado direito da ultima igualdade o valor ex-pectavel da surpresa causada pelo conhecimento do valor assumido variavelaleatoria. Assim, a entropia associada a uma variavel aleatoria e o valor ex-pectavel da surpresa que o seu conhecimento causa.

Um segundo significado intuitivo da entropia esta relacionado com o Teo-rema da codificacao sem ruıdo que estudaremos mais adiante. Suponhamos quepretendemos saber que valor uma determinada variavel aleatoria assumiu, e que


para o fazer podemos apenas colocar questoes de resposta sim/nao a uma pes-soa que conhece o dito valor. O numero de questoes que devemos colocar paraobter o conhecimento que pretendemos pode ser maior ou menor, dependendodo acaso. Podemos obter a resposta que pretendemos logo a primeira, ou podemser necessarias muitas perguntas. O valor expectavel do numero de perguntasque temos que fazer esse depende apenas da estrategia usada (que perguntafazer de cada vez) e da variavel aleatoria. Verifica-se, no entanto que, qualquerque seja a estrategia, ha um mınimo para o valor expectavel do numero de per-guntas de resposta sim/nao que devemos fazer para determinarmos o resultadode uma experiencia aleatoria, e esse mınimo e exactamente a entropia associadaa experiencia aleatoria.

Ilustremos com um exemplo estas consideracoes. Suponhamos que pretende-mos conhecer o resultado obtido no lancamento de um dado, para o que fazemosa pessoa que o lancou um conjunto de perguntas de resposta sim/nao. Uma es-trategia possıvel consiste em perguntar se “saiu” o 1. Se a resposta for sim,temos o assunto resolvido, com apenas uma pergunta; se a resposta for naoperguntamos de seguida se “saiu” o 2, e assim sucessivamente. A Figura 4 re-presenta, no esquema da direita, a sequencia de perguntas a efectuar. Note-se

Figura 4: Duas estrategias para determinar com perguntas de resposta sim/naoo resultado do lancamento do dado. Dentro dos cırculos esta o numero deperguntas necessario para se obter cada determinacao.

que com esta estrategia, o resultado 1 e determinado fazendo apenas uma per-gunta, o 2 com duas perguntas, o 3 com tres perguntas, o 4 com quatro e o 5 e o6 ambos com cinco perguntas. Uma vez que a probabilidade de qualquer destesresultados e 1/6, o valor expectavel do numero de perguntas que devemos fazerpara obter a resposta e

〈N〉 =

6∑k=1

pkNk =1

6(1 + 2 + 3 + 4 + 5 + 5) ' 3,333.

A Figura 4 mostra tambem, a esquerda, o esquema de outra estrategia, outrasequencia de perguntas. Em vez de se comecar perguntando se o resultadoe um valor particular, perguntamos se e menor do que 4, ou seja, se e 1, 2ou 3. Daı em diante, o esquema e semelhante ao da primeira estrategia. Ovalor expectavel do numero de perguntas que devemos fazer para determinar o


resultado do lancamento do dado e, com esta nova estrategia,

〈N〉 =

6∑k=1

pkNk =1

6(4× 3 + 2× 2) ' 2,667.

Esta segunda estrategia e bastante mais eficiente do que a primeira: com menosperguntas em media, conseguimos obter o conhecimento pretendido. Mas agoracolocam-se as questoes: havera estrategias ainda mais eficientes? Havera limitespara a eficiencia? Nao sei a resposta a primeira questao, mas sei a da segunda:ha limites para a eficiencia; o valor mınimo do numero medio de perguntas deresposta sim/nao que devemos colocar para determinar o valor de uma variavelaleatoria e sempre maior ou igual do que a entropia associada a essa variavelaleatoria. No caso que aqui consideramos, tendo em conta que a entropia asso-ciada ao resultado do lancamento de um dado e log 6 ' 2,585 bits, vemos que aperformance da segunda estrategia se aproxima ja bastante do valor optimo.

3.4 Entropia conjunta e entropia condicional

Dadas duas variaveis aleatorias X e Y , nao necessariamente independentes, taisque X pode tomar N valores possıveis com probabilidades p1, p2,. . . , pN epode tomar M valores possıveis com probabilidades q1, q2,. . . , qM . A variavelconjunta pode tomar NM valores possıveis com as probabilidades

Pij ≡ P (X = xi ∩ Y = yj), 1 ≤ i ≤ N, 1 ≤ j ≤M.

A entropia associada a variavel conjunta XY e chamada a entropia conjuntadas duas variaveis e e entao dada por

H(XY ) = −N∑i=1

M∑j=1

Pij logPij . (10)

ExemploSejam X o resultado do lancamento de uma moeda (“cara” ou “coroa”) e Y o resultadodo lancamento de um dado (1, 2, 3, 4, 5, ou 6). A variavel XY pode tomar 12 resultados:(“cara” e 1), (“cara” e 2), . . . , (“cara” e 6), (“coroa” e 1), . . . , (“coroa” e 6). Comoas duas variaveis sao independentes, as probabilidades destes doze valores sao iguais aoproduto das probabilidades dos valores de X e de Y que o formam, ou seja, neste casotao simples, 1/2× 1/6 = 1/12. A entropia conjunta destas duas variaveis e entao

H(XY ) = −“coroa”∑i=“cara”

6∑j=1

Pij logPij = −12× 1

12log

1

12= log 12.

Note-se que a entropia conjunta destas duas variaveis e a soma das suas entropias margi-nais. Com efeito,

log 12 = log(2× 6) = log 2 + log 6,

que, como pode verificar por si, sao as entropias associadas ao lancamento da moeda edo dado, respectivamente.

No exemplo que acabamos de estudar, a entropia conjunta das duas variaveis eigual a soma das entropias marginais de cada uma delas. Isso deve-se ao facto de


as duas variaveis serem independentes (conhecermos o resultado do lancamentoda moeda nao altera em nada as probabilidades dos resultados do lancamentodo dado). Se considerarmos duas variaveis nao independentes, esta igualdadeja nao se verifica, como se constata atraves do seguinte exemplo.

ExemploLanca-se um dado; se o valor obtido for 1, 2, 3, ou 4, lanca-se uma moeda; se o valorobtido no dado for 5 ou 6, lancam-se duas moedas. Seja X a variavel relacionada comqual das duas possibilidades consideradas ocorreu no lancamento do dado e Y o numerode “caras” obtido no lancamento da ou das moedas. Designemos por “caso A” a situacaoem que se obtem no dado 1, 2, 3 ou 4, e por “caso B” aquela em que se obtem 5 ou 6.A variavel X e entao

X =

(A B

2/3 1/3

).

Quanto a variavel Y , sabemos que ela pode tomar os valores 0, 1 ou 2, mas nao conhecemosainda as suas probabilidades marginais. Mas conhecemos as probabilidades condicionadasaos diferentes valores de X. Sabendo que X = A, Y corresponde ao numero de carasque se obtem quando se lanca uma moeda: so pode portanto tomar os valores 0 e 1, comprobabilidades iguais a 1/2. Sabendo que X = B, Y corresponde ao numero de carasobtido no lancamento de duas moedas: toma os valores 0, 1 ou 2, com probabilidades1/4, 1/2 e 1/4, respectivamente. Com o conhecimento das probabilidades marginais davariavel X e das probabilidades condicionadas P (Y |X), podemos calcular as probabilidadesconjuntas. Por exemplo,

P (X = A ∩ Y = 0) = P (Y = 0|X = A)P (X = A) =1

2× 2

3=

1

3.

Repetindo o calculo para as restantes possibilidades (faca-o!) obtemos

P (X ∩ Y ) Y = 0 Y = 1 Y = 2

X = A 1/3 1/3 0X = B 1/12 1/6 1/12

A entropia conjunta destas duas variaveis e entao

H(XY ) = −B∑i=A

2∑j=0

P (xi ∩ yj) logP (xi ∩ yj)

= −2

3log

1

3− 2

12log

1

12− 1

6log

1

6

' 2,085 bits.

Para finalizar o estudo deste exemplo, calculemos as entropias marginais associadas asvariaveis X e Y . Da primeira ja conhecemos as probabilidades; Da segunda, devemosainda determina-las a partir das probabilidades conjuntas. Assim,

H(X) = H(1/2,1/2) = log 2 = 1 bit

H(Y ) = H(5/12,1/2,1/12) = 1,325 bits.

Verificamos agora que a entropia conjunta e menor que a soma das entropias associadasa cada uma das variaveis.

Dadas duas variaveis aleatorias X e Y ,

X =

(x1 x2 . . . xNp1 p2 . . . pN

)Y =

(y1 y2 . . . yMq1 q2 . . . qM

),


consideremos a variavel Y , sabendo que ocorreu um valor particular de X,digamos X = xi. Com essa condicionante, as probabiliades dos varios resultadospossıveis para Y sao as probabilidades condicionais P (Y |X = xi). Faz sentido,para esta variavel condicionada, calcular a entropia que lhe esta associada, eque, naturalmente, sera dada por

H(Y |X = xi) = −M∑j=1

P (Y = yj |X = xi) logP (Y = yj |X = xi). (11)

Chama-se a esta quantidade a entropia condicionada de Y, sabendo que ocorreo valor X = xi.

ExemploNum dado paıs, 2% da populacao esta infectada com uma certa doenca. No entanto,entre os cidadaos que integram o grupo de risco da doenca, essa percentagem sobe para15%. (a) Qual a entropia associada a possibiliade de infeccao por essa doenca de umindivıduo escolhido aleatoriamente na populacao do paıs? (b) Qual a entropia associadaa possibilidade de infeccao por essa doenca de um indivıduo escolhido aleatoriamente napopulacao que pertence ao grupo de risco?

Seja X a variavel aleatoria associada a possibilidade de infeccao, tomando os valoresX = 0 (o indivıduo esta sao) e X = 1 (o indivıduo tem a doenca). Seja Y a variavelaleatoria associada a pertenca ao grupo de risco, igualmente assumindo um de dois valores:Y = 0 (o indivıduo nao pertence ao grupo de risco) e Y = 1 (o indivıduo pertence aogrupo de risco).

A probabilidade de um cidadao qualquer estar infectado pela doenca e P (X = 1) =0,02; a probabilidade de ele nao estar infectado e, entao, P (X = 0) = 1 − 0,02 = 0,98.A entropia pedida na alınea (a) e entao

H(X) = −0,02 log 0,02− 0,98 log 0,98 = 0,14 bits.

Por outro lado, a entropia requerida na alınea (b) e a entropia condicional associada aposssibilidade do cidadao estar infectado, sabendo que ele pertence ao grupo de risco.Ora, a probabilidade de ele estar infectado, sabendo que pertence ao grupo de risco eP (X = 1|Y = 1) = 0,15; a probabilidade de ele nao estar infectado, sabendo quepertence ao grupo de risco e P (X = 0|Y = 1) = 1− 0,15 = 0,85. A entropia condicionale entao

H(X|Y = 1) = −0,15 log 0,15− 0,85 log 0,85 = 0,61 bits.

Se a variavel X assume um valor particular xi, a entropia que lhe estaassociada (a Y , entenda-se) reduz-se, do seu valor marginal H(Y ), a sua entropiacondicional sabendo que ocorreu X = xi, H(Y |X = xi). Esta reducao deentropia ocorre com probabilidade igual a da ocorrencia condicionante, ou seja,pi ≡ p(X = xi). O valor expectavel das entropias condicionadas de Y para todosos valores de X chama-se entropia condicional de Y conhecido X e representa-sepor H(Y |X)(4). Naturalmente, e dada por

H(Y |X) =

N∑i=1

piH(Y |X = xi). (12)

(4)Relativamente a notacao H(Y |X = xi) com que representamos a entropia condicional deY sabendo que occorreu X = xi, note-se que ja nao e especificado o valor concreto de X quecondiciona Y .


ExemploNuma comissao constituida por tres homens e quatro mulheres, e escolhido um porta-voz.Qual o valor da entropia condicional associada a pessoa escolhida, conhecido o seu sexo?

Numeremos os elementos da comissao, atribuindo os numeros 1 a 4 para as mulherese os numeros 5 a 7 para os homens. Seja X a variavel aleatoria que representa o sexo doporta-voz escolhido. Esta variavel pode tomar dois valores, digamos 0 (se e mulher) e 1(se e homem), com as probabilidades 3/7 e 4/7, respectivamente, dada a composicao dacomissao. Seja Y a variavel aleatoria que representa a pessoa escolhida. Y pode tomaros valores 1, 2, 3, 4, 5, 6 e 7, correspondendo aos numeros que atribuımos aos elementosda comissao. Uma vez que o portavoz e escolhido de forma aleatoria, as probabilidadesmarginais de Y sao todas iguais a 1/7. As duas variaveis sao entao

X =

(0 1

4/7 3/7

); Y =

(1 12 3 4 5 6 7

1/7 1/7 1/7 1/7 1/7 1/7 1/7

)Mas as probabilidades condicionadas de Y aos valores de X sao, e claro, diferentes:

P (Y |X = 0) =

(1 2 3 4 5 6 70 0 0 0 1/3 1/3 1/3

);

P (Y |X = 1) =

(1 2 3 4 5 6 7

1/4 1/4 1/4 1/4 0 0 0

).

A entropia condicional de Y sabendo que X = 0 (ou seja, sabendo que o porta-vozescolhido e do sexo femenino) e

H(Y |X = 0) = −7∑j=1

P (Y = j|X = 0) logPP (Y = j|X = 0) = log 4,

e a entropia condicional de Y sabendo que X = 1 (ou seja, sabendo que o porta-voz e dosexo masculino) e

H(Y |X = 1) = −7∑j=1

P (Y = j|X = 0) logPP (Y = j|X = 0) = log 3.

A entropia condicional associada a pessoa escolhida, conhecido o seu sexo, e entao

H(Y |X) =

1∑i=0

p(X = i)H(Y |X = i) =4

7H(Y |X = 0) +

3

7H(Y |X = 1) ' 1,82 bits.

3.5 Algumas propriedades da entropia

1. Como as probabilidades sao numeros reais compreendidos entre zero e um,os seus logaritmos sao sempre negativos (ou nulos, para acontecimentoscertos, ou seja, com probabilidade 1). Logo,

H = −∑k

pk log pk =∑k

pk (− log pk) ≥ 0 :

A entropia associada a uma variavel aleatoria e sempre um numero realnao negativo.


2. Consideremos uma variavel aleatoria que pode assumir N valores equi-provaveis. Entao a probabilidade de cada valor e 1/N , e portanto o valorda entropia associada a esta variavel e

H = −N∑

k=1

pk log pk = −N × 1

Nlog

1

N= logN.

Ou seja, a entropia associada a uma variavel com distribuicao de probabi-lidade uniforme e simplesmente o logaritmo do numero de possibilidades.

3. Se duas variaveis aleatorias sao independentes, a sua entropia conjunta eigual a soma das entropias associadas a cada uma delas, de acordo com oterceiro requisito. Mas, se as variaveis nao forem independentes, conheceruma delas da alguma informacao sobre a outra. Ou seja, por outras pa-lavras, ha uma ignorancia comum as duas ignorancias associadas a cadavariavel. Assim, se as duas variaveis nao sao independentes, a entropiaconjunta deve ser menor do que a soma das entropias associadas a cadavariavel.

Este argumento torna-se mais evidente com um exemplo. Considere umgrupo constituido por 110 mulheres e 90 homens. A uma das mulheres edada uma bola preta e as 109 restantes e dada uma bola branca; a umdos homens e dado uma bola branca, e aos 89 restantes e dada uma bolapreta. Entao, neste grupo constituıdo por 110 mulheres e 90 homens,cada um tem uma bola; 110 pessoas (109 mulheres e um homem) tembolas brancas, 90 pessoas (89 homens e uma mulher) tem bolas pretas. Aprobabilidade de uma pessoa deste grupo escolhida ao acaso ser mulhere p(M) = 110/200 = 0,55, e e igual a probabilidade de essa pessoa teruma bola branca. A entropia associada a qualquer destas duas variaveise H = −0,55 log 0,55− 0,45 log 0,45 = 0,99 bits.

Por outro lado, as probabilidades conjuntas sao(5) P (m∩ b) = 109/200 =0,545, P (m ∩ p) = P (h ∩ b) = 1/200 = 0,005, P (h ∩ p) = 89/200 = 0,445,de onde obtemos a entropia conjunta Hc = 1,07 bits. Constatamos assimque, neste caso, a entropia conjunta, longe ser igual a soma das duasentropias marginais, e so muito ligeiramente maior que qualquer delas.Isto verifica-se porque as duas variaveis aleatorias consideradas (“qual osexo da pessoa escolhida”, uma; “qual a cor da bola da pessoa escolhida”,a outra) sao, muito claramente, nao independentes. Da forma como asbolas foram atribuıdas as pessoas, saber que foi escolhida uma mulherda-nos uma grande confianca de que essa pessoa tenha uma bola branca;saber que a pessoa escolhida tem uma bola preta leva-nos a ter poucasduvidas de que se trata de um homem. Ignorar uma variavel e quaseigual a ignorar a outra; conhecer uma das variaveis e quase o mesmo queconhecer a outra.

Aceitemos entao, como conclusao geral, que

H(X,Y ) ≤ H(X) +H(Y ), (13)

verificando-se a igualdade se X e Y forem independentes. No Apendice Bapresenta-se uma demonstracao formal desta desigualdade.

(5)Usa-se aqui a notacao P (h∩p) para representar a probabilidade de a pessoa escolhida serhomem e ter uma bola preta, P (m ∩ b) a de essa pessoa ser mulher e ter bola branca, etc.


4. Dadas duas variaveis aleatorias, conhecer uma delas nao pode, em media,aumentar a nossa ignorancia relativamente a outra. Logo, a entropia con-dicional de uma, conhecida a outra deve ser menor do que a entropiamarginal da primeira. O maximo que pode acontecer e as duas variaveisserem independentes; nesse caso, conhecer uma delas nao reduz em nadaa entropia da outra, e portanto a entropia marginal de uma das variaveise a sua entropia condicional, conhecida a outra devem ser iguais. Ou seja,

H(Y |X) ≤ H(Y ), (14)

verificando-se a igualdade se as duas variaveis forem independentes. Con-sulte o Apendice B para seguir uma demonstracao desta desigualdade.

3.6 Informacao. Informacao mutua

Agora que estabelecemos uma medida de ignorancia, podemos voltar a definicaode informacao dada pela Eq. (8). Dadas duas variaveis aleatorias X e Y , aquantidade de informacao que recebemos sobre Y quando nos dizem que Xtem um determinado valor X = xi e igual a reducao na ignorancia de Y que oconhecimento desse facto implica:

I(Y ;X = xi) = H(Y )−H(Y |X = xi). (15)

ExemploA equipa A vence 60% dos jogos em que enfrenta as diversas equipas do campeonato quedisputa, mas e claramente superior a equipa B, ja que a vence em 80% dos jogos em queas duas equipas se enfrentam. Quanta informacao recebemos relativamente ao resultadodo proximo jogo da equipa A, sabendo que ela vai jogar com a equipa B?

Seja Y a variavel que representa o resultado do proximo da equipa A e X a variavelque representa a equipa que a equipa A deve defrontar nesse jogo. A entropia marginalrelativamente a vitoria ou derrota da equipa A e

H(Y ) = −0,6 log 0,6− 0,4 log 0,4 ' 0,97 bits.

A entropia relativamente a vitoria da equipa A, sabendo que ela jogara com a equipa B,por seu lado, e

H(Y |X = B) = −0,8 log 0,8− 0,2 log 0,2 ' 0,72 bits.

A informacao que recebemos relativamente a vitoria da equipa A, quando nos dizem queo jogo sera com a equipa B e entao

I(Y ;X = B) = H(Y )−H(Y |X = B) ' 0,25 bits.

Sejam ainda X e Y duas variaveis aleatorias. Chama-se informacao mutuasobre Y conhecido X a quantidade

I(Y ;X) = H(Y )−H(Y |X). (16)

Note-se a diferenca relativamente a Eq. (15): enquanto que aquela definia ainformacao sobre Y veiculada pelo conhecimento de que X assumia um valor


particular xi, a Eq. (16) define a informacao sobre Y veiculada pelo conheci-mento de X, sem especificar o valor concreto assumido por X. A bem dizer, ainformacao mutua de X sobre Y e o valor expectavel das informacoes veiculadaspelo conhecimento de que X assumiu cada um dos seus valores possıveis.

Analisando a Eq. (16) tendo em conta a desigualdade da Eq. (14), consta-tamos que a informacao mutua de uma variavel sobre outra e sempre positiva.Mas a informacao sobre uma variavel veiculada pelo conhecimento de que ou-tra tomou um valor concreto, essa, pode tomar qualquer valor real, positivo ounegativo. Vejamos esta questao com um exemplo.

ExemploA equipa A vence 80% dos jogos que realiza contra a equipa B. Considerando apenas osjogos que decorrem no estadio da equipa A, a percentagem de vitorias sobe para 90%;pelo contrario, considerando apenas os jogos que tem lugar no estadio da equipa B, apercentagem de vitorias da equipa A desce para os 70%. (a) Qual o valor da informacaorelativa a vitoria da equipa A num dado jogo, quando se sabe que esse jogo decorrera nocampo da equipa B? (b) Qual o valor da informacao mutua relativa a vitoria da equipa Anum dado jogo conhecido o campo onde ele tera lugar?

(a) Seja V a variavel aleatoria que associamos a equipa que ganha o jogo (V = A ouV = B) e c a que corresponde ao campo onde o jogo se da. A entropia marginal associadaa vitoria da equipa A e

H(V ) = −0,8 log 0,8− 0,2 log 0,2 = 0,64 bits.

Mas a entropia condicional associada a vitoria da equipa A, sabendo que o jogo se realizano campo da equipa B e

H(V |c = B) = −p(V = A|c = B) log p(V = A|B)−p(V = B|c = B) log p(V = B|c = B)

= −0,7 log 0,7− 0,3 log 0,3 = 0,88 bits.

Entao aplicando a definicao da Eq. (15), saber que o jogo decorrera no campo da equipaB fornece uma quantidade de informacao

I(V ; c = B) = H(V )−H(V |c = B) = 0,64− 0,88 = −0,24 bits < 0.

Ficamos mais ignorantes sobre o resultado do jogo quando sabemos que o jogo decorrerano campo da equipa B porque as probabilidades de vitoria das duas equipas se aproximamquando o jogo decorre neste campo.

(b) A entropia condicional relativa a vitoria da equipa A sabendo que o jogo decorrena campo da equipa B ja foi calculada. A mesma entropia condicional, mas sabendo agoraque o campo que acolhe o jogo e o da equipa A, e

H(V |c = A) = −p(V = A|c = A) log p(V = A|c = A)

− p(V = B|c = A) log p(V = B|c = A)

= −0,9 log 0,9− 0,1 log 0,1 = 0,47 bits.

Uma vez que os jogos entre as duas equipas acontecem alternadamente num ou no outrocampo, a probabilidade do jogo se realizar num ou no outro campo e 1/2. Entao a entropiacondicional relativa ao resultado do jogo conhecido o campo onde se realizara e

H(V |c) = p(c = a)H(V |c = a) + p(c = b)H(V |c = b)

=1

2× 0,47 +

1

2× 0,88 = 0,87 bits > 0.


3.7 Duas aplicacoes recreativas

Adivinhar um numero

Alice escolhe um numero inteiro s entre dois valores a e b, inclusive; Bernardotenta adivinhar o valor desse inteiro por tentativas. Em cada tentativa, Bernardopropoe uma hipotese h e Alice responde “e baixo demais” (se h < s), “e altodemais” (se h > s) ou “esta certo” (se h = s). Poe-se agora a questao: comodeve Bernardo escolher a hipotese h, de modo a adivinhar o valor de s no menornumero medio de tentativas? Intuitivamente, parece-nos evidente que Bernardodeve, em cada tentativa, “atirar” ao centro do intervalo de possibilidades, ouseja, deve escolher h = (a + b)/2. Vamos aplicar a teoria da informacao paraverificar essa intuicao.

Seja Rs(h) a resposta dada por Alice a hipotese h. R(h) tem tres valorespossıveis:

Rs(h) =

1 (“e baixo demais”), se h < s

2 (“e alto demais”), se h > s

3 (“esta certo”), se h = s

Seja H(s) a entropia associada ao valor do numero secreto s. Uma vez que, nointervalo [a,b] ha (b− a+ 1) possibilidades, temos

H(s) = log(a− b+ 1).

Em cada tentativa, a hipotese h a colocar por Bernardo deve ser aquela quemaximiza o valor expectavel da informacao fornecida pela resposta de Alice (istoe, por outras palavras, aquela que reduz ao mınimo a incerteza resultante), ouseja, a que maximiza o valor de

I(s;R(h)) = H(s)−H (s|Rs(h)) ,

sendo H (s|Rs(h)) o valor da entropia associada a s, conhecida a resposta dadapor Alice a tentativa h.

Face a uma hipotese h apresentada por Bernardo, ha tres possibilidades,resultantes da resposta de Alice. Analisemos separadamente essas tres possibi-lidades.

1. R(h) = 1, ou seja h < s. Se Alice disser a Bernardo que h < s, restamb − h possibilidades para s. A entropia associada ao valor de s reduz-se,entao, a

H (s|Rs(h)=1) = log(b− h).

A probabilidade de que Alice de esta resposta e igual ao numero de casosfavoraveis (b− h) a dividir pelo numero toal de casos (b− a+ 1), ou seja,

P (Rs =1) =b− h

b− a+ 1.

2. R(h) = 2, ou seja h > s. Se Alice nos diz que h > s, restam h − apossilidades, de forma que a entropia associada a s se reduz a

H (s|Rs(h)=2) = log(h− a);

4 CODIFICACAO SEM RUIDO 30

por outro lado, a probabilidade de que Alice de esta resposta a umahipotese h e igual a

P (Rs(h)=2) =h− a

b− a+ 1.

3. R(h) = 3, ou seja h = s. Se Alice der esta resposta a hipotese h, ficamosa conhecer o valor de s, logo a entopia que lhe esta associada reduz-se azero:

H(s|Rs(h)=3) = 0.

A probabilidade de que seja esta a resposta e, claro,

P (Rs(h)=3) =1

b− a+ 1

(ha apenas uma possibilidade favoravel ao acontecimento que estamos aconsiderar, para um total de b− a+ 1 de possibilidades).

A entropia condicional associada a s, conhecida a resposta dada por Alice ahipotese h e, de acordo com a definicao,

H (s|Rs(h)) =

3∑r=1

P (Rs(h)=r)H (s|Rs(h))

=b− h

b− a+ 1× log(b− h) +

h− ab− a+ 1

× log(h− a) +1

b− a+ 1× 0

A informacao que importa maximizar e, entao,

I (s;Rs(h)) = log(b− a+ 1)− (b− h) log(b− h) + (h− a) log(h− a)

b− a+ 1.

O nosso problema reduz-se agora a determinacao do valor de h que maximizaI(s;Rs(h)). Esse valor determina-se com a tecnica usual da analise matematica,ou seja, anulando a derivada de I(s;Rs(h)) em ordem a h. Essa derivada e

dI(s;Rs(h))

dh= −−(log(b− h) + 1) + (log(h− a) + 1)

b− a+ 1

=1

b− a+ 1log

b− hh− a

Esta expressao anula-se quando o argumento do logaritmo, no segundo membro,for igual a 1, isto e, quando

h =b+ a

2.

Ou seja, a hipotese mais produtiva, aquela de onde se retira, em media, maisinformacao, e aquela que “aponta” ao centro do intervalo de possibilidades,justamente aquela que a nossa intuicao sugeria.

Mastermind

[Falta escrever]

4 Codificacao sem ruıdo

[Falta escrever]

A PROPRIEDADES ELEMENTARES DOS LOGARITMOS 31

A Propriedades elementares dos logaritmos

Definicao

A funcao logaritmo e a funcao inversa da exponencial. Ou seja, dados b > 0(b 6= 1) e x > 0, entao

y = logb x⇔ x = by b > 0, b 6= 1, x > 0.

A funcao logaritmo nao esta definida para valores negativos do argumento, ouseja, logb x nao existe se x ≤ 0.

Representacao grafica

Figura 5: Graficos da funcao logaritmo de base 2 (linha contınua), de base e(linha tracejada) e de base 10 (pontilhada).

Algumas propriedades

1. logb(xy) = logb x+ logb y

2. logb(x/y) = logb x− logb y

3. logb(xa) = a logb x

4. logb 1 = 0

5. logb b = 1

6. loga x =logb x

logb a

A PROPRIEDADES ELEMENTARES DOS LOGARITMOS 32

DemonstracaoSejam α = logb x; β = logb y. Entao

1. logb(xy) = logb

(bαbβ

)= logb

(bα+β

)= α+ β = logb x+ logb y

2. logb(x/y) = logb

(bα/bβ

)= logb

(bαb−β

)= logb

(bα−β

)= α − β = logb x −

logb y

3. Caso A — α e inteiro. Entao a propriedade 3 resulta da propriedade 1. Caso B

— α = 1/n, com n inteiro. y = logb

(x1/n

)⇔ by = x1/n ⇔ (by)n = x ⇔

n logb (by) = logb x ⇔ y =1

nlogb x. Caso C — alpha e um numero racional (ou

seja, α = n/m, com n,m inteiros). Aplicam-se os casos A e B. Caso D — α eirracional. Neste caso, aceita-se a propriedade, servindo ate para definir potenciasde expoente irracional.

4. Resulta de 3 com α = 0.

5. y = logb b⇔ by = b⇔ y = 1.

6. y = loga x⇔ ay = x⇔ y logb a = logb x⇔ y = logb x/logb a

Nomenclatura e aspectos praticos

1. A expressao logb x le-se “logaritmo de base b de x”.

2. As bases mais frequentemente usadas sao a base e (Lei do decaimentoradioactivo, Lei de Beer-Lambert, carga/descarga de um condensador), abase 10 (escala de pH, escala decibelica, escala de Richter), e a base 2(definicao de bit).

3. A generalidade das calculadoras dispoem das funcoes loge x e log10 x, de-signadas respectivamente como lnx e log x. No entanto, a utilizacao danomenclatura ln nao e universal. Muitos autores usam log x para represen-tar o logaritmo natural (de base e), designando o de base 10 pela notacaopadrao log10.

4. Usa-se a propriedade 6 para calcular logaritmos de base arbitraria. Emparticular, e uma vez que as calculadoras nao dispoem, em geral, de loga-ritmos de base 2, podemos calcula-los como

log2 x =lnx

ln 2=

lnx

0,693(Logaritmos naturais)

ou

log2 x =log10 x

log10 2=

log10 x

0,301(Logaritmos decimais)

B DEMONSTRACAO DE ALGUMAS PROPOSICOES ENUNCIADAS 33

B Demonstracao de algumas proposicoes enun-ciadas

B.1 Um teorema auxiliar

Sejam pi, qi, 1 ≤ i ≤ N dois conjuntos de numeros reais, positivos e que somema 1, ou seja

∑pi =

∑qi = 1. Entao

−N∑i=1

pi log pi ≤ −N∑i=1

pi log qi, (17)

verificando-se a igualdade apenas se pi = qi, ∀i.DemonstracaoO logaritmo e uma funcao concava, isto e, o seu grafico fica sempre abaixo de qualquerdas suas tangentes, como se ve na Figura 6. Considerando em particular os logaritmos de

y

-4

-2

0

2

4

6

x0 1 2 3 4 5

log2 x(x-1)/ln 2

Figura 6: Grafico da funcao log2 x e da sua tangente no ponto x = 1.

base 2 e a tangente ao grafico no ponto x0 = 1, esta propriedade da funcao logaritmotraduz-se na desigualdade

log x ≤ x− 1

ln 2,

onde log x ≡ log2 x e ln 2 representa o logaritmo natural de 2. Tomemos, nesta expressao,x = qi/pi, 1 ≤ i ≤ N . Ela escreve-se entao como

logqipi≤ 1

ln 2

(qipi− 1

)=

1

ln 2

qi − pipi

,

de onde se obtem

pi logqipi≤ 1

ln 2(qi − pi) .

Usando agora a propriedade das funcoes logaritmo log a/b = log a− log b e somando paratodos os i, resulta

N∑i=1

pi log qi −N∑i=1

pi log pi ≤1

ln 2

(N∑i=1

pi −N∑i=1

qi

).


Mas os somatorios no lado direito tem ambos o valor 1, de acordo com uma das condicoesque impusemos aos conjuntos {pi} e {qi}. Logo, o lado direito desta desigualdade e nulo,e obtem-se, passando o primeiro termo no lado esquerdo para o lado direito

−N∑i=1

pi log pi ≤ −N∑i=1

pi log qi,

justamente o que se pretendia demonstrar.

B.2 −∑

pk log pk e a unica medida aceitavel de ignorancia

Antes de iniciarmos esta demonstracao, note-se que nao e necessario que a funcaode ignorancia que definimos nestes apontamentos seja a unica possıvel. Bastaque ela seja, como e, uma definicao razoavel, ou seja, que satisfaca os tresrequistos apresentados na Seccao 3.2.1. Mas e bom que ela seja unica porqueisso torna-a universal sem ser necessario impor convencoes, sempre mais oumenos arbitrarias. [Falta escrever]

B.3 −∑

pk log pk e maxima se os pk forem todos iguais

DemonstracaoComo se viu na Seccao 3.5 (mais especificamente, ver a propriedade 2), a entropia asso-ciada a uma variavel aleatoria que toma N resultados possıveis com iguais probabilidadesqi = 1/N tem o valor HN = logN . Consideremos a desiguladade da Eq. (17) no casoem que os qi sao todos iguais:

H(pi) = −N∑i=1

≤ −∑i=1

Npi log1

N= − log

1

N= logN = HN ,

o que conclui a demonstracao.

B.4 H(X,Y ) ≤ H(X) + H(Y )

DemonstracaoSejam X e Y as variaveis aleatorias

X =

(x1 x2 . . . xNp1 p2 . . . pN

)Y =

(y1 y2 . . . yMq1 q2 . . . qM

).

A variavel conjunta XY toma N ×M valores e sejam Pij , 1 ≤ i ≤ N, 1 ≤ j ≤M as ausprobabilidades de ocorrencia(6). Recordemos aqui que as probabilidades marginais pi e qjsatisfazem as igualdades

pi =

M∑j=1

Pij qj =

N∑i=1

Pij .

(6)Se X e Y forem independentes, Pij = piqj .


Entao as entropias marginais de X e Y podem ser escritas como

H(X) = −N∑i=1

pi log pi = −N∑i=1

M∑j=1

Pij log pi

H(Y ) = −M∑j=1

qj log qj = −N∑i=1

M∑j=1

Pij log qj

Entao

H(X) +H(Y ) = −N∑i=1

M∑j=1

Pij log pi −N∑i=1

M∑j=1

Pij log qj

= −N∑i=1

M∑j=1

Pij (log pi + log qj) = −N∑i=1

M∑j=1

Pij log(piqj)

≥ −N∑i=1

M∑j=1

Pij logPij ,

onde a ultima desigualdade e uma expressao do teorema auxiliar da Eq (17). Mas asoma do ultimo termo e exactamente a entropia conjunta das duas variaveis, pelo que ficaconcluıda a demonstracao.

B.5 H(Y |X) ≤ H(Y )

DemonstracaoDe acordo com a sua definicao, dada na Eq. (12), a entropia condicional e

H(Y |X) =

N∑i=1

piH(Y |X = xi) = −N∑i=1

M∑j=1

P (yj |xi)pi logP (yj |xi).

Usando aqui a expressao da probabilidade condicional, esta expressao reescreve-se como

H(Y |X) = −N∑i=1

M∑j=1

Pij logPijpi

= −N∑i=1

M∑j=1

Pij (logPij − log pi)

= −N∑i=1

M∑j=1

Pij logPij +N∑i=1

M∑j=1

Pij log pi

= −N∑i=1

M∑j=1

Pij logPij +

N∑i=1

pi log pi = H(X,Y )−H(X).

Considerando agora a desigualdade demonstrada na Seccao B.4, obtemos

H(Y |X) ≤ H(Y ),

como se pretendia demonstrar.

C “ENTROPIA”?! PORQUE ESTA PALAVRA? 36

C “Entropia”?! Porque esta palavra?

[Falta escrever]

Brev ssima introduc˘~ao a teoria da informac˘ao~amoreira/lectnotes/fisinf.pdf · Brev ssima...

Documents

Transcript of Brev ssima introduc˘~ao a teoria da informac˘ao~amoreira/lectnotes/fisinf.pdf · Brev ssima...