Erwartungswert für Nachbarn in String

15.04.2018, 19:06	Kruemelix	Auf diesen Beitrag antworten »
Erwartungswert für Nachbarn in String Hallo, Problem ist folgendes: Ich habe einen String bestehend aus n verschiedenen Buchstaben, welche in dem String jeweils genau zweimal an zufälligen Positionen vorkommen. Ein Beispiel für n=4 wäre "ABDCCBAD". Was ist der Erwartungswert für die Anzahl an Nachbarn (in vorigem Beispiel wäre das nur CC) in Abhängigkeit von n? Überabschätzungen sind im begrenzten Maße erlaubt, ich will idealerweise zeigen, dass die Anzahl an Nachbarn geteilt durch n für n gegen unendlich gegen 0 geht. Ich sitze jetzt schon eine ganze Weile dran, komme aber nicht wirklich weiter. Vielleicht hat ja jemand eine intelligente Idee... Viele Grüße
15.04.2018, 19:25	HAL 9000	Auf diesen Beitrag antworten »
Sei $\begin{eqnarray} X \end{eqnarray}$ die zufällige Anzahl solcher Nachbarpaare, dann ist $\begin{eqnarray} X=\sum_{k=1}^n X_k \end{eqnarray}$ mit den Indikatorfunktionen $\begin{eqnarray} X_k=1_{A_k} \end{eqnarray}$ der Ereignisse $\begin{eqnarray} A_k \end{eqnarray}$ ... die beiden $\begin{eqnarray} k \end{eqnarray}$ -Symbole sind Nachbarn. Die genaue Verteilung von $\begin{eqnarray} X \end{eqnarray}$ mag schwierig zu berechnen sein - der bloße Erwartungswert hingegen ist kein Problem: Es ist $\begin{eqnarray} E(X) = \sum_{k=1}^n E(X_k) = nE(X_1) = nP(A_1) \end{eqnarray}$ aus Symmetriegründen, und weiter dann $\begin{eqnarray} P(A_1) = \frac{2(2n-1)!}{(2n)!} = \frac{1}{n} \end{eqnarray}$ , woraus $\begin{eqnarray} E(X)=1 \end{eqnarray}$ folgt, und das für alle $\begin{eqnarray} n \end{eqnarray}$ .
15.04.2018, 19:46	Kruemelix	Auf diesen Beitrag antworten »
ui, danke für die flotte Antwort! Ich Depp hatte die Formel eigentlich schon (zumindest bis 1/n) - dann allerdings vergessen, dass man den Erwartungswert additiv aufspalten kann...
16.04.2018, 09:07	HAL 9000	Auf diesen Beitrag antworten »
Die Indikatorfunktionen sind auch ein geeignetes Mittel, weitere Charakteristika dieser Zufallsgröße $\begin{eqnarray} X \end{eqnarray}$ zu berechnen, z.B. die Varianz: Es ist $\begin{eqnarray} V(X)=E(X^2)-(E(X))^2 = E(X^2)-1 \end{eqnarray}$ , dabei ist das quadratische Moment $\begin{eqnarray} E(X^2) = E\left(\sum_{k=1}^n \sum_{j=1}^n X_k X_j\right) = nE(X_1^2)+n(n-1)E(X_1X_2) = 1+n(n-1)P(A_1\cap A_2) \end{eqnarray}$ mit $\begin{eqnarray} P(A_1\cap A_2) = \frac{2^2(2n-2)!}{(2n)!} = \frac{2}{n(2n-1)} \end{eqnarray}$ und daher $\begin{eqnarray} V(X) = \frac{2(n-1)}{2n-1} = 1-\frac{1}{2n-1} \end{eqnarray}$ .
16.04.2018, 18:00	Kruemelix	Auf diesen Beitrag antworten »
Danke für die Herleitung, aber wie genau bist du auf die Wahrscheinlichkeit für $\begin{eqnarray} P(A_1 \cap A_2) \end{eqnarray}$ gekommen?
16.04.2018, 19:11	HAL 9000	Auf diesen Beitrag antworten »
Wir betrachten als Grundmenge sämtliche $\begin{eqnarray} (2n)! \end{eqnarray}$ Permutationen (dabei betrachten wir alle Buchstaben als unterscheidbar, sozusagen $\begin{eqnarray} a_1a_2b_1b_2\ldots \end{eqnarray}$ ). i) Bei $\begin{eqnarray} A_1\cap A_2 \end{eqnarray}$ betrachten wir zunächst $\begin{eqnarray} (2n-2) \end{eqnarray}$ Objekte, die beliebig permutiert werden dürfen: Ein $\begin{eqnarray} a \end{eqnarray}$ -Block, ein $\begin{eqnarray} b \end{eqnarray}$ -Block, und dann die $\begin{eqnarray} (2n-4) \end{eqnarray}$ Einzelbuchstaben $\begin{eqnarray} c_1,c_2,d_1,d_2,\ldots \end{eqnarray}$ . Davon gibt es insgesamt $\begin{eqnarray} (2n-2)! \end{eqnarray}$ Permutationen. ii) Nun kann der $\begin{eqnarray} a \end{eqnarray}$ -Block aber $\begin{eqnarray} a_1a_2 \end{eqnarray}$ oder $\begin{eqnarray} a_2a_1 \end{eqnarray}$ lauten, das sind 2 Möglichkeiten, analog beim $\begin{eqnarray} b \end{eqnarray}$ -Block. Das ergibt kombiniert $\begin{eqnarray} 2^2\cdot (2n-2)! \end{eqnarray}$ günstige Varianten. Genauso hat man $\begin{eqnarray} 2^3\cdot (2n-3)! \end{eqnarray}$ günstige Varianten für $\begin{eqnarray} P(A_1\cap A_2\cap A_3) \end{eqnarray}$ , usw.
Anzeige

17.04.2018, 22:41	Kruemelix	Auf diesen Beitrag antworten »
vielen vielen Dank - auf die letzte Lösung hätte ich auch selber kommen können, war aber zu dumm dazu...
20.05.2018, 12:29	Kruemelix	Auf diesen Beitrag antworten »
kleines Update: Die Indikatorfunktion hat mir jetzt schon bei etlichen artverwandten Problemen geholfen, bei einem komme ich allerdings partout nicht weiter: Und zwar geht es um den Erwartungswert für doppelten Nachbarn. Diese wären z.B. von der Form "...AB...AB..." "...AB...BA..." "...ABA...B..." wobei der extremste Fall für einen String der Form "ABCDE....ABDCE...." angenommen wird Ich habe schon versucht, eine geeignete indikatorfunktion zu finden, komme allerdings auf keinen grünen Zweig. Meine Überlegungen bisher waren: - Eine Indikatorfunktion welche angibt, ob zwischen der k-ten Position und der k+1-ten Position im String ein doppelter Nachbar ist. Das Problem: Doppelte Nachbarn treten immer nur im "Doppelpack" auf, dies würde bei einer solchen Indikatorfunktion komplett vernachlässigt werden. - Eine Indikatorfunktion welche angibt, ob zwischen dem i-ten und dem k-ten Buchstaben ein doppelter Nachbar existiert. Das Problem: Bei n unterschiedlichen Buchstaben gibt es mit dieser Indikatorfunktion n(n-1) mögliche Kombinationen, allerdings sind tatsächlich nur n-1 möglich. Hat irgendjemand eine Idee oder einen Hinweis? Idealerweise will ich gar nicht den ganzen Lösungweg erfahren, sondern nur einen Stupser in die richtige Richtung bekommen. Vielen Dank schon im Voraus!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »