Bsp 6.2

[dj_m.o.h.t.]

Angabe: Man betrachte die Zahl X der Inversionen einer zufälligen Permutation von 1, 2, 3, 4. Das Paar (i,j) ist eine Inversion, wenn i<j aber j in der Permutation vor i liegt. Ist die zufällige Permutation bespielsweise: 2 4 1 3, so gibt es drei Inversionen, nämlich (1,2), (1,4) und (3,4).

(a) Was ist die minimale/maximale Anzahl von Inversionen?

(b) Man bestimme den Mittelwert E(X).

(c) Man bestimme die Varianz von X.


Lösung:

(a) min = 0 => 1 2 3 4 ...0 Inversionen
max = 6 => (1,2), (1,3), (1,4), (2,3), (2,4) und (3,4)

(b) 1 2 3 4 ...0 Inversionen
1 2 4 3 ...1 Inversion (4,3)
1 3 2 4 ...1 Inversion (3,2)
1 3 4 2 ...2 Inversion (3,2) (4,2)
1 4 2 3 ...2 Inversionen (4,2) (4,3)
1 4 3 2 ...3 Inversionen (4,3) (4,2) (3,2)
2 1 3 4 ...1 Inversion (2,1)
2 1 4 3 ...2 Inversionen (2,1) (4,3)
2 3 1 4 ...2 Inversionen (2,1) (3,1)
2 3 4 1 ...3 Inversionen (2,1) (3,1) (4,1)
2 4 1 3 ...3 Inversionen (2,1) (4,1) (4,3)
2 4 3 1 ...4 Inversionen (2,1) (4,1) (3,1) (4,3)
3 1 2 4 ...2 Inversionen (3,1) (3,2)
3 1 4 2 ...3 Inversionen (3,1) (3,2) (4,2)
3 2 1 4 ...3 Inversionen (3,2) (3,1) (2,1)
3 2 4 1 ...4 Inversionen (3,2) (3,1) (2,1) (4,1)
3 4 1 2 ...4 Inversionen (3,1) (3,2) (4,1) (4,2)
3 4 2 1 ...5 Inversionen (3,2) (3,1) (4,2) (4,1) (2,1)
4 1 2 3 ...3 Inversionen (4,1) (4,2) (4,3)
4 1 3 2 ...4 Inversionen (4,1) (4,3) (4,2) (3,2)
4 2 1 3 ...4 Inversionen (4,2) (4,1) (4,3) (2,1)
4 2 3 1 ...5 Inversionen (4,2) (4,3) (4,1) (2,1) (3,1)
4 3 1 2 ...5 Inversionen (4,3) (4,1) (4,2) (3,1) (3,2)
4 3 2 1 ...6 Inversionen (4,3) (4,2) (4,1) (3,2) (3,1) (2,1)

=> jetzt ne Tabelle:
0 Inversionen: 1
1 Inversionen: 3
2 Inversionen: 5
3 Inversionen: 6
4 Inversionen: 5
5 Inversionen: 3
6 Inversionen: 1

=> jetzt die Anzahl, was bei den jeweiligen Inversionen herausgekommen ist, zusammen zählen => 1+3+5+6+5+3+1=24

E(X) = ((1/24)*0) + ((3/24)*1) + ((5/24)*2) + ((6/24)*3) + ((5/24)*4) + ((3/24)*5) + ((1/24)*6) = 0 + (1/8) + (5/12) + (3/4) + (5/6) + (5/8) + (1/4) => E(X)=3

(c) Var(X) = (((0-3)^2)*(1/24)) + (((1-3)^2)*(4/24)) + (((2-3)^2)*(5/24)) + (((3-3)^2)*(6/24)) + (((4-3)^2)*(5/24)) + (((5-3)^2)*(3/24)) + (((6-3)^2)*(1/24)) => VAR X = 2.33

[luke]

also

1 3 4 2 ...1 Inversion
sind 2 Inversionen (2, 3) und (2, 4)

3 1 4 2 ...2 Inversionen
sind 3 Inversionen (1, 3) , (2, 3) und (2, 4)

oder?


luke

[miezl]

zu b)
Ich denke, dass man E(x) folgendermaßen berechnet (Bitte um Korrektur, wenn ich falsch liege):

Ni ... Anzahl der verschiedenen Permutationsmöglichkeiten bei i Inversionen

E(x) = summe (i=0..6) (Ni * Ni/24) = 1^2/24 + 3^2/24 + 5^2/24 + 5^2/24 + 5^2/24 + 3^2/24 + 1^2/24 = 3,958


zu c)
Var(x) = summe(n=0..6) (Ni - 3,958)^2 * Ni/24 = 4,809

[lj_scampo]

@miezl:
Laut mir stimmt zwar die Formel, es gibt aber 6 3er-Inversionen (sonst wuerde ja 1+3+5+5+5+3+1=23 und nicht 24 sein...)
-> E(X)=4,416
-> V(X)=4,174

Robbys Inversionsliste stimmt nicht ganz, wie luke schon erkannte

[moose]

E(X) = µ = Sum[xi * p(xi)] = (1*0 + 3*1 + 5*2 + 6*3 + 5*4 + 3*5 + 1*6) /24 =
= 3

Var(X) = E( ( X-E(X) )^2 ) = Sum[ (xi-µ)^2 * p(xi) ] = ( 1*(0-µ)^2 +
3*(1-µ)^2 + 5*(2-µ)^2 + 6*(3-µ)^2 + 5*(4-µ)^2 + 3*(5-µ)^2 + 1*(6-µ)^2 ) / 24 =
= 2,167

[edit] tippfehler, danke Richie

[lj_scampo]

Wenn ich mir das so anseh, hat glaub ich moose glatt recht! Koennte man ja eigentlich mit freiem Auge auch schon erkennen, da das Ganze symmmetrisch um 6 (xi=3) ist und xi geht ja von 0..6 und nicht 1,3,5,6,5,3,1.

[SideshowRichie]

Original geschrieben von moose

Var(X) = E( ( X-E(X) )^2 ) = Sum[ (xi-µ)^2 * p(xi) ] = ( 1*(0-µ)^2 +
3*(1-µ)^2 + 5*(4-µ)^2 + 6*(3-µ)^2 + 5*(4-µ)^2 + 3*(5-µ)^2 + 5*(6-µ)^2 ) / 24 =
= 2,167

[/B]

hast du dich da vielleicht am ende vertippt? da gehört doch 1*(6-µ)^2 und nicht 5*(6-µ)^2, oder irre ich mich da?

und gehört am anfang anstatt 5*(4-µ)^2 nicht 5*(2-µ)^2?

[sCHmIkOla]

hmm...wenn ich mich nicht vertan habe sollte (laut excel) für die varianz 3,85417 rauskommen....kann der wert stimmen!?

grüße

[Nxsis]

Bitte gar nicht mehr lesen, war ein absoluter Blödsinn.

//////
Entschuldigt mal (bin eine absolute Statistik-Niete), aber in der Angabe steht:

"Man betrachte die Zahl X der Inversionen EINER zufälligen Permutation ...";

eure Rechenschritte lassen mich aber irgendwie vermuten, ihr interpretiert das als

"Man betrachte die Zahl X der Inversionen ALLER Permutationen ..."

Wenn das jetzt ein absoluter Blödsinn ist, was ich da sage, dann bitte kräftig schimpfen...
///////