Abwandlung des Rosinenproblems (Kugel-Fächer-Modell)

01.04.2011, 17:17

alle

Abwandlung des Rosinenproblems (Kugel-Fächer-Modell)

Meine Frage:
Moin,
Ihr kennt ja sicher das Rosinenproblem:
Ein Bäcker backt x (z.B. 20) Brötchen, wie viele Rosinen n muss er dem Teig beigeben, damit ein beliebiges Brötchen mit der Wahrscheinlichkeit p (z.B. 0,9) mindestens eine Rosine enthält? Hier geht man ja bekanntermaßen einfach über die Gegenwahrscheinlichkeit
$\begin{eqnarray*} 1- (\frac{x-1}{x}) ^{n} \end{eqnarray*}$

Jetzt bin ich aber auf eine Abwandlung dieses Problems gestoßen:
Ein Bäcker backt x (z.B. 20) Brötchen, wie viele Rosinen n muss er dem Teig beigeben, damit mit einer Wahrscheinlichkeit p (z.B. 0,9) jedes Brötchen mindestens eine Rosine enthält? (es muss auf alle gleichzeitig zutreffen)

Meine Ideen:
Da man aus der alten Aufgabe ja schon die Wahrscheinlichkeit hat, dass eines der Brötchen mindestens eine Rosine enthält würde ich jetzt so vorgehen:
$\begin{eqnarray*} 1-(1-(1- (\frac{x-1}{x}) ^{n}))^{x} \end{eqnarray*}$
oder einfacher
$\begin{eqnarray*} 1-((\frac{x-1}{x}) ^{n})^{x} \end{eqnarray*}$

Allerdings betrachtet man dabei die Fächer/Brötchen ja unabhängig von einander, eigentlich kann das ja nicht zulässig sein, oder?

01.04.2011, 17:50

Dopap

Auf diesen Beitrag antworten »

RE: Abwandlung des Rosinenproblems (Kugel-Fächer-Modell)

Zitat:

Original von alle
$\begin{eqnarray*} 1-(1-(1- (\frac{x-1}{x}) ^{n}))^{x} \end{eqnarray*}$
oder einfacher
$\begin{eqnarray*} 1-((\frac{x-1}{x}) ^{n})^{x} \end{eqnarray*}$

Allerdings betrachtet man dabei die Fächer/Brötchen ja unabhängig von einander, eigentlich kann das ja nicht zulässig sein, oder?

ist meiner Meinung nach falsch.

Ich komme auf $\begin{eqnarray*} \left( 1-(\frac {x-1}{x})^n\right)^x \geq 0.9 \end{eqnarray*}$
was bei 20 Brötchen n=103 Rosinen liefert.

01.04.2011, 18:07

HAL 9000

Auf diesen Beitrag antworten »

Es besteht hier wieder das Problem fehlender Unabhängigkeit:

Für jedes einzelne Brötchen mag die Wahrscheinlichkeit, mindestens eine Rosine abzubekommen, gleich

$\begin{eqnarray*} 1 - \left( \frac{x-1}{x} \right)^n \end{eqnarray*}$

sein, aber dass dies für alle $\begin{eqnarray*} x \end{eqnarray*}$ zugleich gilt, kann man nicht einfach mit dem $\begin{eqnarray*} x \end{eqnarray*}$ -fachen Produkt dieser Wahrscheinlichkeit berechnen. unglücklich

Das sieht man eindrucksvoll am Beispiel $\begin{eqnarray*} n<x \end{eqnarray*}$ , denn dort muss es ja mindestens ein Brötchen ohne Rosinen geben, was Wahrscheinlichkeit 0 bedeutet.

Zugegeben, für $\begin{eqnarray*} n \gg x \end{eqnarray*}$ ist $\begin{eqnarray*} \left( 1 - \left( \frac{x-1}{x} \right)^n \right)^x \end{eqnarray*}$ eine passable Näherung.

Die exakte Berechnung ist mit der Siebformel möglich, und auch nach der kommt n=103 heraus.

01.04.2011, 18:27

Dopap

Auf diesen Beitrag antworten »

