Lawinenartiger stochastischer Prozess

16

Betrachten Sie den folgenden Prozess:

Es gibt Fächer, die von oben nach unten angeordnet sind. Anfangs enthält jeder Behälter eine Kugel. In jedem Schritt wirn

  1. Wählen Sie eine Kugel gleichmäßig zufällig undb
  2. Bewegen Sie alle Kugeln aus dem Behälter mit in den Behälter darunter. Wenn es bereits der niedrigste Behälter war, entfernen wir die Kugeln aus dem Prozess.b

Wie viele Schritte dauert es in Erwartung, bis der Prozess beendet ist, dh bis alle Kugeln aus dem Prozess entfernt wurden? Wurde das schon einmal untersucht? Ergibt sich die Antwort leicht aus bekannten Techniken?n

Im besten Fall kann der Vorgang nach Schritten beendet werden. Im schlimmsten Fall kann es Θ ( n 2 ) Schritte dauern . Beide Fälle sollten jedoch sehr unwahrscheinlich sein. Meine Vermutung ist, dass es Θ ( n log n ) Schritte dauert und ich einige Experimente durchgeführt habe, die dies zu bestätigen scheinen .nΘ(n2)Θ(nLogn)

(Beachten Sie, dass das gleichmäßige und zufällige Auswählen eines Behälters ein ganz anderer Vorgang ist, für dessen Abschluss offensichtlich Schritte erforderlich sind .)Θ(n2)

Matthias
quelle
Die Frage sieht interessant aus (obwohl ich die Antwort nicht kenne). Es scheint schwierig zu sein, weil es keine Monotonie gibt. Wenn sich alle n Bälle im oberen Behälter befinden, endet der Vorgang eindeutig in genau n Schritten.
Tsuyoshi Ito

Antworten:

11

Keine wirkliche Antwort, aber ein ausführlicher Kommentar zu András 'Antwort.

Die Antwort von András enthält eine nette Intuition, obwohl ich nicht glaube, dass es eine rigorose Berechnung der erwarteten Anzahl von Schritten ist. Ich denke, es ist vielleicht eine gute Annäherung an eine Antwort, aber es scheint nicht richtig mit Fällen umzugehen, in denen der Behälter unter dem höchsten belegten Behälter leer wird, bevor der obere Behälter nach unten geleert wird. Trotzdem könnte dies eine vernünftige Annäherung sein (ich bin mir nicht sicher).

Seine Berechnung enthält einen Fehler, der die Skalierung beeinflusst. Ich werde genau den gleichen Ausgangspunkt nehmen und die Berechnung wiederholen und erweitern.

Es fehlt ein Faktor von p innerhalb der Summation, da die Wahrscheinlichkeit der zufälligen Auswahl des richtigen Bins statt1pn . Als Ergebnis haben wir1n

n+p=1nk=0(k+1)pn(n-pn)k=n+p=1npnk=0(k+1)(n-pn)k=n+p=1npnn2p2=n+np=1n1/p=n(1+Hn)

Dabei ist die n-te Harmonische . Um sich H n anzunähern, können wir die Summation einfach durch ein Integral ersetzen: H nn + 1 1 1Hn=p=1n1/pHn. Somit ist die Skalierungn(1+log(n+1))oder ungefährnlog(n+1). Obwohl diese Skalierung nicht genau mit der Skalierung des Problems übereinstimmt (siehe Simulation unten), ist sie um einen Faktor von fast genaulog(2)niedriger.Hn1n+11xdx=Log(n+1)n(1+Log(n+1))nLog(n+1)Log(2)

Simulation gegen Theorie

nLog2(n+1)nLog(n+1)

