Discussion:
Begründung gesucht
(zu alt für eine Antwort)
Alfred Heiligenbrunner
2018-09-23 19:57:29 UTC
Permalink
Hallo,

wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt:


Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
Zufallszahlen" ergibt sich:
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.

Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?

Danke,
Alfred
Martin Vaeth
2018-09-25 06:29:45 UTC
Permalink
Post by Alfred Heiligenbrunner
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.
So ganz überzeugt bin ich noch nicht: Wenn, dann hätte ich eine
monotone Annäherung von E-2s erwartet (s. unten), aber s=10 scheint
dem zu widersprechen. Oder ist s=10 schon eine Simulation oder
möglicherweise rundungsfehlerbehaftet?

Hast Du einen Beweis?
Oder eine geschlossene/rekursive Formel für natürlich s bzw.
einen "expliziten" Zusammenhang mit der Irvin-Hall-Verteilung?
(Mir war ehrlich gesagt schon der Fall s=2 zu rechenaufwändig,
als dass ich das durchziehen wollte... erstaunlich, dass Du
bis s=3 durchgehalten hast.)
E scheint (für natürliches s) ja stets ein rationales Polynom in e zu
sein; im Hinblick auf die Irvin-Hall-Verteilung würde es mich nicht
wundern, wenn in den Koeffizienten oder deren Rekursionsformeln
Bernoulli-Zahlen auftauchen.
Post by Alfred Heiligenbrunner
Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?
Die Asymptotik E ~ 2s für große s ist nicht überraschend, weil n/2
der Erwartungswert für die Summe bei n Würfen ist: Das "mindestens s"
sollte sich doch für große s im Vergleich zum Erwartungswert
amortisieren. Aber dass der "Fehler" gegen eine Konstante konvergieren
und diese auch noch 2/3 sein soll!?
In jedem Fall hätte ich - wie oben erwähnt - zumindest eine Monotonie
für den "Fehler" erwartet. Wenn dem nicht so ist, gibt es
vermutlich genauere asymptotische Entwicklungen, aber höhere Terme
einer Asymptotik entziehen sich meistens der Anschauung
(vgl. Stirling-Formel, wo die einzige mir bekannte "anschauliche"
Herleitung nicht einmal den ersten Summanden "korrekt" abdeckt.)
Alfred Heiligenbrunner
2018-09-27 19:59:53 UTC
Permalink
Post by Martin Vaeth
Post by Alfred Heiligenbrunner
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.
So ganz überzeugt bin ich noch nicht: Wenn, dann hätte ich eine
monotone Annäherung von E-2s erwartet (s. unten), aber s=10 scheint
dem zu widersprechen. Oder ist s=10 schon eine Simulation oder
möglicherweise rundungsfehlerbehaftet?
Mit Hilfe der Irwin-Hall-Verteilung, die im genannten Video bei Minute
18:00 angegeben wird, bin ich auf folgenden Ausdruck für den
Erwartungswert gekommen (Mathematica-Schreibweise):
erwZ[s_]:=Sum[(-1)^k Sum[1/m! (s - k)^m (m + 1 - s) Binomial[m+1, k] ,
{m, s, Infinity}], {k, 0, Floor[s]}]

Mathematica gibt für s=10 diesen Ausdruck zurück:
-(e/362880) + (2 e^2)/315 - (243 e^3)/560 + (256 e^4)/45 - (
625 e^5)/24 + 54 e^6 - (343 e^7)/6 + 32 e^8 - 9 e^9 + e^10,
oder numerisch
20.6666666664763...

Leider dauert die Berechnung für größere Werte von s relativ lange.
Simulation ist dagegen relativ einfach.
Für s=100 erhalte ich bei 100000 Wiederholungen jeweils einen Wert
zwischen 200.6 und 200.7.

LG
Alfred
Martin Vaeth
2018-09-27 22:26:47 UTC
Permalink
Post by Alfred Heiligenbrunner
erwZ[s_]:=Sum[(-1)^k Sum[1/m! (s - k)^m (m + 1 - s) Binomial[m+1, k] ,
{m, s, Infinity}], {k, 0, Floor[s]}]
Die innere Reihe ist eine wilde hypergeometrische Funktion mit
Integer-Koeffizienten.
Post by Alfred Heiligenbrunner
-(e/362880) + (2 e^2)/315 - (243 e^3)/560 + (256 e^4)/45 - (
625 e^5)/24 + 54 e^6 - (343 e^7)/6 + 32 e^8 - 9 e^9 + e^10,
Dahinter scheint irgendeine Rekursionsformel für die
hypergeometrische Funktion mit Integer-Koeffizienten zu stecken.
Zwar könnte man natürlich versuchen, zu verstehen, was diese
Rekursionsformel in obigem Fall macht, aber ich stimme zu,
dass es ziemlich hoffnungslos scheint, daraus ableiten zu
wollen, dass das Ergebnis für große s stets nahe an einem
ganzzahlien Vielfachen von 1/3 liegen soll...
Einen tiefen anderen Zugang sehe ich aber auch nicht.

