Verteilung /bedingte < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (Informatik)
Gegeben sei ein Vektor [mm] (x_{1}, [/mm] . . . , [mm] x_{n}) [/mm] von
paarweise verschiedenen Elementen, der durchsucht werden soll.
Dazu dienen verschiedene Strategien
(I) Der Informatiker wählt zufällig (gleichverteilt) eine Position aus, notiert das Ergebnis [mm] x_{r(1)} [/mm] und eliminiert das Element aus dem Vektor. Im nächsten Schritt wird der um die Länge 1 reduzierte Vektor erneut unabhängig von der Vorgeschichte nach demselben Verfahren behandelt usw.. Dieser Schritt wird solange durchgeführt, bis jedes Element einmal ausgewählt wurde. Daraus ergibt sich eine permutierte Reihung [mm] (x_{r(1)}, [/mm] . . . , [mm] x_{r(n)}) [/mm] des Ausgangvektors.
(II) Der Informatiker wählt eine gleichverteilte Zufallsvariable [mm] \pi [/mm] = [mm] (\pi(1), [/mm] . . . , [mm] \pi(n)) [/mm] (zufällige Permutation) mit Werten in der symmetrischen Gruppe Sn der Permutationen von 1, . . . , n und bestimmt dadurch eine Reihung [mm] (x_{\pi(1)}, [/mm] . . . , [mm] x_{\pi(n)}) [/mm] .
a) Zeigen Sie, dass beide Strategien dieselbe Verteilung des umgeordneten Vektors ergeben. Was ist die bedingte Verteilung von [mm] x_{\pi(k)} [/mm] gegeben [mm] \pi(1) [/mm] = [mm] i_{1}, [/mm] . . . , [mm] \pi(k-1)= i_{k-1} [/mm] für 1 [mm] \le [/mm] k [mm] \le [/mm] n?
Anleitung: Verwenden Sie das Multiplikationsgesetz für bedingte Wahrscheinlichkeiten.
b) Gesucht wird ein Wert y [mm] \in (x_{1}, [/mm] . . . , [mm] x_{n}) [/mm] , der als Realisierung einer gleichverteilten Zufallsvariable
Y angesehen werden kann, die unabhängig vom Suchverfahren ist. Bestimmen Sie die Verteilung der Zufallsvariablen N, die die Anzahl der Iterationsschritte (nach Strategie I) angibt, die benötigt werden,
um y zu finden.
c) Der Informatiker wählt irgend ein anderes Suchverfahren, dessen Reihenfolge (unabhängig von Y ) durch eine Zufallsvariable von Permutationen [mm] \sigma [/mm] = [mm] (\sigma(1),...,\sigma(n)) [/mm] mit beliebiger Verteilung auf [mm] S_{n} [/mm] gegeben ist. Zeigen Sie, dass N stets die gleiche Verteilung besitzt.
Anleitung: Betrachten Sie die bedingten Wahrscheinlichkeiten
[mm] p_{y,i}= P({x_{\sigma(i)=y}}) [/mm] = y | {Y = y})
und verwenden Sie den Satz von der totalen Wahrscheinlichkeit. |
Hallo,
versuche mich an der Aufgabe aber komme auf keinen grünnen Zweig.
Brauche ein Idee bzw. Vorschlag.
Vom Veraständnis ist die Augfgabe ja so schwer nicht aber die Umsetzung ist anscheinend schwer.
|
|
| |
|
| Aufgabe | a) Zeigen Sie, dass beide Strategien dieselbe Verteilung des umgeordneten Vektors ergeben. Was ist die bedingte Verteilung von $ [mm] x_{\pi(k)} [/mm] $ gegeben $ [mm] \pi(1) [/mm] $ = $ [mm] i_{1}, [/mm] $ . . . , $ [mm] \pi(k-1)= i_{k-1} [/mm] $ für 1 $ [mm] \le [/mm] $ k $ [mm] \le [/mm] $ n?
Anleitung: Verwenden Sie das Multiplikationsgesetz für bedingte Wahrscheinlichkeiten.
b) Gesucht wird ein Wert y $ [mm] \in (x_{1}, [/mm] $ . . . , $ [mm] x_{n}) [/mm] $ , der als Realisierung einer gleichverteilten Zufallsvariable
Y angesehen werden kann, die unabhängig vom Suchverfahren ist. Bestimmen Sie die Verteilung der Zufallsvariablen N, die die Anzahl der Iterationsschritte (nach Strategie I) angibt, die benötigt werden,
um y zu finden.
c) Der Informatiker wählt irgend ein anderes Suchverfahren, dessen Reihenfolge (unabhängig von Y ) durch eine Zufallsvariable von Permutationen $ [mm] \sigma [/mm] $ = $ [mm] (\sigma(1),...,\sigma(n)) [/mm] $ mit beliebiger Verteilung auf $ [mm] S_{n} [/mm] $ gegeben ist. Zeigen Sie, dass N stets die gleiche Verteilung besitzt.
Anleitung: Betrachten Sie die bedingten Wahrscheinlichkeiten
$ [mm] p_{y,i}= P({x_{\sigma(i)=y}}) [/mm] $ = y | {Y = y})
und verwenden Sie den Satz von der totalen Wahrscheinlichkeit. |
Zusammenfassung:
[mm] \vec{v}=(x_{1}, [/mm] $ . . . , $ [mm] x_{n}) [/mm] $ wird paarweise durchsucht.
(I)Es wir ene Position $ [mm] x_{r(1)} [/mm] $ zufällig ausgesucht und von [mm] \vec{v} [/mm] entfernt. Dies wird so lange wiederholt bis jedes Element dran war und wir erhalten eine Permutierte Reihung $ [mm] (x_{r(1)}, [/mm] $ . . . , $ [mm] x_{r(n)}) [/mm] $.
(II) Der Informatiker wählt eine gleichverteilte Zufallsvariable $ [mm] \pi [/mm] $ = $ [mm] (\pi(1), [/mm] $ . . . , $ [mm] \pi(n)) [/mm] $ (zufällige Permutation) mit Werten in der symmetrischen Gruppe S_ {n} der Permutationen von 1, . . . , n und bestimmt dadurch eine Reihung $ [mm] (x_{\pi(1)}, [/mm] $ . . . , $ [mm] x_{\pi(n)}) [/mm] $ .
Also die symmetrische Gruppe [mm] S_{n} [/mm] ( ist die Gruppe, die aus allen Permutationen (Vertauschungen) der n-elementigen Menge besteht.
Habe keine Idee :o
|
|
|
| |
|
| Aufgabe | a) Zeigen Sie, dass beide Strategien dieselbe Verteilung des umgeordneten Vektors ergeben. Was ist die bedingte Verteilung von $ [mm] x_{\pi(k)} [/mm] $ gegeben $ [mm] \pi(1) [/mm] $ = $ [mm] i_{1}, [/mm] $ . . . , $ [mm] \pi(k-1)= i_{k-1} [/mm] $ für 1 $ [mm] \le [/mm] $ k $ [mm] \le [/mm] $ n?
Anleitung: Verwenden Sie das Multiplikationsgesetz für bedingte Wahrscheinlichkeiten.
b) Gesucht wird ein Wert y $ [mm] \in (x_{1}, [/mm] $ . . . , $ [mm] x_{n}) [/mm] $ , der als Realisierung einer gleichverteilten Zufallsvariable
Y angesehen werden kann, die unabhängig vom Suchverfahren ist. Bestimmen Sie die Verteilung der Zufallsvariablen N, die die Anzahl der Iterationsschritte (nach Strategie I) angibt, die benötigt werden,
um y zu finden.
c) Der Informatiker wählt irgend ein anderes Suchverfahren, dessen Reihenfolge (unabhängig von Y ) durch eine Zufallsvariable von Permutationen $ [mm] \sigma [/mm] $ = $ [mm] (\sigma(1),...,\sigma(n)) [/mm] $ mit beliebiger Verteilung auf $ [mm] S_{n} [/mm] $ gegeben ist. Zeigen Sie, dass N stets die gleiche Verteilung besitzt.
Anleitung: Betrachten Sie die bedingten Wahrscheinlichkeiten
$ [mm] p_{y,i}= P({x_{\sigma(i)=y}}) [/mm] $ = y | {Y = y})
und verwenden Sie den Satz von der totalen Wahrscheinlichkeit. |
zu a)
Multiplikationsgesetz für bedigte Wahrscheilichkeit:
P(Y=y | [mm] X=x)=\bruch{P(Y=y | X=x)}{P( X=x)}
[/mm]
Die einzelnen W-keiten für
Die 1. Wahl
$ [mm] x_{r(1)} $=\bruch{1}{n}
[/mm]
Die 2. Wahl
$ [mm] x_{r(2)} \bruch$=\bruch{1}{n-1}
[/mm]
...
Die n. Wahl
$ [mm] x_{r(n)} $=\bruch{1}{n-(n-1)}
[/mm]
Die W-keit für
Die 1. Permutation (1.Vertauschung)
$ [mm] x_{\pi(1)} $=\bruch{1}{n}
[/mm]
Die 2. Permutation (2.Vertauschung)
$ [mm] x_{\pi(2)} \bruch$=\bruch{1}{n}
[/mm]
...
Die n. Permutation (n.Vertauschung)
$ [mm] x_{\pi(n)} $=\bruch{1}{n}
[/mm]
Somit die bedigte W-keit für
P($ [mm] x_{\pi(1)} [/mm] $ | $ [mm] x_{r(1)} $)=\bruch{1}{n}
[/mm]
P($ [mm] x_{\pi(2)} [/mm] $ | $ [mm] x_{r(2)} $)=\bruch{1}{n-1}
[/mm]
...
P($ [mm] x_{\pi(n)} [/mm] $ | $ [mm] x_{r(n)} $)=\bruch{1}{n-(n-1)}
[/mm]
Geht das in die Richtige Richtung?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 20.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:25 Mi 19.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mi 19.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
