Dichte eines zweistufigen Zufallsexperiments?

Ich weiß, es gibt gerade zwar wirklich Wichtigeres auf der Welt, aber nichtsdestotrotz steht am 20.4. eine wichtige Mathe-Klausur an, bei dessen Vorbereitung ich mir gerad schwer tue. Und damit geht's schon direkt in die Aufgabe hinein.

Wir betrachten ein zweistufuges Zufallsexperiment.In der ersten Stufe wird eine Münze geworfen mit P(M= 0) = 1/4 und P(M= 1) = 3/4

Die zweite Stufe ergibt sich so:

Gegeben {M = 0} ist die Zufallsvariable X normalverteilt mit Mittelwert 3 und Varianz 9.

Gegeben {M = 1} ist die Zufallsvariable X normalverteilt mit Mittelwert -1 und Varianz 4.

a) Berechnen Sie (i) den Erwartungswert und (ii) die Varianz von X

(b) Bestimmen Sie die Dichte von X

Bisheriger Ansatz:

Das Ergebnis der ersten Stufe wäre E [X] = E [X | M = 0] * P (M = 0) + E [X | M = 1] * P (M = 1) , also mit Zahlenwerten 3 * 1/4 + (-1) * 3/4 = 3/4 - 3/4 = 0.

Dann ist das Variänzchen:

Var [X] = E [X²] - E [X]² = E [X²] - 0

= (9 + 3²) * 1/4 + (4 + (-1)²) * 3/4

= 18 * 1/4 + 5 * 3/4 = 33/4

Jetzt komme ich bei der Dichte nicht weiter. In unserem Lehrbuch steht für Bedingte Dichten: "Ist f (a_1, a_2) da_1, da_2 gemeinsame Dichte von X_1 und X_2 und f_1 (a_1) da_1 Dichte von X_1, dann setzen wir

P (X_2 ∈ da_2 | X_1 = a_1 ) := (f (a_1,a2) / f1 (a_1) ) da_2

und sprechen von der bedingten Dichte von X_2, gegeben {X_1 = a_1}"

Hat das überhaupt was mit der Aufgabe zu tun? Ne, oder?!

Bisher hatten wir immer Aufgaben, wo man bei Standard-Expotentialverteilten Zufallsvariablen die Dichte berechnen sollte. Da wurde dann immer die Ableitung der Verteilungsfunktion berechnet. Das greift hier auch nicht. Wie soll man am besten vorgehen?

Danke und (verzeiht den momentan etwas abgenutzten Spruch) bleibt Gesund.

Schule, Mathematik, Dichte, Statistik, Stochastik, Uni, Wahrscheinlichkeitsrechnung, Zufall, Erwartungswert, mittelwert, Normalverteilung, Varianz, Zufallsexperiment
1 Antwort
Beweis ln (Y) expotentialverteilt und Parameter bestimmen?

Guten Abend,

ich weiß es gibt gerade wirklich wichtigere Probleme auf der Welt, aber unmittelbar nach Beginn der XXL-Corona-Ferien steht direkt um 8.00 Uhr eine wichtige Klausur auf dem Stundenplan. Aber ich will eure wertvolle Zeit nicht weiter mit unwichtigen Details verschwenden, sondern direkt in "medias res" gehen, wie der Franzose sagt. Die Aufgabe

"U sei uniform verteilt auf [0,1]. Wir definieren Y:= 1 / U^(1/3)

a) Berechne

i) die Verteilungsfunktion

ii) die Dichte

iii) den Erwartungswert

b) Weise nach dass ln Y expotentialverteilt ist und finde den Parameter.

Für den Lösungsansatz hab ich versucht die Lösung mit dem Formeleditor hier auf Gutefrage.net zu "texen", aber irgendwie hängt sich die Seite nach einiger Zeit auf. Auch nach 2 Stunden konnte das Problem nicht behoben werden, deswegen hier eine meine Lösungsansatz von einer anderen Latex-Distribution als Screenshot:

Meine Frage

