www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-StochastikVerteilung /bedingte
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Uni-Stochastik" - Verteilung /bedingte
Verteilung /bedingte < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Stochastik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Verteilung /bedingte: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 10:51 Mo 17.11.2008
Autor: Nataliee

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.

        
Bezug
Verteilung /bedingte: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 15:54 Mo 17.11.2008
Autor: Nataliee

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

Bezug
                
Bezug
Verteilung /bedingte: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 11:05 Di 18.11.2008
Autor: Nataliee

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?


Bezug
                        
Bezug
Verteilung /bedingte: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Do 20.11.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                
Bezug
Verteilung /bedingte: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:25 Mi 19.11.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Verteilung /bedingte: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Mi 19.11.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Stochastik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]