Conceito típico de conjunto

14

Eu pensei que o conceito de conjunto típico fosse bastante intuitivo: uma sequência de comprimento pertenceria ao conjunto típico se a probabilidade de saída da sequência fosse alta. Portanto, qualquer sequência que provavelmente estivesse em . (Estou evitando a definição formal relacionada à entropia porque estou tentando entendê-la qualitativamente.)A ( n ) ϵnUMAϵ(n)UMAϵ(n)

No entanto, li que, em geral, a sequência mais provável não pertence ao conjunto típico. Isso me confundiu muito.

Existe uma definição intuitiva de conjunto típico? Ou é apenas uma ferramenta matemática que não tem muito a ver com o bom senso?

Tendero
fonte

Respostas:

11

Sei que você solicitou explicitamente uma explicação intuitiva e deixou de fora a definição formal, mas acho que elas são bastante relacionadas, então, lembre-se da definição de conjunto típico:

X1,X2,...sãoiidvariáveis aleatórias p(x) , em seguida, o conjunto típicoAϵ(n) com respeito aop(x) é o conjunto de sequências(x1,x2,...,xn)χn com a propriedade

(1)2n(H(X)+ϵ)p(x1,x2,...,xn)2n(H(X)ϵ)
Isto significa que para um fixoϵ, o conjunto típico é composta por todas as sequências cujas probabilidadespróximoa2nH(X) . Portanto, para que uma sequência pertença ao conjunto típico, ela só precisa ter uma probabilidade próxima a2nH(X) , mas geralmente não. Para entender por que, deixe-me reescrever a equação 1, aplicando log2 nele.

(2)H(X)ϵ1nlog2(1p(x1,x2,...,xn))H(X)+ϵ

Agora, a definição típica de um conjunto está mais diretamente relacionada ao conceito de entropia ou, de outra forma, à informação média da variável aleatória. O termo meio pode ser pensada como a entropia amostra da sequência, assim, o conjunto típico é feito por todas as sequências que estão nos dando uma quantidade de informação perto da informação média da variável aleatória X . A sequência mais provável geralmente nos fornece menos informações que a média. Lembre-se de que, quanto menor a probabilidade de um resultado, maior será a informação que ele nos fornecer. Para entender por que, deixe-me dar um exemplo:

Vamos supor que você mora em uma cidade cujo clima é altamente provável de ser ensolarado e quente, entre 24 ° C e 26 ° C. Você pode assistir ao boletim meteorológico todas as manhãs, mas não se importaria muito com isso, quero dizer, é sempre ensolarado e quente. Mas e se algum dia o homem / mulher do tempo lhe disser que hoje estará chuvoso e frio, isso muda o jogo. Você terá que usar roupas diferentes, levar um guarda-chuva e fazer outras coisas que normalmente não usa, para que o meteorologista tenha lhe dado uma informação realmente importante.

Em resumo, a definição intuitiva do conjunto típico é que ele consiste em sequências que nos fornecem uma quantidade de informação próxima à esperada da fonte (variável aleatória).

diegobatt
fonte
1
... ou melhor $$H(X)-\epsilon\le \frac{1}{n}log_2(\frac{1}{p(x_1,x_2,...,x_n)}) \le H(X)+\epsilon \tag{2}$$...
Cbhihe
OK, mas qual é o objetivo do conjunto típico definido dessa maneira? Anteriormente, pensei que criamos uma noção de conjunto típico para ter uma intuição que O menor subconjunto de seqüências que precisamos seguir para garantir que "cubram" (1 - \ eps)% casos. Dessa maneira, tomar a sequência mais provável é uma escolha óbvia. o que estou perdendo?
Tomwesolowski
10

A resposta de Diegobatt faz um bom trabalho ao explicar intuitivamente qual é o conjunto típico. Essa resposta abordará a outra pergunta do OP, ecoada por @tomwesolowski: por que você definiria o conjunto típico de uma maneira que exclua os elementos mais prováveis?

A resposta curta é que o conjunto típico é principalmente uma ferramenta matemática. Foi definido para ajudar a provar algo, e essa definição é a mais conveniente para a prova. É um bom exemplo de como as necessidades teóricas às vezes podem superar as preferências intuitivas em matemática.