zu iii) Der Erwartungswert wäre doch eigentlich a * 3a^-4, also 3a^-3. Wieso wird bei Integrieren das a^-3 als konstanter Faktor behalten und die 3 nicht. Weil Integrieren ist doch eigentlich "Den Exponenten um eins erhöhen und durch den neuen Exponenten teilen". Wieso erhöht man den Exponent von 3a^-3 also um 1, so dass es -2 wird und teilt durch 3, aber behält a^-3 als konstanten Faktor. Ein konstanter Faktor bleibt ja beim Ableiten erhalten. Aber wieso wird dann a^-3 als konstanter Faktor gewählt und nich etwa 3? Welchen Faktor soll man beim Integrieren als Konstante betrachten? Ich weiß, blöde 9.Klässler-Frage, aber es beschäftigt mich gerade

zu b) Hier verstehe ich generell nicht, was gemacht wird. Klar, im ersten Schritt wird mittels der e-Funktion ln (Y) zu Y aufgelöst. Aber was geschieht danach und wieso weißt man danach nach, dass ln(Y) expotentialverteilt ist. Und woher bestimmt die 3 als Paramter?

Danke und liebe Grüße.

Beweis ln (Y) expotentialverteilt und Parameter bestimmen?
Schule, Mathe, rechnen, Dichte, Informatik, Informatiker, Integralrechnung, Statistik, Stochastik, Universität, Verteilung, Wahrscheinlichkeitsrechnung, Beweis, Erwartungswert, ln, Parameter, Analysis 1, Analysis
1 Antwort
Eine extrem schwere Aufgabe über Lokale Suche und Approximation?

Guten Abend Deutschland, Guten Morgen aus Tralien,

im Folgenden eine extremst schwere Aufgabe, bei der ich mir momentan die Köpfe ausbeiße (oder so ähnlich...) räusper

Gegeben sei ein bipartiter Graph G= (V1 ∪V2, E) mit V1 ∩ V2= ∅und E⊆ V1×V2 sowie eine Gewichtsfunktionw:E→R. Gesucht ist ein Matching maximalen Gewichts. Das Gewicht eines MatchingsM ist die Summe der Gewichte der enthaltenen Kanten. Zu einem Matching M definierenwir die k-Flip Umgebung als

N_k (M) :={M′: |(M′ \ M) ∪ (M\M′) ∣ ≤k}.

Die lokale Suche mit der k-Flip Umgebung erlaubt den Übergang von einem Matching M zu einemMatching aus N_k(M). Zeige folgende Aussagen:

a) Strikte lokale Suche mit 2-Flip Umgebung für gewichtetes bipartites Matching hat keinenkonstant beschränkten Approximationsfaktor.

b) Strikte lokale Suche mit 3-Flip Umgebung hat einen Approximationsfaktor von höchstens 2.

c) Strikte lokale Suche mit 3-Flip Umgebung hat einen Approximationsfaktor von mindestens 2.

Soweit, so (un-)gut. Ich stelle mir M und M' als 2 unterschiedliche Mengen vor, wo bei die Elemente nun über Kanten verbunden werden können. Dabei darf es keine Verbindungen zwischen den Elementen von M bzw. zwischen den Elementen von M' untereinander geben.

Als Beispiel habe ich M mit 4 Elementen und M' mit 3 Elementen. Eine lokale Suche würde im 1. Anlauf die Elemente so verbinden, dass alle Elemente auf M mit einem aus M' verknüpft sind, aber nicht jeder Knoten ein bipartites Matching hat.

z.b. M besteht aus {1,2,3,4} und M' aus {a,b,c}. Die Verknüpfungen sind {1,a}, {1,b}, {2,b}, {2,c}, {3,b}, {4c}.

Dann wäre ein bipartites Matching z.b. {1,b}, {2c}. Aber man könnte durch k = 2 Operationen (Kante entfernen, Kante einfügen) erkennen das es noch ein viel besseres bipartites Matching geben kann, nämlich {1,a}, {2,b}, {4,c}. Genau so gut könnte man auch {1,a}, {3,b}, {2,c} nehmen. Ist das ein korrekter Beweis für 2-Flip-Umgebung? Und wie zeig ich damit mathematisch korrekt, dass keinen Approximationsfaktor von 2 gibt?

