Fixpunkte, Permutationen, Var < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] X(a_1,...,a_n) [/mm] die Anzahl der Fixpunkte einer zufälligen Permutation [mm] a_1,...,a_n [/mm] der Zahlen 1,...,n. Bestimmen Sie Var(X).
Hinweis: Benutzen Sie dazu X = [mm] X_1 [/mm] +···+ [mm] X_n, [/mm] wobei [mm] X_i (a_1,...,a_n)=1 [/mm] genau dann, wenn [mm] a_i [/mm] = i und [mm] X_i (a_1,...,a_n)=0 [/mm] sonst. Berechnen Sie zunächst [mm] E(X_i), 1\le [/mm] i,j [mm] \le [/mm] n, und [mm] E(X_i X_j), [/mm] 1 [mm] \le [/mm] i, j [mm] \le [/mm] n. |
Hi,
kann mir vielleicht jemand bei dieser Aufgabe helfen?? haben zwar hier den Hinweis, aber so richtig, weiß ich trotzdem nicht, wie ich erstmal anfangen soll.
Danke für hilfe.
gruß
|
|
| |
|
Hallo Steve,
> Sei [mm]X(a_1,...,a_n)[/mm] die Anzahl der Fixpunkte einer
> zufälligen Permutation [mm]a_1,...,a_n[/mm] der Zahlen 1,...,n.
> Bestimmen Sie Var(X).
>
> Hinweis: Benutzen Sie dazu X = [mm]X_1[/mm] +···+ [mm]X_n,[/mm] wobei [mm]X_i (a_1,...,a_n)=1[/mm]
> genau dann, wenn [mm]a_i[/mm] = i und [mm]X_i (a_1,...,a_n)=0[/mm] sonst.
> Berechnen Sie zunächst [mm]E(X_i), 1\le[/mm] i,j [mm]\le[/mm] n, und [mm]E(X_i X_j),[/mm]
> 1 [mm]\le[/mm] i, j [mm]\le[/mm] n.
> Hi,
>
> kann mir vielleicht jemand bei dieser Aufgabe helfen??
> haben zwar hier den Hinweis, aber so richtig, weiß ich
> trotzdem nicht, wie ich erstmal anfangen soll.
Die vorgeschlagene Aufspaltung ist dir ja trotzdem klar, denke ich. Wenn X die Anzahl der Fixpunkte einer Permutation [mm] f:\{1,...,n\}\to\{1,...,n\} [/mm] angibt, kann ich X auch schreiben als
X = [mm] X_{1} [/mm] + ... + [mm] X_{n},
[/mm]
wobei [mm] X_{i} [/mm] genau dann 1 ist, wenn f bei i einen Fixpunkt hat. Das ist einfach mathematisch ausgedrückt das "Durchzählen" der Fixpunkte.
Dir sollte klar sein, dass die [mm] X_{i} [/mm] identisch verteilt sind.
Du kannst also E(X) so berechnen:
E(X) = [mm] E(X_{1} [/mm] + ... + [mm] X_{n}) [/mm] = [mm] E(X_{1})+...+E(X_{n}) [/mm] = [mm] n*E(X_{1}),
[/mm]
weil die [mm] X_{i} [/mm] identisch verteilt sind. Nun musst du nur noch überlegen, was [mm] E(X_{1}) [/mm] ist. Da [mm] X_{1} [/mm] nur 1 oder 0 sein kann (Definition oben!!), musst du nur überlegen, mit welcher Wahrscheinlichkeit p der Wert 1 angenommen wird. Dann ist [mm] E(X_{1}) [/mm] = p*1 + (1-p)*0 = p.
Für [mm] E(X^{2}) [/mm] musst du ähnliche Überlegungen machen.
Grüße,
Stefan
|
|
|
| |
|
Hi stefan, also wenn ich deine Rechnung weiterverfolge, dann müsste es eigentlich so weitergehen:
E(X) = [mm] E(X_{1} [/mm] + ... + [mm] X_{n}) [/mm] = [mm] E(X_{1})+...+E(X_{n}) [/mm] = [mm] n\cdot{}E(X_{1})=n*p
[/mm]
und dann analgo für [mm] E(X^2):
[/mm]
[mm] E(X^2)=E(X^2_{1} [/mm] + ... + [mm] X^2_{n}) [/mm] = [mm] E(X^2_{1})+...+E(X^2_{n}) [/mm] = [mm] n\cdot{}E(X^2_{1})
[/mm]
[mm] E(X^2_{1})=E(X_{1}*X_{1})=E(X_{1})E(X_{1})=p^2
[/mm]
d.h. [mm] E(X^2)=n*p^2
[/mm]
Nach [mm] Var(x)=E(X^2)-(E(X))^2 [/mm] folgt dann:
[mm] Var(x)=E(X^2)-(E(X))^2 [/mm] = [mm] n*p^2 [/mm] - [mm] (n^2 p^2) [/mm] = [mm] n*p^2 [/mm] (1-n)
richtig so??
|
|
|
| |
|
Hallo Steve,
> Hi stefan, also wenn ich deine Rechnung weiterverfolge,
> dann müsste es eigentlich so weitergehen:
>
> E(X) = [mm]E(X_{1}[/mm] + ... + [mm]X_{n})[/mm] = [mm]E(X_{1})+...+E(X_{n})[/mm] =
> [mm]n\cdot{}E(X_{1})=n*p[/mm]
Ja, aber was ist das p? Das habe ich nicht als Ausrede für dich hingeschrieben, dass du es nicht ausrechnen musst  p lässt sich in Abhängigkeit von n darstellen.
Dazu folgende Überlegung: Wir suchen die Wahrscheinlichkeit dafür, dass bei der Permutation f von [mm] \{1,...,n\} [/mm] in sich selbst bei 1 ein Fixpunkt vorliegt. Was 1 bei der Permutation zugeordnet wird, ist gleichverteilt, es kann also mit gleichen Wahrscheinlichkeiten 1, ..., n sein. Aber wir wollen 1. Also:
p = [mm] \frac{GuenstigeEreignisse}{MoeglicheEreignisse} [/mm] = [mm] \frac{1}{n}.
[/mm]
Also ergibt sich $E(X) =1$ !
> und dann analgo für [mm]E(X^2):[/mm]
>
> [mm]E(X^2)=E(X^2_{1}[/mm] + ... + [mm]X^2_{n})[/mm]
... (Hier könnte folgende Kritik stehen: "Schonmal was von Ausmultiplizieren gehört?" ).
Guck mal, es ist doch
[mm] $E(X^{2}) [/mm] = [mm] E\left(\left(\sum_{k=1}^{n}X_{k}\right)^{2}\right) [/mm] = [mm] E\left(\sum_{k=1}^{n}\sum_{l=1}^{n}X_{k}*X_{l}\right) [/mm] = [mm] \sum_{k=1}^{n}\sum_{l=1}^{n}E(X_{k}*X_{l})$.
[/mm]
Nun muss dir zweierlei klar sein: Die [mm] X_{i} [/mm] sind nicht stochastisch unabhängig, deswegen gilt NICHT [mm] E(X_{k}*X_{l}) [/mm] = [mm] E(X_{k})*E(X_{l}).
[/mm]
Warum? Einfachstes Beispiel: Wenn man weiß, dass alle [mm] X_{i} [/mm] außer [mm] X_{n} [/mm] den Wert 1 haben, also f bei 1,...,n-1 Fixpunkte vorliegen hat, dann muss f auch bei [mm] X_{n} [/mm] einen Fixpunkt haben (es bleibt ja nichts anderes mehr übrig, wass f(n) sonst sein könnte).
Du musst nun also zweierlei überlegen:
- Welchen Wert hat [mm] E(X_{k}*X_{l}) [/mm] für [mm] k\not= [/mm] l ?
- Welchen Wert hat [mm] E(X_{k}*X_{l}) [/mm] = [mm] E(X_{k}^{2}) [/mm] für k = l?
Grüße,
Stefan
|
|
|
| |
|
Hi nochmal.
> - Welchen Wert hat $ [mm] E(X_{k}\cdot{}X_{l}) [/mm] $ für $ [mm] k\not= [/mm] $ l ?
> - Welchen Wert hat $ [mm] E(X_{k}\cdot{}X_{l}) [/mm] $ = $ [mm] E(X_{k}^{2}) [/mm] $ für k = l?
Die Sache ist, ist k=1, dann haben wir ja den Erwartungswert wie oben, nur ich weiß nicht, wir haben ja hier ein Produkt von EW´ten [mm] E(X_{k}\cdot{}X_{l}) [/mm] , die wir ja leider auch nicht außeinander nehmen können, da sie stochastisch abhängig sind.
Kann ich einfach sagen: [mm] E(X_{k}\cdot{}X_{l}) =E(X_{k}^{2})=2 [/mm] für k=1 und [mm] E(X_{k}\cdot{}X_{l})=0 [/mm] für [mm] k\not=l [/mm] ??
Aber selber begründen kann ich gerade selber nicht ...
|
|
|
| |
|
Hallo Steve,
> Hi nochmal.
>
> > - Welchen Wert hat [mm]E(X_{k}\cdot{}X_{l})[/mm] für [mm]k\not=[/mm] l ?
> > - Welchen Wert hat [mm]E(X_{k}\cdot{}X_{l})[/mm] = [mm]E(X_{k}^{2})[/mm]
> für k = l?
>
> Die Sache ist, ist k=l, dann haben wir ja den
> Erwartungswert wie oben, nur ich weiß nicht, wir haben ja
> hier ein Produkt von EW´ten [mm]E(X_{k}\cdot{}X_{l})[/mm] , die wir
> ja leider auch nicht außeinander nehmen können, da sie
> stochastisch abhängig sind.
>
> Kann ich einfach sagen: [mm]E(X_{k}\cdot{}X_{l}) =E(X_{k}^{2})=2[/mm]
> für k=1 und [mm]E(X_{k}\cdot{}X_{l})=0[/mm] für [mm]k\not=l[/mm] ??
Nein, das ist falsch, und ich weiß auch nicht wie du darauf gekommen bist. Wichtig: Es sieht so aus, als hättest du mein Ell ("l") als Eins ("1") erkannt, das meinte ich nicht, ich meinte ein Ell.
Also. Um die beiden gesuchten Erwartungswerte zu bestimmen,
> > - Welchen Wert hat [mm]E(X_{k}\cdot{}X_{l})[/mm] für [mm]k\not=[/mm] l ?
> > - Welchen Wert hat [mm]E(X_{k}\cdot{}X_{l})[/mm] = [mm]E(X_{k}^{2})[/mm]
musst du wieder ins "Anschauliche" gehen, also überlegen, wie es sich mit den Fixpunkten bei f verhält.
Zum Beispiel [mm] E(X_{k}^{2}). [/mm] Offensichtlich kann [mm] X_{k}^{2} [/mm] nur die Werte 0 und 1 annehmen, da schon [mm] X_{k} [/mm] nur die Werte 0 und 1 annehmen konnte. Es ist wieder die Frage, mit welcher Wahrscheinlichkeit [mm] X_{k}^{2} [/mm] den Wert 1 annimmt. --> Natürlich mit derselben Wahrscheinlichkeit wie [mm] X_{k} [/mm] den Wert 1 annimmt! Denn wenn [mm] X_{k} [/mm] = 1, dann ist auch [mm] X_{k}^{2} [/mm] = 1.
Also gilt [mm] E(X_{k}^{2}) [/mm] = [mm] \frac{1}{n}.
[/mm]
Nun [mm] E(X_{k}*X_{l}) [/mm] für [mm] k\not= [/mm] l. Offensichtlich kann [mm] X_{k}*X_{l} [/mm] wieder nur die beiden Werte 0 und 1 annehmen. Uns interessiert wieder nur die Wahrscheinlichkeit, dass [mm] X_{k}*X_{l} [/mm] den Wert 1 annimmt. Wann ist das der Fall? Was folgt dann für die Wahrscheinlichkeit?
Grüße,
Stefan
|
|
|
| |
|
> Also gilt $ [mm] E(X_{k}^{2}) [/mm] $ = $ [mm] \frac{1}{n}. [/mm] $
> Nun $ [mm] E(X_{k}\cdot{}X_{l}) [/mm] $ für $ [mm] k\not= [/mm] $ l. Offensichtlich kann $ [mm] X_{k}\cdot{}X_{l} [/mm] $ wieder nur die beiden Werte 0 und 1 annehmen. Uns interessiert wieder nur die Wahrscheinlichkeit, dass $ [mm] X_{k}\cdot{}X_{l} [/mm] $ den Wert 1 annimmt. Wann ist das der Fall? Was folgt dann für die Wahrscheinlichkeit?
[mm] X_{k}\cdot{}X_{l} [/mm] nimmt doch nur dann den Wert 1 an, wenn [mm] a_{k*l} [/mm] =k*l gilt, richtig?? Das war ja in der Def. so gegeben: [mm] X_i (a_1,...,a_n)=1, [/mm] genau dann, wenn [mm] a_i [/mm] = i und [mm] X_i (a_1,...,a_n)=0 [/mm] sonst. Und das ist doch nie der Fall, also haben wir hier:
[mm] E(X_{k}\cdot{}X_{l})=0 [/mm] für [mm] k\not= [/mm] l
So dann haben wir haber jetzt zwei Ergebnisse.
[mm] E(X_{k}\cdot{}X_{l})=\begin{cases} \frac{1}{n}, & \mbox{für } k=l \\ 0 & \mbox{für } k\not= l \end{cases}
[/mm]
irgendwie scheint mir das Ergebnis aber sehr sehr komisch.
Denn irgendwo hatte ich mal gelesen, dass da als Endergebnis der Aufgabe 1 rauskommen muss. Das passt ja bei mir hier vorne und hinten nicht :-/
Ich war mir ehrlich gesagt hier auch am überlegen, ob man unsere Wahrscheinlichkeiten nicht auch so aufschreiben kann:
[mm] X_k (a_1,...,a_n)*X_l (a_1,...,a_n)=X_{k}\cdot{}X_{l} (a_1,...,a_n)(a_1,...,a_n)
[/mm]
Weil so würden wir meines Erachtens auf ein anderes Ergebnis kommen, und zwar dass [mm] E(X_{k}^{2}) [/mm] = [mm] \frac{1}{n^2} k\not= [/mm] l , da Wir n Elemente aus [mm] X_k [/mm] mit n Elementen aus [mm] X_l [/mm] multiplizieren müssen, und die Wahrscheinlichkeit [mm] X_{k}\cdot{}X_{l} [/mm] genau ein mal eintritt......
|
|
|
| |
|
Hallo Steve,
> > Also gilt [mm]E(X_{k}^{2})[/mm] = [mm]\frac{1}{n}.[/mm]
>
> > Nun [mm]E(X_{k}\cdot{}X_{l})[/mm] für [mm]k\not=[/mm] l. Offensichtlich kann
> [mm]X_{k}\cdot{}X_{l}[/mm] wieder nur die beiden Werte 0 und 1
> annehmen. Uns interessiert wieder nur die
> Wahrscheinlichkeit, dass [mm]X_{k}\cdot{}X_{l}[/mm] den Wert 1
> annimmt. Wann ist das der Fall? Was folgt dann für die
> Wahrscheinlichkeit?
>
> [mm]X_{k}\cdot{}X_{l}[/mm] nimmt doch nur dann den Wert 1 an, wenn
> [mm]a_{k*l}[/mm] =k*l gilt, richtig?? Das war ja in der Def. so
> gegeben: [mm]X_i (a_1,...,a_n)=1,[/mm] genau dann, wenn [mm]a_i[/mm] = i und
> [mm]X_i (a_1,...,a_n)=0[/mm] sonst. Und das ist doch nie der Fall,
> also haben wir hier:
Das ist zwar richtig, aber wie folgerst du daraus bitte [mm] a_{k*l} [/mm] = k*l ? Das hat doch damit gar nichts zu tun :-(
Du arbeitest immer noch zu wenig mit der Anschauung.
[mm] X_{k}*X_{l} [/mm] für [mm] k\not= [/mm] l wird nur 1, wenn SOWOHL [mm] X_{k} [/mm] = 1 ALS AUCH [mm] X_{l} [/mm] = 1 gilt.
Die Permutation f muss also gleichzeitig an den beiden Stelle k und l einen Fixpunkt haben, und dafür musst du nun die Wahrscheinlichkeit ausrechnen.
Die Wahrscheinlichkeit, dass f an der Stelle k einen Fixpunkt besitzt, beträgt [mm] \frac{1}{n}. [/mm] Jetzt müssen wir das mit der Wahrscheinlichkeit multiplizieren, dass die Funktion f an der Stelle l einen Fixpunkt besitzt, wenn sie an der Stelle k schon einen besitzt.
Du bist dran!
Grüße,
Stefan
|
|
|
| |
|
ohhh s....., ich dachte die Indizes müssen irgendwie mit dem Wert übereinstimmen. wohl schwachsin gewesen.
> Die Wahrscheinlichkeit, dass f an der Stelle k einen Fixpunkt besitzt, beträgt $ [mm] \frac{1}{n}. [/mm] $ Jetzt müssen wir das mit der Wahrscheinlichkeit multiplizieren, dass die Funktion f an der Stelle l einen Fixpunkt besitzt, wenn sie an der Stelle k schon einen besitzt.
ohhhh ich hoffe, dieses mal wirds richtig. Wir haben dann ja eigentlich einen Fixpunkt weniger, also folgt:
[mm] E(X_{k}\cdot{}X_{l})= \bruch{1}{n(n-1)} [/mm] für [mm] k\not= [/mm] l
Jetzt haben wir aber denn zwei Wahrscheinlichkeiten, nicht wahr? und wenn man aufsummiert, dann auch noch
[mm] E(X^2)=n*E(X_{k}\cdot{}X_{l})=\begin{cases} 1 & \mbox{für } k=l \\ \bruch{n}{n(n-1)},# & \mbox{für } k\not= l \end{cases} [/mm]
So, dann habe ich versucht ,wieder mit $ [mm] Var(x)=E(X^2)-(E(X))^2 [/mm] $ zu arbeiten, aber Var(X)=1 kriege ich trotzdem nicht heraus. Schau mal:
[mm] Var(X)=E(X^2)-(E(X))^2 =\bruch{1}{(n-1)} [/mm] - 1 = [mm] \bruch{1-(n-1)}{(n-1)}=\bruch{2-n}{(n-1)}=\bruch{\bruch{2}{n} - 1}{(1 - \bruch{1}{n})}\not=1
[/mm]
|
|
|
| |
|
> ohhh s....., ich dachte die Indizes müssen irgendwie mit
> dem Wert übereinstimmen. wohl schwachsin gewesen.
>
> > Die Wahrscheinlichkeit, dass f an der Stelle k einen
> Fixpunkt besitzt, beträgt [mm]\frac{1}{n}.[/mm] Jetzt müssen wir
> das mit der Wahrscheinlichkeit multiplizieren, dass die
> Funktion f an der Stelle l einen Fixpunkt besitzt, wenn sie
> an der Stelle k schon einen besitzt.
>
> ohhhh ich hoffe, dieses mal wirds richtig. Wir haben dann
> ja eigentlich einen Fixpunkt weniger, also folgt:
>
> [mm]E(X_{k}\cdot{}X_{l})= \bruch{1}{n(n-1)}[/mm] für [mm]k\not=[/mm] l
![[ok]](/images/smileys/ok.gif "[ok]") Ja, dieses Mal stimmt's
Wenn nämlich z.B. bei 1 schon ein Fixpunkt vorliegt, gibt es ja für 2 nur noch (n-1) Möglichkeiten, also beträgt die Wahrscheinlichkeit, dass dann der Fixpunkt "2" getroffen wird, 1/(n-1).
> Jetzt haben wir aber denn zwei Wahrscheinlichkeiten, nicht
> wahr? und wenn man aufsummiert, dann auch noch
>
> [mm][mm] E(X^2)=n*E(X_{k}\cdot{}X_{l})
[/mm]
Diese Umformung stimmt so leider nicht. Ich hatte dir schon hingeschrieben:
[mm] $E(X^{2}) [/mm] = [mm] \sum_{k=1}^{n}\sum_{l=1}^{n}E(X_{k}*X_{l})$.
[/mm]
Nun musst du diese Summe aufteilen in die beiden Erwartungswerte, die du kennst. In der inneren Summe gibt es immer genau einen Summanden, für den k = l gilt. Den ziehen wir aus der Summe raus:
[mm] $=\sum_{k=1}^{n}\left(E(X_{k}^{2}) + \sum_{l=1, l\not= k}^{n}E(X_{k}*X_{l})\right) [/mm] = [mm] \left(\sum_{k=1}^{n}E(X_{k}^{2})\right) [/mm] + [mm] \left(\sum_{k=1}^{n}\sum_{l=1, l\not= k}^{n}E(X_{k}*X_{l})\right) [/mm] $.
So, nun setze deine Erkenntnisse über die Erwartungswerte ein. Und wehe, du kommst nicht auf 2 !
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:32 Mo 04.01.2010 | | Autor: | jaruleking |
Das war ne Geburt,
vielen Dank für deine Geduld 
Grüße
|
|
|
|
