Erwartungswert von Zyklenelementen

20.11.2018, 14:03

Studentu

Erwartungswert von Zyklenelementen

Hallo Community,

bei folgender Aufgabe bräuchte ich bitte euren Rat:

Sei $\begin{eqnarray*} \overline{a_n} \end{eqnarray*}$ der Erwartungswert der Größe A, wenn die Permutation q(1), ..., q(n) in kanonischer Zyklendarstellung gegeben ist, wobei $\begin{eqnarray*} A= |\{(i,k): 1\leq i < k \leq n, q(i) < q(i+1), q(i) < q(i+2), ..., q(i) < q(k)\}| \end{eqnarray*}$ .

Alternative Herleitung: Sei $\begin{eqnarray*} y_{i,j}(q) = 1 \end{eqnarray*}$ , falls q(i) < q(k) für k=i+1, ..., j bzw. $\begin{eqnarray*} y_{i,j}(q) = 0 \end{eqnarray*}$ , sonst.

Sei $\begin{eqnarray*} \overline{y_{i,j}} \end{eqnarray*}$ der zugehörige Erwartungswert.
Überprüfe:
1) $\begin{eqnarray*} \overline{a_n} = \sum_{1\leq i < j \leq n} \overline{y_{i,j}} \end{eqnarray*}$
2) $\begin{eqnarray*} \overline{y_{i,j}} = \overline{y_{i+s, j+s}} \end{eqnarray*}$
3) $\begin{eqnarray*} \overline{y_{1,j}} = \frac{1}{j} \end{eqnarray*}$
4) $\begin{eqnarray*} \overline{a_n} = (n+1) H_n - 2n \end{eqnarray*}$

Ich scheitere leider schon allein daran, dass ich mir nicht vorstellen kann, wie die Wahrscheinlichkeit aussieht, dass y = 1 ist. Darum wäre ich sehr dankbar, wenn mir jemand auf die Sprünge helfen könnte! smile

20.11.2018, 14:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
wobei $\begin{eqnarray*} A= |\{(i,j): 1\leq i < k \leq n, q(i) < q(i+1), q(i) < q(i+2), ..., q(i) < q(k)\}| \end{eqnarray*}$ .

Irgendwas ist hier mit den Indizes schiefgegangen hinsichtlich $\begin{eqnarray*} j,k \end{eqnarray*}$ , reparier das mal bitte.

20.11.2018, 14:22

Studentu

Auf diesen Beitrag antworten »

Danke für den Hinweis, ist ausgebessert!

Zudem habe ich eine generelle Frage:
Wenn wir zum Beispiel die kanonische Zyklendarstellung (789)(6)(25)(134) haben, ist dann
q(1) = 3 oder q(1) = 7 bzw. q(2) = 5 oder q(2) = 8 usw.?

20.11.2018, 14:31

HAL 9000

Auf diesen Beitrag antworten »

(789)(6)(25)(134) heißt q(1)=3,q(2)=5,q(3)=4,q(4)=1,q(5)=2,q(6)=6,q(7)=8,q(8)=9,q(9)=7.

Zu 1) Ob man nun zu festem $\begin{eqnarray*} (i,j) \end{eqnarray*}$ zählt, wieviele Permutationen die genannte Eigenschaft aufweisen und dann über alle $\begin{eqnarray*} (i,j) \end{eqnarray*}$ summiert - oder aber für feste Permutation die $\begin{eqnarray*} (i,j) \end{eqnarray*}$ zählt und dann über alle Permutationen summiert, ist rum wie num (Prinzip des doppelten Abzählens).

Die Translationsinvarianz 2) ist ebenfalls einfach begründbar: Man kann in einfacher Weise eine Bijektion der zugehörigen Permutationen angeben (Block $\begin{eqnarray*} (i,j) \end{eqnarray*}$ wird nach $\begin{eqnarray*} (i+s,j+s) \end{eqnarray*}$ verschoben, der Rest bleibt in der Reihenfolge erhalten).