Schule, Mathematik, Informatik, Theoretische Informatik, Graphentheorie, Algorithmen und Datenstrukturen
1 Antwort
Zuteilungsproblem NP-Vollständig?

Guten Abend,

kann mir jemand bitte kurz bei der Aufgabe helfen:

"Jedes der m Bewohner in Oestrich-Winkel hat seinen Wunschzettel für das Christkind geschrieben und verschiedene Geschenkwünsche aus einem Katalog mit n verschiedenen Geschenken aufgeschrieben. Ein Bewohner wird glücklich an Heiligabend, wenn er mindestens einen seiner Wünsche erfüllt bekommt. Jeder der k Weihnachtsengel kann sich auf genau ein Geschenk aus dem Katalog spezialisieren und eine beliebig große Stückzahl davon herstellen. Allerdings sind die Engel nicht in der Lage, an verschiedenen Geschenken zu arbeiten. Wenn sie sich einmal spezialisiert haben,können sie in dieser Weihnachtssaison nur diesen Geschenktyp herstellen.

Die Problemstellung für das Weihnachtsgeschenkeproduktionsproblem ist also, ob es zu einem gegebenen Katalog mit n Geschenken eine Auswahl von k Geschenken gibt, sodass jeder Bewohner glücklich wird.

a) Gegeben sei der folgende Weihnachtskatalog: {Schlittschuhe, Eisenbahn, Counterstrike, Smartphone, Fußball, Butterfly-Messer, Puppenhaus, Schlagring}.

Angenommen, es gibt 3 Engel, können damit die folgenden Bewohner mit ihren jeweiligen Wunschzetteln glücklich gemacht werden?

Andrea: {Schlittschuhe, Fußball}

Ben: {Eisenbahn, Butterfly-Messer, Puppenhaus}

Chantal: {Smartphone, Counterstrike, Buch}

Diana: {Fußball, Puppenhaus, Smartphone}

Eve: {Counterstrike, Schlagring}

Fabienne: {Eisenbahn, Butterfly-Messer}

Georg: {Schlagring, Counterstrike, Puppenhaus}

Heidi: {Eisenbahn, Fußball, Schlittschuhe}

Wenn ja, geben Sie eine mögliche Zuordnung der Engel zu den Geschenken an, wenn nein,begründen Sie, warum es nicht geht.

b) Zeigen Sie, dass dasWeihnachtsgeschenkeproduktionsproblem NP-vollständig ist"

-----------------------

Ich verstehe nicht ganz, warum die Zuordnung ein Problem darstellt. Wenn Engel A einfach die Schlittschuhe, die Eisenbahn und Counterstrike produziert; und Engel B das Smartphone, den Fußball und das Butterfly-Messer und C die Puppe und den Schlagring, dann kommt sich doch niemand in die Quere? Die Sachen müssen ja nicht zeitgleich produziert werden, oder? Ganz so einfach kann es aber nicht sein. Soll ich hier mit Bipartiness, Färbungsproblem argumentieren? Ich denke, da in b) steht, dass das Problem NP-vollständig ist, dass es deswegen keine Lösung für a) geben wird. Aber ich verstehe nicht ganz, wie man hier vorgehen soll.

Computer, Studium, Mathe, rechnen, Datenstrukturen, Effizienz, Färbung, Informatik, Modellierung, np, Uni, Algorithmus, Komplexität, Algorithmen und Datenstrukturen, P.
1 Antwort
Wichtelgeschenk für 5 - 10 €?

Howdy,

einer der in letzter Zeit häufig gestellsten Fragen hier auf dieser Seite: Was soll ich meinem Wichtelpartner zum Weihnachtswichteln schenken? Ich kenne die Person, die ich gezogen habe leider noch nicht so lange, aber würd' sie gerne näher kennen lernen. Es sollte auf jeden Fall ein schönes Geschenk sein, über dass sie sich freuen würde, also kein Schrott-Wichteln. Der Wert sollte, laut Vorgabe. 5 - 10 € nicht überschreiten. (Meinetwegen wär ich auch bereit 20 € oder mehr zu bezahlen...muss sie ja nicht wissen, dass es so viel kostet^^)

