Wahrscheinlichkeitsrechnung

Gruum

Für ein kleines Programm von mir müsste ich berechnen wie viele (m) Lose ich mindestens ziehen muss damit ich mit einer Wahrscheinlichkeit von mindestens p_min mindestens n mal gewinne. Wobei die Wahrscheinlichkeit, dass ein Los gewinnt x beträgt.

Nach ein bisschen rum-rechnen habe ich folgende Funktion geschrieben:

static long M(double x, double p_min, long n)
{
    n--;
    double p = 1;
    double b = Math.Pow(x, n + 1);
    long m = n;

    while (p > 1 - p_min)
    {
        p = p - b;
        m++;
        b = b * (1 - x) * ((double)m / (m - n));
    }

    return m;
}

Das scheint die Aufgabe zwar zufriedenstellend zu lösen aber irgendwie habe ich das Gefühl, dass das auch einfacher zu berechnen sein müsste.
Weiß jemand zufällig ob es einfacher geht?

Schau dir mal die geometrische Verteilungsfunktion an!!!

Gruum

Ich sehe nicht inwiefern mir hier die geometrische Verteilungsfunktion weiterhelfen könnte.

Meine Funktion funktioniert leider doch nicht so ganz zufriedenstellend. Bei zu großen n wird b zu klein für double.

Columbo

irgendwie habe ich das Gefühl, dass das auch einfacher zu berechnen sein müsste.

~~Das geht sicherlich mit einer trivialen Formel in [latex]O(n)[/latex].~~
Edit: Hmm.

Fytch

Ich komme auf das hier:
$P_{min} \leq \sum_{i=0}^{m - n} x^{n+i} \cdot (1-x)^{m-n-i} \cdot \binom{m}{n + i}$
Ich glaube, du hast in deinem Code den faktoriellen Anteil vergessen. Z.B. gibt dein Code für $x=0.25, P_{min} = 0.3, n = 2$ 5 aus: http://ideone.com/2XWFpU
Von Hand + Taschenrechner habe ich 4 erhalten:
$P_{m=2} = x^2 = 0.0625$
$P_{m=3} = x^3 + x^2\cdot(1-x)^1\cdot \binom{3}{2} = 0.15625$
$P_{m=4} = x^4 + x^3\cdot(1-x)^1\cdot \binom{4}{3} + x^2\cdot(1-x)^2\cdot \binom{4}{2} = 0.26171875$
Eine explizite Form für $m$ fällt mir leider nicht ein.

Edit:
Zur Erklärung:
Dein Code erkennt 1-1-0 für n=2 als gewonnen, 1-0-1 z.B. aber nicht. Genau dafür steht der Binomialkoeffizient; die Anzahl der Möglichkeiten, zwei unterschiedliche Dinge anzuordnen. Genauer gesagt, [latex]n[/latex] Elemente (von denen [latex]k[/latex] von der einen Gruppe und [latex]n-k[/latex] von der anderen sind) anzuordnen.

Edit 2:
Fehler korrigiert, siehe unten.

Gruum

Ich glaub du hast dich verrechnet. Jedenfalls habe ich experimentell überprüft ob die Ergebnisse die mein Programm liefert stimmen.
In deiner Summenformel müsste glaube ich die obere Grenze der Summe m-n sein und nicht m-n+1. Im unteren Teil des Binomialkoeffizienten müsste n+i stehen.

Ich hatte allerdings folgendes berechnet:

$f(m) = 1 - P\_m = \sum\_{k=0}^{n-1} \binom{m}{k} x^k (1-x)^{m-k}$

nach ein bisschen umformen bin ich dann darauf gekommen:

$f(n-1) = 1$
$f(m+1) = f(m) - \binom{m}{n-1} x^n (1-x)^{m-n+1}$
$f(m+1) = f(m) - b(m)$
mit
$b(n-1) = x^n$
$b(m+1) = b(m) (m+1)/(m-n) (1-x)$

Das ist etwa das was mein Programm berechnet. Dummerweise kann x^n und damit b kleiner sein, als es ein double noch darstellen kann.

Fytch

Gruum schrieb:

In deiner Summenformel müsste glaube ich die obere Grenze der Summe m-n sein und nicht m-n+1.

Ups, hatte die Syntax vom Summenzeichen falsch im Kopf (OBOE).

Gruum schrieb:

Im unteren Teil des Binomialkoeffizienten müsste n+i stehen.

Auch hier hast du recht. Hab's bei den tatsächlichen Berechnungen aber zum Glück auch korrekt gemacht. *patsch* Keine Ahnung was da vor sich ging.

Wie du vermutetest habe ich mich bei der Berechnung verrechnet, die letzte Formel ergibt auch nach meiner Methode 0.26..., was noch nicht hinreichend ist. Unsere Formeln sind äquivalent nachdem ich sie korrigiert habe.

Anders betrachtet: Wird hier nach einer geschlossenen Form der Umkehrfunktion der Verteilungsfunktion der Binomialverteilung gesucht? Wie ich darauf komme:
Die einzelnen Möglichkeiten, die wir aufsummiert haben, sind binomialverteilt. Die Verteilungsfunktion steht für die Wahrscheinlichkeit aller Ereignisse ≤ k. Und nun die Umkehrfunktion derer, da wir ja mit gegebener Wahrscheinlichkeit $P_{min}$ an n kommen möchten.