Zu 3) Die Wahrscheinlichkeit, dass bei einer (im Sinne der diskreten Gleichverteilung) zufälligen Permutation das kleinste der ersten $\begin{eqnarray*} j \end{eqnarray*}$ Elemente gleich am Anfang sitzt, ist genau $\begin{eqnarray*} \frac{1}{j} \end{eqnarray*}$ .

Bei 4) fließen die bisherigen Erkenntnisse 1)-3) schön ein...

20.11.2018, 15:06

Studentu

Auf diesen Beitrag antworten »

Danke für deine Antwort!

1) Was du geschrieben hast, kann ich nachvollziehen. Allerdings müssen wir doch noch irgendwie begründen, dass es auch keinen Unterschied macht, obwohl wir die Erwartungswerte betrachten. Oder reicht es dafür, deine Begründung herzunehmen und einfach zu sagen, dass man für den Erwartungswert diese günstigen Fälle einfach jeweilsdurch alle möglichen Fälle dividiert und wegen der Linearität des Erwartungswertes?

2) Kannst du das bitte näher ausführen? Mir ist nicht ganz klar, was du mit der Bijektion und Blockverschiebung genau meinst, denn die kanonische Zyklendarstellung ist ja eindeutig bestimmt und muss absteigend (bzw. innerhalb der Zyklen aufsteigend) geordnet sein?

3) Klar, danke!

4) Unter Verwendung von 1,2,3 habe ich nun Folgendes: $\begin{eqnarray*} \overline{a_n} = \sum_{1 \leq i < j \leq n \overline{y_{i,j}}} = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \overline{y_{i,j}} = \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\overline{y_{i,i+k}} = \sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \overline{y_{1,1+k}} = \sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \frac{1}{k+1} = \sum_{i=1}^{n-1}(H_{n-i}-1) = \sum_{k=1}^{n-1}(H_k-1) \end{eqnarray*}$
Ist da wo ein Fehler drin, denn ich sehe nicht, wie sich das auf das Gewünschte umformen ließe?

20.11.2018, 15:43

HAL 9000

Auf diesen Beitrag antworten »

Ok, das war nicht ganz durchdacht, was ich zu 1) geschrieben hatte, nochmal von vorn. Gleichung 1) kann man bereits auf Zufallsebene begründen: Es gilt $\begin{eqnarray*} a_n(q) = \sum_{1\leq i < j\leq n} y_{i,j}(q) \end{eqnarray*}$ für jedes einzelne $\begin{eqnarray*} q \end{eqnarray*}$ , und damit natürlich auch im Erwartungswert. Dabei bezeichne ich mit $\begin{eqnarray*} a_n(q)=\left| B_n(q)\right| \end{eqnarray*}$ für die Menge $\begin{eqnarray*} B_n(q) = \left\{(i,j): 1\leq i < j \leq n, q(i) < q(i+1), q(i) < q(i+2), \ldots , q(i) < q(j)\right\} \end{eqnarray*}$ .

Denn dann ist $\begin{eqnarray*} (i,j)\in B_n(q) \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} y_{i,j}(q)=1 \end{eqnarray*}$ ist.

2) Sei $\begin{eqnarray*} q \end{eqnarray*}$ eine Permutation mit $\begin{eqnarray*} y_{i,j}(q)=1 \end{eqnarray*}$ . Der ordnen wir jetzt eine Permutation $\begin{eqnarray*} q' \end{eqnarray*}$ mit $\begin{eqnarray*} y_{i+s,j+s}(q')=1 \end{eqnarray*}$ zu, zunächst mal für $\begin{eqnarray*} 0\leq s\leq n-j \end{eqnarray*}$ :