Zur Person: Sie ist sehr introvertiert, aber kommt in manchen Momenten auch richtig aus sich raus. Ihre Hobbys sind Tanzen, Schlittschuhlaufen und Zeichnen. Sie ist ein Fan von Melanie Martinez und hat eine Vorliebe für Düstere-Gruselige Sachen. Sie sammelt Messer. Der größte gemeinsame Nenner zwischen uns ist Mathematik (wegen Studium^^).

Ich bin total ratlos, weil ich keinen richtigen Zusammenhang zwischen all dem finde. Ich könnt ihr dass Melanie-Martinez-Parfüme schenken, aber das kostet weit aus mehr als 10 € und ich will sie nicht mit einem teueren Geschenk beschämen. Eine weitere Alternative wäre Taschenmesser, aber sie hat schon so eine große Kollektion und ich will ja zeigen, dass ich mir beim Schenken etwas mehr Gedanken mache, als einfach nur das nächstliegende zu holen.

Habt ihr vielleicht einen guten Tipp? Es sollte etwas seien, worüber sie sich auch wirklich freuen würde.

Geschenk, wichtelgeschenk, wichteln
2 Antworten
6 Tupel angeben bei Turingmaschine?

Ich hoffe dass diese Frage jetzt nicht den "Shitstorm of Doom" beschwört, da es allein auf dieser Seite gefühlt 713 Fragen zur Turingmaschine gibt, aber ich dromm' grad nicht kauf...äh...komm' grad nicht drauf..

Entwerfe für jeden Aufgabenteil eine Turingmaschine M, welche Folgendes leistet:

a) M akzeptiert die Sprache L={0,1}+. Am Ende der Berechnung steht nur noch das letzte Zeichen der Eingabe auf dem Band.

b)M akzeptiert die Sprache L={w∈{0,1}+ | w ist die Binärdarstellung einer ganzen Zahl n mit 1024 ≤ n <4096}.

c)M akzeptiert die Sprache L={w∈{0,1}+| w ist die Binärdarstellung einer ganzen Zahl n >0} und am Ende einer akzeptierenden Berechnung befindet sich die Zahl 2n−1(in Binärdarstellung) auf dem Band.

Hinweis:Beachten Die Binärdarstellung einer natürlichen Zahl kann beliebig viele führende Nullen enthalten kann.

-----

Ansatz: ich weiß, dass eine Turingmaschine zunächst das erste Zeichen liest und dann weitergeht bis ein neuer Buchstabe kommt Wenn ein neuer Buchstabe kommt geht, man weiter bis zum Blanksymbol. In der Vorlesung wurde das Beispiel gebracht: a^x * b^x = aaaabbbb. Man läuft von a bis zum ersten b. Dann vom b bis zum ersten Blanksymbol. Vom Blanksymbol wird wieder in A zurückgelaufen, u.s.w, so dass sich das von links und rechts aufbaut.

Zur Teilaufgabe a) sind zudem die Lösungen geleakt worden.

L = {0,1}+ = {0,1} \ {ε }

M = {Q, Σ, δ , Γ, q_0, F)

Q = {q_0, q_1, q_2}

Σ = {0,1}

T = Σ ∪ {B}

Startzustand q_0

Übergangsfunktion q_0

δ (q_0, 0) = (q1, 0, rechts)

δ (q_0, 1) = (q1, 1, rechts)

δ (q_1, 0) = (q1, 0, rechts)

δ (q_1, 1) = (q1, 1, rechts)

δ (q_1, B) = (q2, B, rechts)

Was ist damit gemeint? Vom Zustand q_0 kommt man mit dem Zeichen 0 in den Zustand q1 mit Zeichen und verschiebt den Lesekopf nach rechts. Eine Zeile später ist man jedoch wieder in Zustand q_0. Wie kamen die auf die Lösung?