Joe Fitzsimons
quelle
ln2
@ András: Ich habe nicht wirklich ein gutes Gefühl dafür, ob dies eine solide Annäherung ist oder nicht. @ Peters Vorstellung, dass sich Trauben bilden, die sich nach unten verschieben, scheint den richtigen Ausdruck zu geben, vorausgesetzt, dass sich diese gleich wahrscheinlich in jedem Behälter bilden.
Joe Fitzsimons
@Joe: Der oberste Ball bleibt in fast 1/3 der Fälle isoliert. Betrachten Sie die Top 3 Bälle. Wenn der mittlere zuerst ausgewählt wird (von diesen 3), wird er dem dritten hinzugefügt. Diese beiden bewegen sich fortan doppelt so schnell wie der obere Ball. Der Abstand zwischen ihnen und dem oberen Ball ist ein stark voreingenommener Zufallsrundgang, und die Wahrscheinlichkeit, dass der obere Ball aufholt, ist durch eine kleine (ish) Konstante begrenzt (grobe Schätzung 15%). Aber die gute Nachricht ist, dass die Top-Log-n-Bälle eigentlich keine Rolle spielen sollten. Wenn alles andere in n \ log n Schritten gelöscht wird, werden nur weitere n \ log n Schritte hinzugefügt.
Matthias
nLogn
@Matthias: Die Analyse der erwarteten Zeit unter der Annahme, dass Peters Intuition korrekt ist, ist nicht die Straßensperre (zumindest aus meiner Sicht). Für mich ist es zunächst notwendig zu beweisen, dass diese Intuition tatsächlich eine gerechte Reflexion dessen ist, was passiert, obwohl ich vermute, dass es eine gute Annäherung ist.
Joe Fitzsimons
9

Bearbeiten: Ich lasse diese Antwort wie sie ist (für den Moment), um den chaotischen Prozess des Beweisens von Theoremen zu veranschaulichen, etwas, das in veröffentlichten Veröffentlichungen weggelassen wurde. Die Kernintuition hier ist, dass es ausreicht, sich auf den oberen Ball zu konzentrieren, da er alles darunter wegfegt. Bitte beachten Sie die Kommentare (insbesondere @Michael, der darauf hinweist, dass Lücken auftreten können) und @ Joes spätere Antwort, wie Fehler identifiziert und korrigiert wurden. Ich mag besonders Joes Experimente, um zu überprüfen, ob die Formeln sinnvoll sind.


n(1+π2/6)n

b1b2bnb1=nb2n-1bichn-ich+1b1b2bn1,2,,n). Diese Ereignisse können nacheinander als separate Ereignisse betrachtet werden. Die erwartete Anzahl von Schritten ist dann

n+p=1nk=0k+1n(n-pn)k=n+p=1n-11n-pk=1k(n-pn)k=n+p=1n-11n-pn(n-p)/p2=n+np=1n-11/p2(1+π2/6)n.

András Salamon
quelle
3
@Andras @Joe: Heiliger Schmoley. Wenn alle Personen, die Fragen auf dieser Website stellen, ihre Fragen genauso ernst nehmen, wie Sie sie beantworten, wäre dies die schlimmste URL im Internet.
Aaron Sterling
1
@ András: Ich versuche deine Aussage zu verstehen "Eine Abfolge von Bällen löscht alle Fächer genau dann, wenn sie eine Untersequenz enthält ...". Vielleicht habe ich etwas falsch verstanden, aber wir haben vier Bälle. Wenn die Sequenz 3,4,3,2,4 ist, scheint sie Ihre Untersequenzanforderung zu erfüllen, jedoch wurden nicht alle Fächer gelöscht.
Michael
1
@ András: Wenn du eine vernünftige Obergrenze anzeigen willst, musst du die Tatsache nutzen, dass Kugeln aus dem Prozess verschwinden und nicht mehr gepickt werden. Andernfalls wird der oberste Ball immer nur mit einer Wahrscheinlichkeit von 1 / n gepickt, und es besteht eine gute Chance (möglicherweise etwas weniger als 1/2), dass dieser Ball die ganze Zeit isoliert bleibt. Für diesen Ball benötigen Sie n ^ 2 Stufen.
Matthias
1
@Michael: Ich denke, Sie haben den Fehler identifiziert. Ich gehe fälschlicherweise davon aus, dass sich der obere Ball nach unten bewegt, auch wenn es eine Lücke gibt.
András Salamon
2
Ö(n)Ö(nLogn)n/2Logn