Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Erwartete Anzahl von Paaren in Permutation...

Erwartete Anzahl von Paaren in Permutation...

Universität / Fachhochschule

Erwartungswert

Tags: Erwartungswert, Paar, permutation

Gammler aktiv_icon

13:44 Uhr, 19.05.2014

Guten Tag,
ich habe eine Aufgabe an der ich mich schon stundenlang abquäle und jetzt muss ich wohl doch mal nachfragen!

Also gegeben ist eine zufällige Permutation

X = (X_{1}, X_{2}, ..., X_{n})

der Menge

{1, ..., n}, n \in ℕ

.

Gesucht ist nach der erwarteten Anzahl von Paaren

(i, i + 1),

sodass

X_{i} \leq X_{i + 1} - 4

.

Mein Ansatz wäre: Sei

Y

die Zufallsvariable die Anzahl dieser Paare. Wenn man nun mit

1_{{X_{i} \leq X_{i + 1} - 4}}

arbeitet,
dann ist ja

Y = \sum_{i = 1}^{n - 1} 1_{{X_{i} \leq X_{i + 1} - 4}}

Wie ich allerdings jetzt die Wahrscheinlichkeiten für den Indikator berechne ist mir rätselhaft. Zumal die Paare ja nicht unabhängig voneinander sind.

Kann mir da jemand weiterhelfen?

Grüße

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

15:08 Uhr, 19.05.2014

Also, die W-keit

P (X_{i} \leq X_{i + 1} - 4)

bei einem fixierten

i

.
Das geht so: wenn an der Stelle

i

eine

1

steht, habe für die Stelle

i + 1

alle Möglichkeiten von

5

bis

n

, also

(n - 4)

Varianten. Wenn an der Stelle

i

eine

2

steht, habe für die Stelle

i + 1

alle Möglichkeiten von

6

bis

n

, also

(n - 5)

Varianten. Usw. Insgesamt gibt's

(n - 4) + (n - 5) + . . . 2 + 1 = \frac{(n - 3) (n - 4)}{2}

Varianten für passende Paare der Werte von

X_{i}, X_{i + 1}

. Wenn diese zwei Stellen schon belegt sind, gibt's

(n - 2)!

Möglichkeiten, andere Stellen zu belegen, also insgesamt

(n - 2)! \frac{(n - 3) (n - 4)}{2}

passende Permutationen von insgesamt

n!

. Damit ist die W-keit

P (X_{i} \leq X_{i + 1} - 4) = \frac{(n - 3) (n - 4)}{2 n (n - 1)}

Gammler aktiv_icon

15:13 Uhr, 19.05.2014

Hey danke schon mal für die Antwort. Kann ich jetzt genau das einfach bei jedem Indikator einfügen als Wahrscheinlichkeit? Weil Wenn man zum Beispiel

(X_{1}, X_{2})

nimmt, und dieses erfüllt die Bedingung, dann kommt es doch auf den konkreten Wert von

X_{2}

an. Ist dieser bspw.

n,

dann ist ja die Wahrscheinlichkeit, dass

(X_{2}, X_{3})

die Bedingung erfüllt 0. Verstehst du was ich meine?

Grüße

DrBoogie aktiv_icon

15:20 Uhr, 19.05.2014

"Ist dieser bspw. n, dann ist ja die Wahrscheinlichkeit, dass (X2,X3) die Bedingung erfüllt 0."

Ja, aber ich zähle nur mögliche Paare, also ein Paar

(n, j)

wird nie mitgezählt.
Wenn Du genau meine Zählmethode betrachtest, wirst Du sehen, dass der Wert

n - 4

für

X_{2}

der letzte ist, welche noch eine Variante dazu gibt. Für

n - 3, n - 2, n - 1

und

n

gibt's keine passende Paare mehr.
Und ja, man kann diese W-keit direkt benutzen.
Für Erwartunswert bekommt man also

\frac{(n - 3) (n - 4)}{2 n}

. Interessant wäre zu prüfen, ob das stimmt. Für

n = 5

stimmt die Formel, aber für andere zu prüfen kann man wohl nur mit einem Programm.

Gammler aktiv_icon

17:39 Uhr, 19.05.2014

Okay, dann wäre das geklärt. Danke dir ;-)

1166885

1166801

	Status: nicht eingeloggt	Noch nicht registriert?