Um Punkte auf die Aufgabe zu bekommen, muss zudem M = {Q, Σ, δ , Γ, q_0, F) für jede Teilaufgabe genau definiert sein.

(und aus irgendwelchen Gründen bekomm' ich die Fettschrift an der Stelle hier nicht weg. Diesen Absatz bitte nicht mit aggressiven Schreien assozieren. Danke und LG

Computer, Schule, Mathematik, Mathe, rechnen, Automat, Informatik, Uni
3 Antworten
Varianz des Stichprobenmittels beim Ziehen ohne Zurücklegen?

Hallo ihr lieben,

ich habe gerad ein bisschen Probleme bei folgender Aufgabe und hoffe ihr könnt mir weiterhelfen. Die Aufgabe im Wortlaut:

Meine bisherigen Ansätze:

a) i) Erwartungswert E (x) = 1/2 * 10 + 1/6 * 5 + 1/3 * 20 = 12,5

ii) Varianz: (10 - 12,5)² 1/2 + (5 - 12,5)² * 1/6 + (20 - 12,5)² * 1/3 = 31,25

iii) Wurzel von 31,26 = 5,5902

b)

α) Es weden alle Individuen gezogen. Der Ausgang ist deterministisch und damit  (richtig oder Quatsch?)

β)Für die Kovarianz habe ich folgende Formel im Internet gefunden



 ist die Varianz, also 31,25. Aber was ist der hintere Term, also 

γ)Hier hätte ich gesagt 1/30 * 31,25 = 1,0412. Hier bin ich mir nicht sicher, ob es nicht doch zu einfach ist.

c) Auch hier wieder eine Formel durch Internetrecherche

 Für n hätt' ich jetzt 30 eingesetzt, da dies die Stichprobengröße ist. Aber was ist p, wenn die Abweichung 2 sein soll? 200 %?

Im Skript ist die Ungleichung von Chebyshev wie folgt definiert:

"Y sei eine reellwertige Zufallsvariable mit endlichem Erwartungswert μ. Dann gilt für alle ε >0: P(|Y−μ|≥ε) ≤ \frac{1}{ε^2}Var[Y] ".

Den Erwartungswert und die Varianz habe ich aus Aufgabenteil a). Aber was wären Mü und Epsilon?

Danke und liebe Grüße

Varianz des Stichprobenmittels beim Ziehen ohne Zurücklegen?
Computer, Schule, Mathematik, Mathe, rechnen, erwartungen, Informatik, Statistik, Stochastik, Wahrscheinlichkeit, stichprobe, Erwartungswert, population, Standardabweichung, Varianz
1 Antwort
Kleine Knobelaufgabe zu Wahrscheinlichkeitsrechnung?

Zu spät schlafender Stunde wurde uns noch ein besonderes Betthupferl errichtet, bei dem ich kurz um etwas Hilfe bitte. Die Aufgabe lautet:

"In der Krossen Krabbe gibt es einen runden Tisch mit 30 Sitzplätzen, nummeriert mit 1,. . . , 30, so dass auch die Plätze 1 und 30 benachbart sind. Unterschiedliche Meeresbewohner aus 3 verschiedenen Gattungen (5 Krabben,10 Hummer, 15 Tintenfische) werden rein zufällig platziert.

(i) Wie wahrscheinlich ist es, dass Platz 6 und 7 mit Meeresbewohner aus derselben Gattung besetzt werden?

(ii) Was ist die erwartete Anzahl von Paaren benachbarter Plätze, auf Meeresbewohner aus derselben Gattung sitzen?

(iii) Was ist die erwartete Anzahl von Paaren benachbarter Plätze, auf denen Meeresbewohner aus verschiedenen Gattungen sitzen?

Ansatz:

Würde jetzt sagen, dass der ganze Spaß dem Modell "Ziehen ohne Zurücklegen" entspricht, da sobald sich ein Meeresbewohner platziert, der Stuhl besetzt ist. Es gibt jetzt 3 Szenarien

i) Hier gäbe es 3 Möglichkeiten: Entweder sitzen auf Platz 6 und 7 zwei Krabben nebeneinander, oder zwei Hummer oder zwei Tintenfische.

