Concept d'ensemble typique

15

Je pensais que le concept d'ensemble typique était assez intuitif: une séquence de longueur n appartiendrait à l'ensemble typique si la probabilité de sortie de la séquence était élevée. Donc, toute séquence qui serait probable serait dans . (J'évite la définition formelle liée à l'entropie parce que j'essaie de la comprendre qualitativement.) A ( n ) ϵUNEϵ(n)UNEϵ(n)

Cependant, j'ai lu que, en général, la séquence la plus probable n'appartient pas à l'ensemble typique. Cela m'a beaucoup dérouté.

Existe-t-il une définition intuitive de l'ensemble typique? Ou s'agit-il simplement d'un outil mathématique qui n'a pas grand-chose à voir avec le bon sens?

Tendero
la source

Réponses:

13

Je sais que vous avez explicitement demandé une explication intuitive et de laisser de côté la définition formelle, mais je pense qu'ils sont plutôt liés, alors permettez-moi de rappeler la définition de l'ensemble typique:

X1,X2,...sontiidvariables aléatoires p(x) , alors l'ensemble typiqueAϵ(n) par rapport àp(x) est l'ensemble des séquences(x1,x2,...,xn)χn avec la propriété

(1)2n(H(X)+ϵ)p(x1,x2,...,xn)2n(H(X)ϵ)
Cela signifie que pour un fixeϵ, l'ensemble typique est composé de toutes les séquences dont les probabilités sontprochesde2nH(X). Donc, pour qu'une séquence appartienne à l'ensemble typique, elle doit simplement avoir une probabilité proche de2nH(X) , ce n'est généralement pas le cas. Pour comprendre pourquoi, permettez-moi de réécrire l'équation 1 en y appliquantlog2 .

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

Maintenant, la définition d'ensemble typique est plus directement liée au concept d'entropie, ou énoncée d'une autre manière, l'information moyenne de la variable aléatoire. Le moyen terme peut être considéré comme l'entropie échantillon de la séquence, donc l'ensemble typique est faite par toutes les séquences qui nous donnent une quantité d'information à proximité de l'information moyenne de la variable aléatoire X . La séquence la plus probable nous donne généralement moins d'informations que la moyenne. N'oubliez pas que plus la probabilité d'un résultat est faible, plus les informations qu'il nous donne seront élevées. Pour comprendre pourquoi permettez-moi de donner un exemple:

Supposons que vous vivez dans une ville dont le temps est très susceptible d'être ensoleillé et chaud, entre 24 ° C et 26 ° C. Vous pouvez regarder le bulletin météo tous les matins, mais vous vous en foutez, je veux dire, il fait toujours beau et chaud. Mais que se passe-t-il si un jour l'homme / la femme météo vous dit qu'aujourd'hui sera pluvieux et froid, cela changera la donne. Vous devrez utiliser des vêtements différents et prendre un parapluie et faire d'autres choses que vous n'avez pas l'habitude, donc l'homme météo vous a donné une information vraiment importante.

Pour résumer, la définition intuitive de l'ensemble typique est qu'il se compose de séquences qui nous donnent une quantité d'informations proche de celle attendue de la source (variable aléatoire).

diegobatt
la source
1
... ou plutôt $$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, mais quel est le but de l'ensemble typique défini de cette façon, alors? Auparavant, je pensais que nous avions créé une notion d'ensemble typique pour avoir une intuition que LE PLUS PETIT sous-ensemble de séquences que nous devons prendre pour nous assurer de "couvrir" (1 - \ eps)% cas. De cette façon, prendre la séquence la plus probable est un choix évident. Qu'est-ce que je rate?
tomwesolowski
12

La réponse de Diegobatt explique bien intuitivement ce qu'est un ensemble typique. Cette réponse répondra à l'autre question du PO, reprise par @tomwesolowski: pourquoi définiriez-vous l'ensemble typique de manière à exclure les éléments les plus probables?

La réponse courte est que l' ensemble typique est avant tout un outil mathématique. Il a été défini pour aider à prouver quelque chose, et cette définition est la plus pratique pour la preuve. C'est un bon exemple de la façon dont les besoins théoriques peuvent parfois l'emporter sur les préférences intuitives en mathématiques.

L'ensemble typique a été défini par le père de la théorie de l' information , Claude Shannon . Il voulait déterminer l'efficacité avec laquelle on pourrait éventuellement coder un flux de symboles d'un alphabet fixe, en supposant que chaque symbole est un échantillon aléatoire iid d'une certaine distribution. Ses idées clés étaient les suivantes:

  1. Il existe un ensemble relativement petit de séquences "typiques" facilement identifiables qui apparaissent de manière disproportionnée souvent dans le flux.
  2. L'attribution de cet "ensemble typique" de séquences aux codages les plus courts donne un codage efficace de manière optimale (asymptotiquement, car la sortie du flux augmente arbitrairement).

L'ensemble typique découvert par Shannon est composé précisément des séquences dont l' auto-information , ou «surprenante nesse», est à peu près la même que l'auto-information attendue , en moyenne, pour la distribution de la source du flux. De telles séquences sont "typiques" dans le sens où leurs informations sont dans la moyenne, mais cette définition exclut implicitement les séquences qui ont beaucoup moins d'informations que la moyenne. Ces séquences moins informatives sont également les plus probables.

Comme le note l'OP, ce n'est pas intuitivement attrayant! À première vue, l'ensemble typique sonne comme s'il devrait contenir toutes les séquences les plus probables jusqu'à un certain seuil. Cela représenterait mieux ce qui est généralement vu dans le flux.

Mais Shannon ne voulait pas de l'ensemble typique le plus "typique" possible; il en voulait un qui facilitait la preuve du résultat qu'il voulait prouver. Il est garanti que l'ensemble typique défini par Shannon existe, qu'il est petit et qu'il est à peu près aussi petit que tout autre ensemble que vous pourriez proposer, comme le souligne cette réponse . L'ajout des éléments les plus probables rend l'ensemble plus probable, ce qui est bien, mais il agrandit également l'ensemble, ce qui est mauvais. Si tout ce dont vous vous souciez est de faire votre preuve, pourquoi réparer ce qui n'est pas cassé?

Si vous avez des objectifs différents de Shannon, votre concept de typicité préféré pourrait également être différent. Par exemple, dans le codage Huffman , les symboles (ou séquences de symboles) les plus probables obtiennent les codes les plus courts. Dans un certain sens technique, le codage Huffman est la solution optimale au problème original de Shannon, et il capture mieux notre intuition sur la typicité. D'un autre côté, la définition de Shannon de la typicité est plus pratique pour prouver les choses.

Paul
la source
1
Excellent raisonnement et bravo pour un travail bien fait en comblant l'écart entre l'intuition et la définition. Je dirais que cet écart se produit en raison d'une lacune linguistique de la vie quotidienne où typique et moyenne signifient généralement la même chose, mais en termes de statistiques, le typique (au sens de la probabilité, c'est-à-dire le mode) n'est pas nécessairement le même que la moyenne , c'est-à-dire la valeur attendue.
Emil
H(X)-εH(X)+ε
@Emil, je suppose que l'auteur l'a dit de cette façon, car nous avons tous convenu que les séquences contenant plus d'informations (moins probables) ne devraient pas être contenues dans un ensemble typique.
tomwesolowski
1