@HAL9000
Schon öfters von Siebformel gehört, aber noch nie gesehen.
Könntest du uns Unwissende evtl. aufklären?

01.04.2011, 18:40

HAL 9000

Auf diesen Beitrag antworten »

Bezeichnen wir die Ereignisse

$\begin{eqnarray*} A_k \end{eqnarray*}$ ... Brötchen $\begin{eqnarray*} k \end{eqnarray*}$ enthält keine Rosine

für $\begin{eqnarray*} k=1,\ldots,x \end{eqnarray*}$ . Dann ist die Wahrscheinlichkeit, dass alle Brötchen jeweils mindestens eine Rosine enthalten, gleich

$\begin{eqnarray*} p = P\left( \bigcap\limits_{k=1}^x A_k^c \right) = 1 - P\left( \bigcup\limits_{k=1}^x A_k \right) \end{eqnarray*}$ .

Nach Siebformel folgt dann weiter

$\begin{eqnarray*} p = \sum_{I\subseteq \{1,\ldots,x\}} (-1)^{|I|} \cdot P\left( \bigcap\limits_{k\in I} A_k \right) \end{eqnarray*}$ ,

wobei sich diese Summe über alle $\begin{eqnarray*} 2^x \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} I \end{eqnarray*}$ der Gesamtindexmenge $\begin{eqnarray*} \{1,\ldots,x\} \end{eqnarray*}$ erstreckt.

Warum das was bringt? Die Wahrscheinlichkeit des Durchschnitts einer endlichen Anzahl $\begin{eqnarray*} m \end{eqnarray*}$ (hier $\begin{eqnarray*} m=|I| \end{eqnarray*}$ ) solcher $\begin{eqnarray*} A_k \end{eqnarray*}$ ist leicht zu berechnen: Es bedeutet, dass diese $\begin{eqnarray*} m \end{eqnarray*}$ Brötchen sämtlich keine Rosinen abbekommen, also alle $\begin{eqnarray*} n \end{eqnarray*}$ Rosinen auf die anderen $\begin{eqnarray*} x-m \end{eqnarray*}$ Brötchen verteilt werden - was nicht notwendig heißt, dass jedes dieser $\begin{eqnarray*} x-m \end{eqnarray*}$ Brötchen auch Rosinen abbekommt. Dies geschieht mit Wahrscheinlichkeit $\begin{eqnarray*} \left( \frac{x-m}{x} \right)^n \end{eqnarray*}$ . Da es nun insgesamt $\begin{eqnarray*} \binom{x}{m} \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} I \end{eqnarray*}$ mit $\begin{eqnarray*} |I|=m \end{eqnarray*}$ gibt, folgt

$\begin{eqnarray*} p = \frac{1}{x^n} \cdot \sum_{m=0}^x (-1)^m \binom{x}{m} (x-m)^n \end{eqnarray*}$ .

01.04.2011, 19:09

Dopap

Auf diesen Beitrag antworten »

Vielen Dank HAL9000 Freude

