Erwartungswert:Element finden < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:59 So 16.12.2012 | | Autor: | yonika |
| Aufgabe | In einem unsortierten Array befinden sich n Elemente, wir wollen ein bestimmtes Element x finden.
Wir ziehen nacheinander zufällig einzelne Elemente und pruefen, ob wir erfolgreich sind. Das machen wir solange, bis Element x gefunden wurde.
Wenn wir ein Element geprueft haben, wird es nicht zurueckgelegt.
Was ist die erwartete Anzahl an Schritten bis wir x gefunden haben? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Mein Ansatz:
[mm] p_{i} [/mm] Wahrscheinlichkeit, x in Schritt i zu finden
[mm] k_{i} [/mm] Wahrscheinlichkeit, x bis (einschliesslich) Schritt i nicht gefunden zu haben
Notation fuer Ereignisse:
i = 2 <=> x in Schritt 2 finden
i [mm] \not=2 [/mm] <=> x bis einschliesslich Schritt 2 nicht finden
[mm] p_{1} [/mm] = [mm] \bruch{1}{n}
[/mm]
[mm] k_{1} [/mm] = 1 - [mm] p_{1} [/mm] = [mm] \bruch{n-1}{n}
[/mm]
[mm] p_{2} [/mm] = [mm] k_{1} [/mm] * P(i=2|i [mm] \not=1) [/mm] = [mm] k_{1} [/mm] * P(i=2 [mm] \cap [/mm] i [mm] \not=1) [/mm] / [mm] k_{1} [/mm] = [mm] \bruch{1}{n-1} [/mm] * [mm] \bruch{n-1}{n} [/mm] = [mm] \bruch{1}{n}
[/mm]
[mm] k_{2} [/mm] = [mm] k_{1} [/mm] * [mm] P(i\not=2|i \not=1) [/mm] = [mm] k_{1} [/mm] * [mm] P(i\not=2 \cap [/mm] i [mm] \not=1) [/mm] / [mm] k_{1} [/mm] = [mm] \bruch{n-1}{n} [/mm] * [mm] \bruch{n-2}{n-1} [/mm] = [mm] \bruch{n-2}{n}
[/mm]
[mm] p_{3} [/mm] = [mm] k_{2} [/mm] * P(i=3|i [mm] \not=2) [/mm] = [mm] k_{2} [/mm] * P(i=3 [mm] \capi \not=2) [/mm] / [mm] k_{2} [/mm] = [mm] \bruch{1}{n-2} [/mm] * [mm] \bruch{n-2}{n} [/mm] = [mm] \bruch{1}{n}
[/mm]
[mm] k_{3} [/mm] = [mm] k_{2} [/mm] * [mm] P(i\not=3|i \not=2) [/mm] = [mm] k_{2} [/mm] * [mm] P(i\not=3 \cap [/mm] i [mm] \not=2) [/mm] / [mm] k_{2} [/mm] = [mm] \bruch{n-2}{n} [/mm] * [mm] \bruch{n-3}{n-2} [/mm] = [mm] \bruch{n-3}{n}
[/mm]
...
[mm] p_{i} [/mm] = [mm] \bruch{1}{n}
[/mm]
[mm] k_{i} [/mm] = [mm] \bruch{n-i}{n}
[/mm]
Erwartete Anzahl Schritte:
E[x] = [mm] \summe_{i=1}^{n} x_{i} [/mm] * [mm] p_{i} [/mm] = [mm] \summe_{i=1}^{n} [/mm] i * [mm] \bruch{1}{n} [/mm] = [mm] \bruch{1}{n} [/mm] * [mm] \summe_{i=1}^{n} [/mm] i = [mm] \bruch{1}{n} [/mm] * [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{n+1}{2}
[/mm]
Vielen Dank fuer Korrekturvorschläge!
Schönen Gruss
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:13 So 16.12.2012 | | Autor: | luis52 |
Moin
>
> Vielen Dank fuer Korrekturvorschläge!
Es gibt nichts auszusetzen. ![[ok]](/images/smileys/ok.gif "[ok]")
> Schönen Gruss
Ebenfalls,
Luis
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:36 So 16.12.2012 | | Autor: | yonika |
Vielen Dank!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:35 So 16.12.2012 | | Autor: | yonika |
| Aufgabe | | Ist der Erwartungswert geringer als die erwarteten Anzahl an Schritte, wenn man bereits gepruefte Elemente wieder zuruecklegt? |
Ohne Zuruecklegen:
E[x] = [mm] \summe_{i=1}^{n} x_{i} [/mm] * [mm] p_{i} [/mm] = [mm] \summe_{i=1}^{n} [/mm] i * [mm] \bruch{1}{n} [/mm] = [mm] \bruch{1}{n} [/mm] * [mm] \summe_{i=1}^{n} [/mm] i = [mm] \bruch{1}{n} [/mm] * [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{n+1}{2} [/mm]
Mit Zuruecklegen:
E[x] = [mm] \summe_{i=1}^{n} x_{i} [/mm] * [mm] p_{i} [/mm] = [mm] \summe_{i=1}^{n} [/mm] i * [mm] (\bruch{n-1}{n})^{i-1} [/mm] * [mm] \bruch{1}{n} [/mm] = [mm] \bruch{1}{n} [/mm] * [mm] \summe_{i=1}^{n} [/mm] i * ( [mm] \bruch{n-1}{n} )^{i-1}
[/mm]
Wie ich auf [mm] p_{i} [/mm] = [mm] (\bruch{n-1}{n})^{i-1} [/mm] * [mm] \bruch{1}{n} [/mm] kam:
Um genau in Schritt i Erfolg zu haben..
...muessen Schritte k < i fehlgeschlagen haben: [mm] (\bruch{n-1}{n})^{i-1}
[/mm]
...muss Schritt i erfolgreich sein: [mm] \bruch{1}{n}
[/mm]
Ich gehe davon aus, dass die erwartete Anzahl Schritte mit Zuruecklegen geringer sein muesste, jedoch gilt offensichtlich:
[mm] (\bruch{n-1}{n})^{i-1} [/mm] * [mm] \bruch{1}{n} [/mm] < [mm] \bruch{1}{n}
[/mm]
Vielleicht könnt ihr mir ja sagen, wo ich einem Denkfehler unterliege?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:56 So 16.12.2012 | | Autor: | luis52 |
Moin, hier bin ich mit deiner Rechnung nicht einverstanden. Wenn du mit Zuruecklegen ziehst, ist die Anzahl der Zuege unbegrenzt. Es laeuft dann auf eine geometrische Verteiung hinaus.
vg Luis
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:07 So 16.12.2012 | | Autor: | yonika |
Ah, vielen Dank fuer den Hinweis!
Schönen Gruss
|
|
|
|