Vielleicht ist der diskrete Zugang hilfreicher, der auch in
dem Video vorgestellt wird, auf das Du verlinkt hattest?
Immerhin bekommt man damit von vornherein eine rationale Zahl
zur Approximation. Andererseits hat man dabei das Problem,
dass man Terme höherer Ordnung geschickt vernachlässigen muss,
was für große s vielleicht nicht so "einfach" geht wie im Video.
(Wobei hier ja eindeutig ein wesentlicher Beweisschrit
vernachlässigt wurde. Aber vielleicht ist es gut genug,
die Heuristik, die Du suchst, zu finden).
Post by Alfred Heiligenbrunner
Für s=100 erhalte ich bei 100000 Wiederholungen jeweils einen Wert
zwischen 200.6 und 200.7.
Vielleicht geht trotz der frappierenden Numerik die Differenz E-2s
gegen 0. Dass die Konvergenz logarithmisch langsam und damit bei
numerisch handhabbaren Werten von s nicht feststellbar ist
(egal ob per Simulation oder Computer-Algebra mit Numerik),
sollte bei so kombinatorischen Problemen nicht wirklich überraschen.
Stephan Gerlach
2018-09-26 21:45:35 UTC
Permalink
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Genauere Bezeichnungen:

Z_k = [0,1)-gleichverteilte Zufallsvariablen (im Plural), k Element N
S_n = Summe{k=1 bis n} X_k
X_s = Anzahl Versuche, bis man einen Wert größer oder gleich s erreicht.

Gesucht ist E(X_s).

Bemerkenswert(?) an der ganzen Sache ist, daß für alle s Element R
(reelle Zahlen) und alle n Element N (natürliche Zahlen) gilt:

P(X_s <= n) = P(S_n >= c) [1]
Post by Alfred Heiligenbrunner
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
Genauer: E(X_1) = e.

Allgemeiner kann man sogar zeigen (wenn ich mich nicht irre)
E(X_t) = e^t
für t Element [0,1].

Der Beweis dafür ist IMHO bereits nicht ganz trivial; er benutzt obige
Gleichung [1] sowie folgende Formel

P(S_n <= t) = t^n/n!,

welche aber nur für t Element [0,1] gilt. Man muß gewisse Informationen
über die Verteilung von S_n benutzen, um da drauf zu kommen.
Eine einfachere Herleitung ist mir leider nicht eingefallen.
Post by Alfred Heiligenbrunner
s = 2, E = e * (e-1) = 4,67077;
Das ist dann mit meiner Terminologie E(X_2)...
Post by Alfred Heiligenbrunner
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
... und das E(X_3). Offenbar steckt hier eine Systematik dahinter
Es scheint so, als sei E(s) ein Polynom vom Grad s in der "Variablen" e,
zumindest für den Fall s Element N.
Post by Alfred Heiligenbrunner
s = 10, E = 20,66666666647;
Das wäre dann E(X_10).
Post by Alfred Heiligenbrunner
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Du meinst vermutlich "nähert sich mit wachsendem s immer mehr 2*s+2/3
an". Oder in Formelsprache:

lim_{s -> unendlich} E(X_s) = 2*s+2/3.

Das ergibt aber keinen Sinn, weil der Grenzwert noch von s abhängt,
wobei s aber gegen unendlich geht.

Du meinst vermutlich sowas wie

lim_{s -> unendlich} [E(X_s) / (2*s+2/3)] = 1

oder

lim_{s -> unendlich} [E(X_s) - (2*s+2/3)] = 0.