Die W'keit, dass eine Krabbe einen Tisch Nr. 6 belegt wäre 5/30. Die Wahrscheinlichkeit, dass sich eine 2. Krabbe direkt daneben platziert wäre dann nur noch 4/29. Die Wahrscheinlichkeiten multipliziert, gäbe 5/30 * 4/29 = 2/87

Analog die Wahrscheinlichkeiten zwei Hummer nebeneinander zu platzieren:

10/30 * 9/29 = 3/29

und zwei Tintenfischer gesellen sich mit Wahrscheinlichkeit:

15/30 * 14/29 = 7/29 zueinander.

Wahrscheinlichkeiten addieren: 2/87 + 3/29 + 7/29 = 948/2581 = 36,73 % ?

ii) Evtl. mit dem Binominalkoeffizienten arbeiten, also n über k. Wobei n = 30 sind und k die jeweilige Anzahl der Viecher, d.h. 30 über 5, 30 über 10, 30 über 15. Die einzelnen Wahrscheinlichkeiten für Nachbarn wären 5 über 2, 10 über 2 und 15 über 2. Und das könnte man durch die Gesamtanzahl teilen. Die Frage ist nur welche.

Die Anzahl für 2 Krabben wäre dann (10 über 2)/(30 über 10) = 1,4910^-6. Und das kann nicht sein. :(

iii) Hier diesselbe Frage. bzw. wäre das nicht einfach die Gegenwahrscheinlichkeit zu ii?

Danke und liebe Grüße,

Jensek81

Computer, Rätsel, Schule, Mathematik, Mathe, rechnen, Knobelei, Ereignisse, Aussage, Hausaufgaben, Informatik, Logik, Modell, Modellierung, Statistik, Stochastik, Theorie, Wahrscheinlichkeit, Wahrscheinlichkeitsrechnung, Sitzplatz, permutation
1 Antwort
QT Konsolenanwendung programmieren?

Aloha ola,

unszwar geht es darum, dass wir momentan in QT eine Konsolenanwendung programmieren, genauergesagt soll Cornwalls berühmt-berüchtigtes "Game of Life" implemtentiert werden. Probleme bereitet die Konsolenanwendung. Es soll eine Konsole programmiert werden, die den benutzer jeden einzelnen Teilschritt per Knopfdruck ausführen lässt, also z.B. "30 x 30 Array erstellen", "Array mit Zahlen füllen", "Zahlen aus Array kopieren". u.s.w. Meine Frage ist, wie ich das entsprechende Codefragment mit der Konsolensteuerung in Verbindung bringen soll.

Auf QT gibt es ja eine Vorauswahl an buttons, die man erstellen kann. Habe ein Layer erstellt und dann für jede Aktion den entsprechenden Button. Dann mit Rechtsklick "Slot anzeigen" und den Code dann in das Programm eingebaut, z.B.

void MainWindow::on_create_static_array_clicked()

{

....[Code]

..

}

Ein Klicker-Button dafür, dass ein statisches Array erstellt wird.

Und dann darunter das Code-Fragment.

Leider ist es nicht lauffähig. woran liegt es? Fehlt ein Befehl. In den Tutorials, die ich gesehen habe, hat es gereicht, wenn man den Button erstellt und in das Codefragment einführt. An dem Quellcode an sich liegt es auch nicht, denn der ist Lauffhähig. Kann jemand kurz weiterhelfen,bitte?

Computer, Technik, Programmieren, Programmierung, Array, Button, Cornwall, Informatik, Interface, Qt, Technologie, Widget, gui, konsolenanwendung, Spiele und Gaming
1 Antwort
Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

LG

Jensek81

Computer, Schule, Mathematik, Mathe, Programmieren, rechnen, Array, Informatik, Algorithmus, stack, binomialverteilung, Algorithmen und Datenstrukturen
1 Antwort
Rein zufällige Wahl bei uniformer Zufallsvariable?

Hallo ihr lieben,

ich bräuchte mal kurz Hilfe bei folgender Aufgabe, bzw. wollte fragen, ob meine Lösungen korrekt sind.

