Zufällige Verteilung am runden Tisch - wie viele sitzen dann alleine?

12.06.2016, 18:22

kombinator

Zufällige Verteilung am runden Tisch - wie viele sitzen dann alleine?

Hi zusammen, knobele gerade an folgender Aufgabe:

>>>
Angenommen wir setzen k Personen unabhängig voneinander an einen runden Tisch, an dem
n >= k Stühle stehen. Was ist der Erwartungswert für die Anzahl der Personen, die keinen direk-
ten Tischnachbarn haben?
Hinweis: Aufgrund der Unabhängigkeit kann es passieren, dass mehreren Personen der selbe Stuhl
zugewiesen wird.
<<<

Zusätzlich der Hinweis: Benutzen Sie eine Indikatorvariable und die Linearität des Erwartungswerts.

Aktuell bin ich soweit, dass ich $\begin{eqnarray*} X_{i} \end{eqnarray*}$ für "Person $\begin{eqnarray*} i \end{eqnarray*}$ hat keinen Tischnachbar" definiert habe.

Meinen Überlegungen danach ist dann:
$\begin{eqnarray*} Pr(X_{i}) = Pr(\text{"weder rechts noch links von Person i aus sitzt eine der anderen k-1 Personen"}) \end{eqnarray*}$
$\begin{eqnarray*} Pr(X_{i}) = (1-\frac{2}{n})^{(k-1)} \end{eqnarray*}$

Letztendlich suche ich jetzt einen Erwartungswert für Personen ohne Tischnachbarn. Wenn ich das richtig verstehe, kann ich das als $\begin{eqnarray*} E(Y) \end{eqnarray*}$ definieren.

Dann ist $\begin{eqnarray*} E(Y) = \sum_{i=1}^k i*Pr(X_{i}) \end{eqnarray*}$
bzw.: $\begin{eqnarray*} E(Y) = \sum_{i=1}^k i*(1-\frac{2}{n})^{(k-1)} \end{eqnarray*}$

Was haltet ihr von den bisherigen Überlegungen?
Habt ihr einen Tipp wie ich die Summe am besten auflöse?

Gruß,
Kombinator

12.06.2016, 18:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von kombinator
Habt ihr einen Tipp wie ich die Summe am besten auflöse?

Du weißt schon, dass nur $\begin{align*} i \end{align*}$ die Summationsvariable ist, d.h. alles andere wunderbar ausgeklammert werden kann? Augenzwinkern

EDIT: Das i* ist falsch.

P.S.: Habe ich das richtig verstanden? Wenn z.B. vier Personen auf Platz 2 gesetzt werden, und Platz 1 und 3 frei sind, dann zählen alle diese vier Personen als nachbarfrei? Seltsame Auffassung, wie es überhaupt sehr seltsam an dieser Aufgabe ist, dass überhaupt Plätze mehrfach vergeben werden - wozu braucht man da überhaupt noch Voraussetzung $\begin{align*} n\geq k \end{align*}$ ? Die ist in diesem Fall völlig überflüssig.

12.06.2016, 19:07

kombinator

Auf diesen Beitrag antworten »

Danke dir HAL 9000!

Die Aufgabe ist in der Tat etwas seltsam. Wer sich fragt woher die kommt: die kommt aus dem Informatik-Bereich "Randomisierte Algorithmen".

Danke dir für den Hinweis zum Ausklammern. Augenzwinkern

Wenn ich das richtig verstehe dann gilt folgendes:

$\begin{eqnarray*} E(Y) = \sum_{i=1}^k (1-\frac{2}{n})^{(k-1)} \end{eqnarray*}$
$\begin{eqnarray*} E(Y) = n*(1-\frac{2}{n})^{(k-1)} \end{eqnarray*}$

Würdet ihr das Ergebnis noch umformen? (Aufgrund des Exponenten denke ich, dass die Form so ok ist)

12.06.2016, 19:24

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von kombinator
$\begin{eqnarray*} E(Y) = n*(1-\frac{2}{n})^{(k-1)} \end{eqnarray*}$

Nein, es ist $\begin{eqnarray*} E(Y) = k\cdot \left(1-\frac{2}{n}\right)^{(k-1)} \end{eqnarray*}$ .

12.06.2016, 19:37

kombinator

Auf diesen Beitrag antworten »

Danke

Neue Frage »

Antworten »

Zufällige Verteilung am runden Tisch - wie viele sitzen dann alleine?

Verwandte Themen