In Worten: "Der Quotient geht gegen 1" bzw. "die Differenz geht gegen 0".
Post by Alfred Heiligenbrunner
Das kann man auch durch Simulation bestätigen.
Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?
Anschaulich wohl eher nicht, da wie gesagt bereits der Fall s=1 nicht
ganz einfach zu sein scheint. Vermutlich kann man das aber irgendwie
beweisen, indem man zunächst eine allgemeine Formel (evtl.
Rekursionsformel?!) für E(X_s) herleitet und dann den Limes des
Quotienten oder der Differenz bildet.
--
Post by Alfred Heiligenbrunner
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Alfred Heiligenbrunner
2018-09-27 19:35:22 UTC
Permalink
Post by Stephan Gerlach
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Z_k = [0,1)-gleichverteilte Zufallsvariablen (im Plural), k Element N
S_n = Summe{k=1 bis n} X_k
X_s = Anzahl Versuche, bis man einen Wert größer oder gleich s erreicht.
Gesucht ist E(X_s).
Bemerkenswert(?) an der ganzen Sache ist, daß für alle s Element R
P(X_s <= n) = P(S_n >= c)   [1]
Interessant! Was genau ist c?

LG
Alfred
Stephan Gerlach
2018-09-27 23:05:30 UTC
Permalink
Post by Alfred Heiligenbrunner
Post by Stephan Gerlach
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine
berühmte Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Z_k = [0,1)-gleichverteilte Zufallsvariablen (im Plural), k Element N
S_n = Summe{k=1 bis n} X_k
X_s = Anzahl Versuche, bis man einen Wert größer oder gleich s erreicht.
Gesucht ist E(X_s).
Bemerkenswert(?) an der ganzen Sache ist, daß für alle s Element R
P(X_s <= n) = P(S_n >= c) [1]
Interessant! Was genau ist c?
Argh.. ein Druckfehler. Ich hatte in meinen "Privat-Berechnungen" c
statt s verwendet, aber wollte in meiner Antwort entsprechend deiner
Notation wieder s verwenden. Richtig muß es heißen

P(X_s <= n) = P(S_n >= s).

BTW erscheint mir die Kenntnis der kompletten Verteilung von S_n (Summe
von n [0,1)-gleichverteilten Zufallsvariablen) notwendig, um den Fall
s>1 betrachten zu können. Hast du die bei deiner Herleitung für die
Fälle s=2 und s=3 benutzt?

Für den Fall s<1 kommt man, wie ich bereits schrieb, auch ohne die
Verteilung von S_n aus. Mit etwas Geschick kann man die Formel
P(S_n <= t) = t^n/n!
erraten und dann mit vollständiger Induktion beweisen, ohne die
komplette Verteilung von S_n zu kennen - aber nur für t<1 klappt das.

