Erwartungswert von Hamming Distanz

[Manki E. (manki)]

Die Hamming Distanz ist so definiert (a und c sind vektoren in denen 
Bitfolgen drinnenstehen):

$$\text{dist}(\vec{a},\vec{c}) = \sum_{i=0}^{n-1} \text{dist}(a_i,c_i) \text{ mit dist}(a_i, c_i) =\left\{\begin{matrix} 1 & \text{fuer } a_i \neq c_i\\ 0 & \text{fuer } a_i = c_i \end{matrix}\right.$$

Der Erwartungswert ist so definiert:

$$E[X] = \sum_{i = 1}^L x_i P(X = x_i)$$

Wie kann ich den Erwartungswert der Hamming Distanz berechnen? Ich 
verstehe garnicht was das ist? Also das hier:

$$E[\text{dist}(\vec{a}, \vec{c})]$$

Mein Buch sagt, dass es n/2 ist. Also das rauskommen soll:

$$E[\text{dist}(\vec{a}, \vec{c})] = \frac{n}{2}$$

Aber ich kann das irgendwie nicht nachvollziehen...

[Tim S. (tim_seidel)]

Der Erwartungswert wie du Ihn aufgeschrieben hast ist nichts anderes als 
ein gewichteter Durchschnitt.
Die Hammin-Distanz zweier Vektoren ist die Anzahl der Bits, die beide 
Vektoren unterscheiden.

Am trivialen Beispielen n=1:

(0,0) - Wahrscheinlichkleit 1/4 - Hamming Distanz = 0
(1,0) - Wahrscheinlichkleit 1/4 - Hamming Distanz = 1
(0,1) - Wahrscheinlichkleit 1/4 - Hamming Distanz = 1
(1,1) - Wahrscheinlichkleit 1/4 - Hamming Distanz = 0
Summe der Distanzen * Wahrscheinlichkeit = 0 + 1/4 + 1/4 + 0 = 1/2 = n / 
2

Du weisst die Distanz ist symetrisch d.h. Distanz(a,b) = Distanz(b,a)
Du weisst zudem die Distanz eines Vektors ist die Summe aller Distanzen 
seiner Teilvektoren mit der Dimension = 1.

D.h. du kannst per Vollständiger Induktion aus E(Distanz für Länge 1 
Bitvektoren) die E(Distanz für Länge n>1 Bitvektoren) bilden und stellst 
fest, dass gilt

E(Distanz für Länge m+1 Bitvektoren) = E(Distanz für Länge m 
Bitvektoren) + E(Distanz für Länge 1 Bitvektoren)

Der Schluß zu

E(Distanz für n) = n/2 ist dann trivial

[Manki E. (manki)]

Ja macht sinn Danke!

[Johann L. (gjlayde)]

Manki E. schrieb:
> Mein Buch sagt, dass es n/2 ist.

Für welche Wahrscheinlichkeitsverteilung?