Wir betrachten eine Gesamtfläche S bestehend aus g Pixeln und eine Teilfläche A bestehend aus f: = p·g Pixeln. Dabei sei p eine Zahl im Intervall [0,1], und sowohl g als auch f seien natürliche Zahlen. Die dreimalige rein zufällige Wahl eines Pixels aus S (entsprechend einem “Ziehen mit Zurücklegen”), beschreiben wir durch eine auf dem Wertebereich {1, . . . , g}3 uniform verteilte Zufallsvariable X= (X1, X2, X3).

a) Wieviele Ausgänge von X gibt es?

b) Wieviele Ausgänge von X gibt es, bei denen X1 auf die Menge {1, . . ., f} und X2 sowie X3 auf die Menge {f+ 1, . . . , g} fallen? Drücke das Ergebnis durch g und p aus.

c) Wieviele Ausgänge von X gibt es, bei denen genau eines der drei gewählten Pixel auf die Menge {1, . . . , f} fällt?

d) Wie wahrscheinlich ist es, dass von den drei zufällig aus S gewählten Pixeln genau eines aus A gewählt wird?

e) Bestimme die 4 möglichen Ausgänge der zufälligen Trefferquote M von A, sowie deren Verteilungsgewichte

Ansatz:

a) Es würde 8 verschiedene Ausgänge geben.

1) Kein Pixel liegt in A

2) Pixel 1 liegt in A, dafür Pixel 2 und Pixel 3 nicht.

3) Pixel 2 liegt in A, dafür Pixel 1 und Pixel 3 nicht

4) Pixel 3 liegt in A, dafür Pixel 1 und Pixel 2 nicht

5) Pixel 1 und Pixel 2 liegen in A, dafür Pixel 3 nicht

6) Pixel 1 und Pixel 3 liegen in A, dafür Pixel 2 nicht

7) Pixel 2 und Pixel 3 liegen in A, dafür Pixel1 nicht

8) Alle Pixel liegen in A

=> 8 Ausgänge. (?)

Hier bin ich mir nicht sicher, ob ich's mir nicht zu einfach mache.

b) Hier versteh' ich nicht, was mit X1 auf der Menge {1,...f} und X2 und X3 auf den Mengen {f+1,...g} gemeint sein soll. Meinen die damit, dass X1 auf die Teilmenge A fällt und X2 und X3 nicht? In dem Fall wäre es nur ein Ausgang. Aber ich glaub' , damit ist etwas anderes gemeint.

c) Hier wieder diesselbe Argumentation wie bei a). Es würde 3 Ausgänge geben (Pixel 1, Pixel 2 oder Pixel 3). ?

d) M = z1 + z2 + z3

{M = 1} = ({x1 ∈ F} ∩ {x2 ∉ F} ∩ {x3 ∉ F}) ∪ ({x2 ∈ F} ∩ {x1 ∉ F} ∩ {x3 ∉ F}) ∪ ({x3 ∈ F} ∩ {x1 ∉ F} ∩ {x2 ∉ F})

= 3 * (p * (1-p)² )

Richtig?

e) Und hier versteh ich nicht, was genau mit 4 möglichen Ausgängen der Trefferquote gemeint sein soll. Es gibt doch, vorausgesetzt ich habe Aufgabenteil a) richtig gelöst, 8 Ausgänge, oder?

Ich weiß, dass man die Verteilungsgewichte mittels p (b) = P (M = b), b ∈ S berechnet. Und mann dann die möglichen Wahrscheinlichkeiten (also eine Zahl zwischen 0 und 1) gleich M setzt. Aber mich verwirrt diese "4 mögliche Ausgänge"?. Das würde doch eher bei 2 Zufallsvariablen zutreffen und nicht für drei?

Kann jemand bitte ein bisschen Licht ins Dunkle bringen?

Danke und liebe Grüße,

Mathematik, Mathe, rechnen, Ereignisse, Ausgang, Informatik, menge, Pixel, Statistik, Stochastik, Uniform, Verteilung, Wahrscheinlichkeit, ergebnis
1 Antwort