Eine Rekursion von X_s auf X_{s+1} erscheint mir (erstmal für natürliche
s) schwierig bzw. nicht zielführend.
--
Post by Alfred Heiligenbrunner
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Martin Vaeth
2018-09-28 04:49:39 UTC
Permalink
Post by Stephan Gerlach
BTW erscheint mir die Kenntnis der kompletten Verteilung von S_n (Summe
von n [0,1)-gleichverteilten Zufallsvariablen) notwendig
Das ist die hier schon mehrmals angesprochene Irwin-Hall-Verteilung,
die auch im erwähnten Video vorkam. Damit alleine ist man aber noch
lange nicht am Ziel.
Stephan Gerlach
2018-09-29 00:06:35 UTC
Permalink
Post by Martin Vaeth
Post by Stephan Gerlach
BTW erscheint mir die Kenntnis der kompletten Verteilung von S_n (Summe
von n [0,1)-gleichverteilten Zufallsvariablen) notwendig
Das ist die hier schon mehrmals angesprochene Irwin-Hall-Verteilung,
die auch im erwähnten Video vorkam.
Kannte ich nicht bzw. hab' das Video noch gar nicht gesehen, sondern
habe nur "für mich selbst herumprobiert".
Post by Martin Vaeth
Damit alleine ist man aber noch
lange nicht am Ziel.
Trotzdem danke für den Tip, ich werd' mich demnächst mal über die
Irwin-Hall-Verteilung schlau machen.
--
Post by Martin Vaeth
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
a***@gmail.com
2018-09-30 05:45:50 UTC
Permalink
Post by Stephan Gerlach
Post by Stephan Gerlach
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine
berühmte Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Z_k = [0,1)-gleichverteilte Zufallsvariablen (im Plural), k Element N
S_n = Summe{k=1 bis n} X_k
Hier meintest du vermutlich:
S_n = Summe{k=1 bis n} Z_k
Post by Stephan Gerlach
Post by Stephan Gerlach
X_s = Anzahl Versuche, bis man einen Wert größer oder gleich s erreicht.
Gesucht ist E(X_s).
Bemerkenswert(?) an der ganzen Sache ist, daß für alle s Element R
P(X_s <= n) = P(S_n >= s).
BTW erscheint mir die Kenntnis der kompletten Verteilung von S_n (Summe
von n [0,1)-gleichverteilten Zufallsvariablen) notwendig, um den Fall
s>1 betrachten zu können. Hast du die bei deiner Herleitung für die
Fälle s=2 und s=3 benutzt?
Für den Fall s<1 kommt man, wie ich bereits schrieb, auch ohne die
Verteilung von S_n aus. Mit etwas Geschick kann man die Formel
P(S_n <= t) = t^n/n!
P(S_(n+1) <= t) = t^n/n!
Vgl. https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution#Special_cases
Post by Stephan Gerlach
erraten
Gratuliere!
Post by Stephan Gerlach
und dann mit vollständiger Induktion beweisen, ohne die
komplette Verteilung von S_n zu kennen - aber nur für t<1 klappt das.
Weiteres hat ja Martin Vaeth schon angemerkt und hast du auch schon beantwortet.
LG
Alfred
Stephan Gerlach
2018-10-05 23:59:50 UTC
Permalink
Post by a***@gmail.com
Post by Stephan Gerlach
Post by Stephan Gerlach
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine
berühmte Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Z_k = [0,1)-gleichverteilte Zufallsvariablen (im Plural), k Element N
S_n = Summe{k=1 bis n} X_k
S_n = Summe{k=1 bis n} Z_k
Ja, natürlich. Hab' von meinem Schmierzettel falsch abgeschrieben.
Post by a***@gmail.com
Post by Stephan Gerlach
Post by Stephan Gerlach
X_s = Anzahl Versuche, bis man einen Wert größer oder gleich s erreicht.
Gesucht ist E(X_s).
Bemerkenswert(?) an der ganzen Sache ist, daß für alle s Element R
P(X_s <= n) = P(S_n >= s).
BTW erscheint mir die Kenntnis der kompletten Verteilung von S_n (Summe
von n [0,1)-gleichverteilten Zufallsvariablen) notwendig, um den Fall
s>1 betrachten zu können. Hast du die bei deiner Herleitung für die
Fälle s=2 und s=3 benutzt?
Für den Fall s<1 kommt man, wie ich bereits schrieb, auch ohne die
Verteilung von S_n aus. Mit etwas Geschick kann man die Formel
P(S_n <= t) = t^n/n!
P(S_(n+1) <= t) = t^n/n!
n+1 statt n?
Der von dir angegebene Index n+1, statt wie bei mir n, könnte damit zu
tun haben, daß ich u.U. irgendwo eine andere Zählweise hatte, statt des
Relationszeichen > evtl. >= benutzt habe o.ä.
Post by a***@gmail.com
Vgl. https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution#Special_cases
Erstaunlich, daß es sogar eine (noch halbwegs übersichtliche)
geschlossene Formel für die Verteilung der Summe von n unabhängigen
[0,1]-gleichverteilten Zufallsvariablen Z_n gibt.
Die Schwierigkeit steckt IMHO in der oberen Summationsgrenze mit der
unteren Gaußklammer bzw. der Verwendung der sgn()-Funktion.

Im Prinzip ist das Ganze ja "nur" die Faltung von n
[0,1]-Gleichverteilungen, wie Roland bereits anmerkte.
Post by a***@gmail.com
Post by Stephan Gerlach
erraten
Gratuliere!
Ich hatte das zuerst für den Fall t=1, n=2 bestimmt; danach für den Fall
t=1, n=3. Da kann man sich die Wahrscheinlichkeit geometrisch als
Dreieck bzw. Pyramide, welche bis zu den Ecken eines Einheits-Quadrats
bzw. -Würfels reicht, vorstellen.
Allerdings brauchte ich für den Beweis für allgemeines n in einem
Integral in der Berechnung den Ausdruck für variables t in [0,1], nicht
nur für t=1. Wenn man Dreieck und/oder Pyramide im R^2 bzw. R^3
entsprechend maßstäblich verkleinert, kommt man auf den Faktor t^2 bzw.
t^3. Allgemein wird daraus dann t^n.
Post by a***@gmail.com
Post by Stephan Gerlach
und dann mit vollständiger Induktion beweisen, ohne die
komplette Verteilung von S_n zu kennen - aber nur für t<1 klappt das.
Weiteres hat ja Martin Vaeth schon angemerkt und hast du auch schon beantwortet.
Wo der Summand 2/3 herkommt, scheint ja nach wie vor unklar zu sein.
Am ehesten dürfte das mit der Approximation der Verteilung von S_n durch
die Normalverteilung beweisbar sein, die mir einfacher als die
Irwin-Hall-Verteilung erscheint. Ist aber nur eine Vermutung.
--
Post by a***@gmail.com
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Roland Franzius
2018-09-28 13:37:24 UTC
Permalink
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.
Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?
Nein, die gibt es