O conjunto típico foi definido pelo pai da teoria da informação , Claude Shannon . Ele queria determinar a eficiência se poderia codificar um fluxo de símbolos de um alfabeto fixo, assumindo que cada símbolo é uma iid amostra aleatória de alguma distribuição. Suas idéias principais foram:

  1. Existe um conjunto relativamente pequeno e facilmente identificável de sequências "típicas" que aparecem desproporcionalmente com frequência no fluxo.
  2. Atribuir a esse "conjunto típico" de seqüências as codificações mais curtas produz uma codificação idealmente eficiente (assintoticamente, à medida que a saída do fluxo cresce arbitrariamente longa).

O conjunto típico descoberto por Shannon é composto precisamente pelas seqüências cuja auto-informação , ou "surpresa", é quase a mesma que a auto-informação esperada , em média, para a distribuição de fontes do fluxo. Tais seqüências são "típicas" no sentido de que suas informações são sobre a média, mas essa definição exclui implicitamente aquelas sequências que possuem significativamente menos informações que a média. Essas seqüências menos informativas também são as mais prováveis.

Como observa o OP, isso não é intuitivamente atraente! Por sua vez, o conjunto típico parece que deve conter todas as seqüências mais prováveis ​​até algum limite. Isso representaria melhor o que normalmente é visto no fluxo.

Mas Shannon não queria o conjunto típico mais "típico" possível; ele queria um que facilitasse provar o resultado que ele queria provar. É garantido que o conjunto típico definido por Shannon existe, é pequeno e é tão pequeno quanto qualquer outro conjunto que você possa propor, como aponta esta resposta . Adicionar os elementos mais prováveis ​​aumenta a probabilidade do conjunto, o que é bom, mas também aumenta o conjunto, o que é ruim. Se tudo o que importa é fazer sua prova, por que consertar o que não está quebrado?

Se você tem objetivos diferentes de Shannon, seu conceito preferido de tipicidade também pode ser diferente. Por exemplo, na codificação de Huffman , os símbolos mais prováveis ​​(ou sequências de símbolos) obtêm os códigos mais curtos. Em certo sentido técnico, a codificação de Huffman é a solução ideal para o problema original de Shannon e captura melhor nossa intuição sobre a tipicidade. Por outro lado, a definição de tipicidade de Shannon é mais conveniente para provar as coisas.

Paulo
fonte
1
Excelente raciocínio e parabéns por um trabalho bem feito, abordando a lacuna entre intuição e definição. Eu diria que essa discrepância ocorre devido a uma falta de linguagem da vida cotidiana em que típico e médio geralmente significam a mesma coisa, mas em termos estatísticos, o típico (no sentido de probabilidade, ou seja, modo) não é necessariamente o mesmo que a média , ou seja, valor esperado.
Emil
H(x)-εH(x)+ε
@ Emil, presumo que o autor tenha dito dessa maneira, porque todos concordamos que seqüências com mais informações (menos prováveis) não deveriam estar contidas no conjunto típico.
tomwesolowski
1

A idéia de um conjunto típico trata implicitamente as seqüências de resultados como multisets, ou seja, assume que você se preocupa apenas com o histograma de cada sequência, por exemplo, você considera todas as 10 sequências de sorteio com 7 cabeças e 3 caudas como equivalentes.

p(H)=.9

O resultado importante é que, para seqüências suficientemente longas, quase todas as seqüências amostradas estarão arbitrariamente próximas das frequências esperadas, ou seja, a distribuição se torna extremamente alta à medida que a duração das sequências consideradas aumenta.

105P(H)=.9104+/-300

Conjunto típico é uma versão mais geral, teoricamente definida, dessa idéia.

Daniel Mahler
fonte
0

De acordo com o teorema 6.3 nestas notas de aula, não importa se tomamos um subconjunto de seqüências com maior probabilidade ou com probabilidade próxima de2-nH(X) (do conjunto típico), precisamos levar aproximadamente 2nHpara garantir que o subconjunto escolhido contenha sequência aleatória com alta probabilidade. Normalmente, usamos elementos de conjunto típicos, porque podemos limitar o tamanho dele com mais facilidade.

tomwesolowski
fonte
1
Você poderia explicar como isso aborda a solicitação de "definição intuitiva de conjunto típico"?
whuber
Não tenho certeza, mas pretendia abordar "No entanto, li que, em geral, a sequência mais provável não pertence ao conjunto típico. Isso me confundiu bastante." parte da pergunta :)
tomwesolowski