( war das nicht die fiese Computer-Maschine aus Kubricks 2001? )
[hab' schon gehört, HAL wäre IBM eins rückwärts...]

01.04.2011, 19:13

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
war das nicht die fiese Computer-Maschine aus Kubricks 2001?

Ich bin nicht fies - nur kalt und nüchtern logisch: Alles für die Mission! Big Laugh

08.07.2012, 14:07

Fragen über Fragen

Auf diesen Beitrag antworten »

Ich verstehe nicht ganz, warum ihr diese Formel für die Wahrscheinlichkeit, dass von x Brötchen genau m Brötchen keine Rosinen abbekommen, nehmt.
Dafür müsste man sich n unterscheidbare Rosinen in einer Reihe vorstellen, denen jeweils x-m unterscheidbare Brötchen zugeordnet werden können. Das für alle Rosinen, also hoch n nehmen und durch x^n teilen.

Es wäre aber viel einleuchtender, n nicht unterscheidbare Rosinen auf x-m Brötchen zu verteilen. Also
$\begin{eqnarray*} P= \frac{\begin{pmatrix} x-m+n-1 \\ n \end{pmatrix}} {\begin{pmatrix} x+n-1 \\ n \end{pmatrix}} \end{eqnarray*}$

Zitat:

Original von alle

Ein Bäcker backt x (z.B. 20) Brötchen, wie viele Rosinen n muss er dem Teig beigeben, damit ein beliebiges Brötchen mit der Wahrscheinlichkeit p (z.B. 0,9) mindestens eine Rosine enthält? Hier geht man ja bekanntermaßen einfach über die Gegenwahrscheinlichkeit
$\begin{eqnarray*} 1- (\frac{x-1}{x}) ^{n} \end{eqnarray*}$

Zitat:

Original von HAL 9000
Es bedeutet, dass diese $\begin{eqnarray*} m \end{eqnarray*}$ Brötchen sämtlich keine Rosinen abbekommen, also alle $\begin{eqnarray*} n \end{eqnarray*}$ Rosinen auf die anderen $\begin{eqnarray*} x-m \end{eqnarray*}$ Brötchen verteilt werden - was nicht notwendig heißt, dass jedes dieser $\begin{eqnarray*} x-m \end{eqnarray*}$ Brötchen auch Rosinen abbekommt. Dies geschieht mit Wahrscheinlichkeit $\begin{eqnarray*} \left( \frac{x-m}{x} \right)^n \end{eqnarray*}$ .

11.07.2012, 13:29

Fragen über Fragen

Auf diesen Beitrag antworten »

Person A geht zu 10 Leuten. Wie hoch ist die Wahrscheinlichkeit, dass niemand am gleichen Tag wie Person A Geburtstag hat? (Schaltjahre gibt es dabei nicht)

Jeder sagt sofort: P= 1- (364/365)^10
Aber warum nicht
(364 über 10) durch (365+10-1 über 10) ?

Mir ist klar, dass beide zu einem anderen Zufallsexperiment gehören (zweiter Fall ist, wenn die 10 Leute ihren Geburtstag in eine Strichliste mit 365 Zeilen eintragen).
Wie kann man aus der Aufgabenstellung rauslesen, dass die Reihenfolge berücksichtigt werden soll? Das gleich verstehe ich an eurer Rosinenüberlegung nicht, und Rosinen kann man ja im Gegensatz zu Menschen wirklich nicht unterscheiden!

PS: Ich habe eine halbe Stunde probiert, in Latex Zahlen in Matrizen (als Binomialkoeffizient missbraucht) zu schreiben- x-m+n-1 geht, aber x+n-1 geht nicht mehr? Wieso kann man in eine Matrix keine reinen Zahlen schreiben?
Ich habe mir aus anderen Threads und diesem hier auch ein paar Binomialkoeffizientbefehle (z.B. \frac{\binom{2}{1} \cdot \binom{6}{3}}{\binom{8}{4}}) kopiert, sobald man aber andere Zahlen einsetzt, wird in der Vorschau alles völlig falsch oder nicht angezeigt?
Schade, dass sich das hier niemand durchliest, ich könnte hier wirklich Hilfe gebrauchen.

12.07.2012, 20:44

Fragen über Fragen

Auf diesen Beitrag antworten »

Der Richtigkeit wegen muss ich doch noch mal nerven: Weil Latex mich so geärgert hat, habe ich mich bei der Wahrscheinlichkeit verschrieben; richtig wäre

P=(364+10-1 über 10) durch (365+10-1 über 10)

16.07.2012, 14:46

Fragen über Fragen

Auf diesen Beitrag antworten »

Ok im Stress habe ich hier einen unnötig bescheuerten Fehler gemacht: Nicht jede Strichliste ist gleichwahrscheinlich. Entsprechend ist nicht jede Rosinenanordnung gleichwahrscheinlich; man muss also erstmal so tun, als wären sie unterscheidbar.
Sowas ist mir noch nie passiert- ich bitte deswegen um Löschung meiner vier Beiträge hier (schade, dass man unbeantwortete Beiträge nicht selber editieren/löschen kann)

Neue Frage »

Antworten »

Abwandlung des Rosinenproblems (Kugel-Fächer-Modell)

Verwandte Themen