bins and balls problem

Neue Frage »

Godric Auf diesen Beitrag antworten »
bins and balls problem
Hallo,
ich höre eine Vorlesung bei der ich Beweise über randomizierte Algorithmen führe, ohne jemals eine Stochhastikvorlesung zu hören, deshalb wundert euch bitte nicht über vielleicht besonders dumme Fehler :P .

Aufgabe:
Gegeben seien n Bälle die unabhängig voneinander und zufällig in n Eimer geworfen werden.
Sei die Anzahl der Bälle in i.

Beweise: 1.
2. Was bedeutet 1. für?

Erstens habe ich versucht zu beweisen. Ich habe erst die Summe aus der Gleichung gezogen. Was ich aufgrund der Linearität des Erfahrungswertes darf. Folgend ziehe ich das c_i aus dem Erwartungswert heraus, sodass folgt was ich aufgrund der unabhängigkeit machen kann. Nach weiteren Umformungen, bei denen ich mich sicher bin da ich sie aus der Analysis kenne komme ich dann auf O(n). E(2) ist dabei 1/n^2 * (1-1/n)^n-2 oder?

In Bezug auf 2. würde ich tippen, dass logarithmisch sein muss. Aber warum zeige ich bei 1. überhaupt 2^c_i was für eine Bedeutung hat das?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Godric
Ich habe erst die Summe aus der Gleichung gezogen. Was ich aufgrund der Linearität des Erfahrungswertes darf.

Das stimmt (noch). Also

.

Zitat:
Original von Godric
Folgend ziehe ich das c_i aus dem Erwartungswert heraus, sodass folgt

Nein, das ist falsch. Und mit Unabhängigkeit hat das gar nichts zu tun. Vielleicht solltest du eben doch eine Stochastikvorlesung besuchen, oder dich an (evtl vorhandene) Schulstochastikkenntnisse erinnern.



Zwei Hinweise:

(1) Als Erwartungswert einer diskreten Zufallsgröße ist wegen der möglichen Werte

.

(2) Aus deiner Problembeschreibung heraus ergibt sich die Verteilung .


(2) in (1) eingesetzt kann man berechnen.
Godric Auf diesen Beitrag antworten »

Leider muss ich dir recht geben unglücklich die Regel gilt nur für unabhängige Zufallsvariablen unglücklich

wie könnte ich un weiter argumentieren?

herzlichen dank an den Vorposter :-)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Godric
Leider muss ich dir recht geben unglücklich die Regel gilt nur für unabhängige Zufallsvariablen unglücklich

Nein: Was du dort gemacht hast, geht gar nicht - es sei denn, ist gar keine echte Zufallsgröße, sondern eine feste reelle Zahl.
Godric Auf diesen Beitrag antworten »

Nocheinmal danke für deine schnelle und vor allem kompetente Hilfe... Ich habe mich aber auch etwas dumm angestellt, ich hätte nur die Definition des Erwartungswertes vernünftig anwenden müssen. Gut die Abschätzung war nicht ganz einfach, aber die kannte ich aus der Analysis. Danke nun bin ich schlauer.
HAL 9000 Auf diesen Beitrag antworten »

Von welcher Abschätzung sprichst du? verwirrt
 
 
Godric Auf diesen Beitrag antworten »

ich habe es folgendermaßen gezeigt..
(Fortsetzung von deinem mir freundlicherweise genannten Hinweis):

dann habe ich eine abschätzung nach oben gemacht und habe (1-1/n)^(n-k) wegfallen lassen, da es immer kleiner 1 ist. Dann habe ich nocheinmal eine Abschätzung nach oben gemacht und die unendliche geometrische Reihe gebildet für alle n>=3 und bin so auf n*n/(n-2) gekommen. n/(n-2) ist streng monoton fallend (1.abl.) und konvergiert gegen 1. Und der rest sollte dann passen...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Godric

Leider ist dir da ein großer Fehler unterlaufen: Du hast den Binomialkoeffizienten vergessen! Tatsächlich lautet die fragliche Summe (die über können wir durch Faktor ersetzen):

.

Das lässt sich leicht über den Binomischen Satz berechnen (und damit deinen Fehler korrigieren).
Godric Auf diesen Beitrag antworten »

warum verwendet man den Binominalkoeffizienten?

Die Wkt., dass der Korb 0 mal getroffen wird ist doch (1/n)^0 *(1-1/n)^n, denn n mal wird ein anderer Korb getroffen, oder nicht? Wo liegt mein Denkfehler?

Viele Grüße
HAL 9000 Auf diesen Beitrag antworten »

(Doppelpost, bitte löschen)
HAL 9000 Auf diesen Beitrag antworten »

Das sind sie wohl wieder, deine abgrundtiefen Stochastiklücken: Ich habe oben schon geschrieben, dass die bei dieser Verteilungsweise der Bälle binomialverteilt sind, Stichwort "Bernoulli-Experiment".
Godric Auf diesen Beitrag antworten »

Du darfst gerne schon weiter oben schreiben was du gerne möchtest. Aber ob ich dir sofort alles glaube ist eine andere Frage :P Aber ja ich gestehe du hast recht :-)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Godric
Aber ob ich dir sofort alles glaube ist eine andere Frage

"Glauben" sollst du hier gar nichts. Du hast es gefälligst als richtig einzusehen! Teufel
Godric Auf diesen Beitrag antworten »

Hallo,

ich habe noch eine nachträgliche Frage:

Es sollte doch gelten (unter den selben Voraussetzungen wie oben)

(verkürzt dargestellt)

oder?
Godric Auf diesen Beitrag antworten »

obiger Beitrag hat sich von alleine geklärt :-)
René Gruber Auf diesen Beitrag antworten »

Dann solltest du ihn auch zurückziehen, denn diese Formelzeile enthält einige haarsträubende Falschheiten, sowohl in Form wie in Inhalt.
HAL 9000 Auf diesen Beitrag antworten »

Da mich Godric per PN kontaktiert hat:

Ja, man kann bei konsequenter Fortführung des begonnenen Weges schließlich beweisen. Das folgt aus dem Ergebnis von a) unter Einbeziehung der Jensenschen Ungleichung für eine geeignet gewählte konvexe Funktion .


EDIT (28.6.11): So stark war das Interesse dann also doch nicht - schade drum. Wenn es so bestellt ist, hättest du auch nicht per PN drängeln müssen. unglücklich
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »