Zufallspermutationen < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Eine aufsteigende Teilfolge einer Permutation [mm]\omega\in S_n[/mm] ist durch eine Sequenz [mm]\omega(i_1)<\omega(i_2)<\dots <\omega(i_k)[/mm] mit [mm] 1\leqi_1<\dots |
Ich bin leider schon damit überfordert, eine konkrete Frage zu der Aufgabe zu stellen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Gregorowitch, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Du scheinst erst einmal nur die Notation der Aufgabe nicht zu verstehen, oder?
> Eine aufsteigende Teilfolge einer Permutation [mm]\omega\in S_n[/mm]
> ist durch eine Sequenz [mm]\omega(i_1)<\omega(i_2)<\dots <\omega(i_k)[/mm]
> mit [mm]1\leqi_1<\dots
> Anzahl der austeigenden Teilfolgen der Permutation [mm]\omega[/mm].
> Zeigen Sie, dass für eine gleichverteilte
> Zufallspermutation aus [mm]S_n[/mm] gilt: [mm]E[N]=\sum_{k=1}^{n} \frac{1}{k!}{{n}\choose{k}}.[/mm]
>
> Ich bin leider schon damit überfordert, eine konkrete
> Frage zu der Aufgabe zu stellen.
Nehmen wir eine Permutation von [1234], oder wie auch immer Ihr das notiert. Einige Beispiele:
In [1423] sind folgende aufsteigenden Teilfolgen mit Längen von 2 bis 4 enthalten:
[14],[12],[13],[23],[123]
In [1243] gibt es [12],[14],[13],[24],[23],[124],[123].
In [2314] gibt es [23],[24],[34],[14],[234].
Kommst Du damit schon weiter?
Grüße
reverend
|
|
|
| |
|
Zunächst einmal vielen Dank für deine schnelle Antwort.
Wie ich mir die aufsteigenden Teilfolgen vorstellen muss, ist ziemlich deutlich geworden, vielen Dank, leider kann ich den Bezug zu den Summanden nicht herstellen.
Bei n=4 komme ich auf einen Erwartungswert von ungefähr 7,71, allerdings kann ich mir keine Permutation mit vier Elementen vorstellen, welche mehr als 7 aufsteigende Teilfolgen hat!
|
|
|
| |
|
Hallo nochmal,
> Wie ich mir die aufsteigenden Teilfolgen vorstellen muss,
> ist ziemlich deutlich geworden, vielen Dank, leider kann
> ich den Bezug zu den Summanden nicht herstellen.
> Bei n=4 komme ich auf einen Erwartungswert von ungefähr
> 7,71,
Korrekt. Genau sind es nach der angegebenen Formel [mm] \bruch{185}{24}.
[/mm]
> allerdings kann ich mir keine Permutation mit vier
> Elementen vorstellen, welche mehr als 7 aufsteigende
> Teilfolgen hat!
Um diesen Durchschnitt/Erwartungswert zu erreichen, müsste es die aber geben. Und Du hast Recht, die kann ich mir auch nicht vorstellen. Unter anderem, weil es keine gibt.
Also ist entweder die Formel falsch, oder da stimmt etwas nicht mit den Relationszeichen in der Aufgabenstellung. Hier insbesondere: sind auch "aufsteigende Teilfolgen" der Länge 1 mitgezählt?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:59 Fr 03.05.2013 | | Autor: | felixf |
Moin,
> Also ist entweder die Formel falsch, oder da stimmt etwas
> nicht mit den Relationszeichen in der Aufgabenstellung.
> Hier insbesondere: sind auch "aufsteigende Teilfolgen" der
> Länge 1 mitgezählt?
da diese nirgends ausgeschlossen werden, vermute ich mal, sie werden mitgezaehlt (ich tippe darauf, dass sie durch den [mm] $\frac{1}{1!} \binom{n}{1}$-Teil [/mm] der Formel beruecksichtigt werden). Es gibt uebrigens auch noch die eine einzige aufsteigende Teilfolge der Laenge 0, die hier allerdings offenbar ignoriert wird (dazu muss man die Summe in der Formel dann wahrscheinlich bei 0 beginnen).
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:24 Fr 03.05.2013 | | Autor: | felixf |
Moin!
> Eine aufsteigende Teilfolge einer Permutation [mm]\omega\in S_n[/mm]
> ist durch eine Sequenz [mm]\omega(i_1)<\omega(i_2)<\dots <\omega(i_k)[/mm]
> mit [mm]1\leqi_1<\dots
> Anzahl der austeigenden Teilfolgen der Permutation [mm]\omega[/mm].
> Zeigen Sie, dass für eine gleichverteilte
> Zufallspermutation aus [mm]S_n[/mm] gilt: [mm]E[N]=\sum_{k=1}^{n} \frac{1}{k!}{{n}\choose{k}}.[/mm]
Ein Tipp zur Aufgabe:
* [mm] $\binom{n}{k}$ [/mm] sagt, wieviele Moeglichkeiten es gibt, Indices [mm] $i_1 [/mm] < \ dots < [mm] i_k \le [/mm] n$ auszuwaehlen (fuer ein festes $k$ und $n$)
* [mm] $\frac{1}{k}$ [/mm] ist die Wahrscheinlichkeit, dass fuer eine zufaellige Permutation [mm] $\pi \in S_n$ [/mm] gilt [mm] $\pi(i_1) [/mm] < [mm] \dots [/mm] < [mm] \pi(i_k)$ [/mm] (das musst du allerdings noch beweisen!)
Damit solltest du keine grossen Probleme haben, die Aufgabe fertigzustellen.
LG Felix
|
|
|
|
