Die Verbundentropie bzw. Blockentropie ist die Verallgemeinerung der Shannonentropie für eine multivariate Zufallsvariable.

Sei X eine multivariate Zufallsvariable (ein Zufallsvektor) Länge k und x eine Realisierung von X über einer Symbolmenge Z (beispielsweise eine DNA-Sequenz mit Z={A,G,C,T}). Sei weiterhin I eine Information (z.B. ein Text) der Länge n>k über der gleichen Symbolmenge Z. Betrachtet man nun eine Realisierung x als eine Folge von Symbolen x_j aus z (genannt Block), dann gibt die Verbundwahrscheinlichkeit

an, wie groß die Wahrscheinlichkeit ist, dass ein bestimmter k-Zeichen-Block in I vorkommt. Die Menge aller möglichen Realisierungen bzw. Blöcke sei [X]_k. Man kann darüber die Blockentropie definieren:

Die Menge [X]_k wird in den meisten Fällen auch Realisierungen enthalten, die nicht in I vorkommen, also p_k(x)=0. Die Anzahl aller möglichen Realisierungen |[X]_k| ist gemäß Kombinatorik gegeben durch:

| [X]_k | = | Z | ^k

Eine allgemeinere Formulierung der Verbundentropie H(X₁,X₂) für zwei Zufallsvariablen X₁ und X₂ ist gegeben durch

H(X₁,X₂) = H(X₁) + H(X₂ | X₁)

die Summe aus der Entropie von X₁ und der bedingten Entropie von X₂ unter gegebenem X₁. Sind X₁ und X₂ unabhängig, dann gilt (äquivalent zur bedingten Wahrscheinlichkeit):

H(X₁,X₂) = H(X₁) + H(X₂)

Die bedingte Entropie wird im Folgenden erläutert.

Bedingte Entropie

Die bedingte Entropie von zwei Zufallsvariablen X und Y ist die Unsicherheit über Y, die verbleibt, wenn X bereits bekannt ist. Sind X und Y voneinander unabhängig, dann bleibt die Entropie von Y vollständig erhalten. Sind X und Y aber voneinander abhängig, dann kann die bedingte Entropie kleiner sein als im unabhängigen Fall.

Formal ist die bedingte Entropie H(X|Y) definiert durch:

Für den Fall, dass X und Y unabhängig sind, ergibt sich:

H(Y | X) = H(Y)

Übertragen auf eine multivariate Zufallsvariable X der Länge k (siehe oben), als Darstellung für einen k-Block von Symbolen (x₁,..,x_k), lässt sich die bedingte Entropie h_k definieren als die Unsicherheit eines Symbols x_k+1 (nach einem bestimmten vorgegebenen k-Block):

h_k: = H_{k + 1} - H_k , mit h₀: = H₁

wobei H_k+1 bzw. H_k die Blockentropie ist.

Der zweidimensionale Fall

Wenn das Auftreten eines Zeichens x_i nur vom vorherigen Zeichen x_j abhängt (wie etwa in der "101010..."-kette) erhält man aus

H(X,Y) =	?	?	p(xi,yj)logp(xi,yj)
	i	j

und

p(x_i,y_j) = p(x_i)p(y_j | x_i)

den Ausdruck

wobei x_i den Zustand, d.h. die Folge der vorhergehenden Symbole, bezeichnet und p(y_j|x_i) ist die bedingte Wahrscheinlichkeit von y_j gegeben x_i. Die Verbundwahrscheinlichkeit von x_i und y_j, p(x_i,y_j) ist wiederum die Wahrscheinlichkeit des gemeinsamen Auftretens von x_i und y_j.

Es folgt für die bedingte Entropie h₁, also die Unsicherheit eines Symbols nach einem 1-Block:

h1 = H2 - H1 = H(X) + H(Y | X) - H(X) = H(Y | X) = -	?	p(xi)	?	p(yj | xi)log2p(yj | xi)
	i		j

Quellentropie

Schließlich ist zu bemerken, dass die beiden vorgenannten Definitionen im Grenzübergang gleichwertig sind; man erhält einen Ausdruck, der die Entropie pro Symbol unabhängig von der Blocklänge beschreibt, die so genannte Quellentropie (source entropy):

Es gelten die Ungleichungen

Siehe auch

Kullback-Leibler Entropie, Zeitreihenanalyse

Weblinks

• http://www.data-compression.com/theory.html#entropy
• http://et.ti.uni-mannheim.de/lehre/skripten/et/et16.pdf
• http://summa.physik.hu-berlin.de/~frank/download/web-tueb.pdf