Die gesuchte Wahrscheinlichkeitsverteilung ist
Pr[Sum X_i >s ] = 1- Pr[sum X_i < s ] = 1 - Pr[ n/2 + sum Y_i < s ]
= 1 - Pr[ sum Y_i < s - n/2 ]

Wobei Y die in {-1/2,1/2} gleichverteilte Zufallsvariable ist.

Die Dichte der Verteilung der Summe gleichverteilter Zahlen ist die
n-fache Faltung der Dichte der Gleichverteilung, die sich bekanntlich
als stückweise polynominale Funktion der Normalverteilung mit Mittelwert
des Erwartungswertes der Summe und der Standardabweichung von sqrt(n) *
Standardabweichung der Gleichverteilung annähert.

Ein bischen mehr Symmetrie kann nicht schaden, also Gleichverteilung auf
(-1,1) rechnen.

Da die Faltung per Fouriertransformatione in die Multiplikation
übergeht, braucht man nur die inverse Fouriertransformation der n-ten
Potenz von

Versuch mal auf Wolfram alpha

f[n_] := g[n, x_] =
InverseFourierTransform[
FourierTransform[UnitStep[y] - UnitStep[y - 1], y, k]^12, k, x]

f[6]

(1/(2554675200 Sqrt[2] \[Pi]^(
11/2)))((-12 + x)^11 Sign[-12 + x] - 12 (-11 + x)^11 Sign[-11 + x] +
66 (-10 + x)^11 Sign[-10 + x] - 220 (-9 + x)^11 Sign[-9 + x] +
495 (-8 + x)^11 Sign[-8 + x] - 792 (-7 + x)^11 Sign[-7 + x] +
924 (-6 + x)^11 Sign[-6 + x] - 792 (-5 + x)^11 Sign[-5 + x] +
495 (-4 + x)^11 Sign[-4 + x] - 220 (-3 + x)^11 Sign[-3 + x] +
66 (-2 + x)^11 Sign[-2 + x] - 12 (-1 + x)^11 Sign[-1 + x] +
x^11 Sign[x])

Plot[g[6, x], {x, 0, 12}, PlotRange -> All]
--
Roland Franzius
a***@gmail.com
2018-09-30 06:04:25 UTC
Permalink
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.
Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?
Anschaulich sieht man es wohl so:
Wenn man mit einer Summe von positiven Zufallszahlen einen Wert s anpeilt, wird man s nur selten direkt treffen, sondern im Allgemeinen etwas darüber hinaus schießen. Sagen wir, im Mittel erreicht man s+1/3. Und dafür sind im Mittel 2*(s+1/3) Zufallszahlen aus [0,1) nötig.
Warum der Wert 1/3 ist, müsste man noch begründen. Auch, warum er für kleine s etwas höher ist.