$\begin{eqnarray*} q'(k) = \begin{cases} q(k) &\;\mbox{für}\; 1\leq k<i\\ q(k-i+j+1) &\;\mbox{für}\; i\leq k<i+s\\ q(k-s) &\;\mbox{für}\; i+s\leq k\leq j+s\\ q(k) &\;\mbox{für}\; j+s< k\leq n\end{cases} \end{eqnarray*}$ .

Bildlich gesprochen nimmt man den $\begin{eqnarray*} (j-i+1) \end{eqnarray*}$ Werte umfassenden Block $\begin{eqnarray*} q(i),q(i+1),\ldots,q(j) \end{eqnarray*}$ und schiebt ihn im ganzen (und unter Erhaltung der Elementreihenfolge) um $\begin{eqnarray*} s \end{eqnarray*}$ Plätze nach hinten. Die dabei passierten und dabei verdrängten Permutationselemente reihen sich direkt vor dem Block wieder ein.

Das ganze geht auch für negative $\begin{eqnarray*} s \end{eqnarray*}$ , zumindest im Bereich $\begin{eqnarray*} 1-i\leq s\leq 0 \end{eqnarray*}$ , dort schiebt man den Block aber um $\begin{eqnarray*} |s| \end{eqnarray*}$ Plätze nach vorn, die verdrängten Elemene wandern direkt hinter den Block.

Meine Rechnung zu 4) geht eher so

$\begin{eqnarray*} \overline{a_n} = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \overline{y_{i,j}} \stackrel{2)}{=} \sum_{i=1}^{n-1} \sum_{j=i+1}^n \overline{y_{1,j-i+1}} = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} \overline{y_{1,k}} \stackrel{3)}{=} \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} \frac{1}{k} \stackrel{!}{=} \sum_{k=2}^{n} \sum_{i=1}^{n-k+1} \frac{1}{k} = \sum_{k=2}^{n} \frac{n-k+1}{k} = (n+1)(H_n-1) - (n-1) = (n+1)H_n-2n \end{eqnarray*}$ .

21.11.2018, 18:41

Studentu

Auf diesen Beitrag antworten »

Danke, HAL9000,
das Ganze ist ja viel einfacher als es mir zuvor vorgekommen ist! smile

Nur bei der Translationsinvarianz hänge ich noch ein bisschen. Also für mich ist alles nachvollziehbar, was du geschrieben hast, nur fehlt mir noch der formale Zusammenhang zwischen der Existenz der Bijektion bzw. geegineten Permutation und der Translationsinvarianz des Erwartungswertes.
Kann man einfach sagen, weil man zu jeder Permutation mit $\begin{eqnarray*} y_{i,j}=1 \end{eqnarray*}$ auch eine findet mit $\begin{eqnarray*} y_{i+s,j+s}=1 \end{eqnarray*}$ und ebenso umgekehrt, muss es jeweils gleich viele Permutationen geben, für die $\begin{eqnarray*} y_{i,j}=1 \end{eqnarray*}$ wie jene, für die $\begin{eqnarray*} y_{i+s,j+s}=1 \end{eqnarray*}$ ist und daher müssen auch die ensprechenden Erwartungswerte für y übereinstimmen?

22.11.2018, 10:31

HAL 9000

Auf diesen Beitrag antworten »

Genau, durch diese bijektive Abbildung der Permutationen (die ich oben beschrieben hatte) ist gewährleistet, dass es genau so viele Permutationen mit $\begin{eqnarray*} y_{i,j}=1 \end{eqnarray*}$ wie mit $\begin{eqnarray*} y_{i+s,j+s}=1 \end{eqnarray*}$ gibt, was im hiesigen Laplaceschen W-Raum (d.h. alle Permutationen sind gleichwahrscheinlich) zu einem gleichen Erwartungswert beider Größen führt.

22.11.2018, 15:44

Studentu

Auf diesen Beitrag antworten »

Alles klar, danke dir! Freude

Neue Frage »

Antworten »

Erwartungswert von Zyklenelementen

Verwandte Themen