L'idée d'un ensemble typique traite implicitement les séquences de résultats comme des ensembles multiples, c'est-à-dire qu'elle suppose que vous vous souciez juste de l'histogramme de chaque séquence, par exemple, vous considérez les 10 séquences de lancer de pièces avec 7 têtes et 3 queues comme équivalentes.

p(H)=.9

Le résultat important est que pour des séquences suffisamment longues, presque toutes les séquences échantillonnées auront été arbitrairement proches des fréquences attendues, c'est-à-dire que la distribution deviendra extrêmement maximale lorsque la longueur des séquences considérées augmentera.

dix5P(H)=.9dix4+/-300

Un ensemble typique est une version plus générale et théoriquement définie de cette idée.

Daniel Mahler
la source
0

Selon le théorème 6.3 de ces notes de cours, peu importe si nous prenons un sous-ensemble de séquences avec la probabilité la plus élevée ou celles avec une probabilité proche de2-nH(X) (à partir d'un ensemble typique), nous devons prendre environ 2nHpour vous assurer que le sous-ensemble choisi contient une séquence aléatoire avec une probabilité élevée. Nous prenons généralement des éléments d'ensemble typiques, car nous pouvons en délimiter la taille plus facilement.

tomwesolowski
la source
1
Pourriez-vous expliquer comment cela répond à la demande de "définition intuitive d'un ensemble typique"?
whuber
Je ne suis pas sûr, mais cela voulait dire "Cependant, j'ai lu qu'en général, la séquence la plus probable n'appartient pas à l'ensemble typique. Cela m'a beaucoup dérouté." une partie de la question :)
tomwesolowski