LG
Alfred
Roland Franzius
2018-09-30 16:18:34 UTC
Permalink
Post by a***@gmail.com
Post by Alfred Heiligenbrunner
Hallo,
wie viele Zufallszahlen aus [0,1) braucht man im Mittel, damit deren
Summe einen Wert größer als s ergibt?
Mit Zufallszahlen sind gleichverteilte Zufallszahlen gemeint, wie man
sie üblicherweise in den gängigen Programmiersprachen zur Verfügung hat.
(Vergleiche für s=1 Edmund Weitz: Wie man "zufällig" auf eine berühmte
Zahl kommt: http://youtu.be/-2PA7SbWoJ0
Mit der Bezeichnung E ... "Erwartungswert der Anzahl der benötigten
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Der Wert für E nähert sich anscheinend immer mehr 2*s + 2/3 an.
Das kann man auch durch Simulation bestätigen.
Meine Frage: Gibt es eine anschauliche Begründung, warum E in der Nähe
von 2*s + 2/3 liegt?
Wenn man mit einer Summe von positiven Zufallszahlen einen Wert s anpeilt, wird man s nur selten direkt treffen, sondern im Allgemeinen etwas darüber hinaus schießen. Sagen wir, im Mittel erreicht man s+1/3. Und dafür sind im Mittel 2*(s+1/3) Zufallszahlen aus [0,1) nötig.
Warum der Wert 1/3 ist, müsste man noch begründen. Auch, warum er für kleine s etwas höher ist.
Es geht um die diskrete Form der Verteilung und der Erwartung für die
Zeit des ersten Treffers auf eine Bariere, das sogenannte
Ankunftszeitproblem.

Die Verteilung der n-fachen Summe unabhängiger, identisch verteilter,
reeller Zufallszahlen mit Mittelwert m und Varianz s^2 konvergiert rasch
gegen die Normalverteilung N(n m, n s^2).

Daher ist die Wahrscheinlichkeit, dass es bis zur Zeit n mindestens
einen Treffer auf die Grenze x>0 gibt, nach dem Reflektionsprinzip
gleich der doppelten Wahrscheinlichkeit, bis n die Grenze überschritten
zu haben, da die Wahrscheinlichkeit, bis n die Grenze zu treffen und
wieder darunter zu landen, ebenso groß ist, wie größer x zu sein.

Pr[ sum_(0<=i<=n) X_i > x] =
2 int_x^oo (2 pi n s^2)^(-1/2) e^(-(x- n m)^2/(2 n s^2))

Damit gilt offenbar für die Verteilung der Zeit des 1. Treffers mit n
Versuchen, x zu erreichen: T_n(x)

Pr[T_n(x) < t] = Pr[ sum_(0<=i<=n) X_i > x] =
1 + Erf[(n s - x)/(Sqrt[2 n] s)]

Ab ca n=6 ist die Verteilung der nfachen Faltung der Gleichverteilung
von der Normalverteilung kaum zu unterscheiden, wenn man mal davon
absieht, das sie kompakten Träger im Intervall n (min,max) hat und sich
daher die Gauss-Näherung für extrem seltene Ereignisse nicht eignet.
--
Roland Franzius
Martin Vaeth
2018-09-30 19:06:30 UTC
Permalink
Post by a***@gmail.com
Post by Alfred Heiligenbrunner
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Warum der Wert 1/3 ist, müsste man noch begründen.
Auch, warum er für kleine s etwas höher ist.
Und vor allem, warum er für etwas größere s sogar kleiner ist
also der vermutete Grentwert und folglich für noch größere s
wieder wachesn muss (falls der Grenzwert richtig sein sollte).
Also ein oszillierendes Verhalten um den Grenzwert.
Laut den paar Beispielen sieht es aber eher so aus, als wenn
der Wert streng monoton fällt; gegen welchen Grenzwert auch immer.
alfred(punkt)heiligenbrunner(at)gmx(punkt)at
2018-10-01 02:05:11 UTC
Permalink
Post by Martin Vaeth
Post by a***@gmail.com
Post by Alfred Heiligenbrunner
s = 1, E = e = 2,7182;
s = 2, E = e * (e-1) = 4,67077;
s = 3, E = e^3 - 2 e^2 + e/2 = 6,66657;
s = 10, E = 20,66666666647;
Warum der Wert 1/3 ist, müsste man noch begründen.
Auch, warum er für kleine s etwas höher ist.
Und vor allem, warum er für etwas größere s sogar kleiner ist
also der vermutete Grentwert und folglich für noch größere s
wieder wachesn muss (falls der Grenzwert richtig sein sollte).
Also ein oszillierendes Verhalten um den Grenzwert.
Laut den paar Beispielen sieht es aber eher so aus, als wenn
der Wert streng monoton fällt; gegen welchen Grenzwert auch immer.
Ja, sieht so aus, als ob er sich oszillierend nähert.
Hier eine Tabelle mit s, E(X_s), E(X_s)-2s-2/3:
1 2.71828182845905 0.0516151617923786
2 4.67077427047160 0.00410760380493833
3 6.66656563955589 -0.000101027110776763
4 8.66660449003270 -0.0000621766339712294
5 10.6666620686224 -4.59804425480865*10^-6
6 12.6666671413781 4.74711454734705*10^-7
7 14.6666667815221 1.14855476783143*10^-7
8 16.6666666704269 3.76022115699568*10^-9
9 18.6666666652703 -1.39634531771114*10^-9
10 20.6666666664763 -1.90347866052504*10^-10
11 22.6666666666700 3.32451023222205*10^-12
12 24.6666666666699 3.23366275290457*10^-12

LG
Alfred
Loading...