Diskussion:Monte-Carlo-Algorithmus

Beispiel "Miller-Rabin-Test" (Primzahltest)

Die im Artikel getroffene Aussage über den möglicherweise auftrentenden Fehler bei diesem Monte-Carlo-Algorithmus ist (a) unscharf und denkt sich (b) nicht mit der Aussage des Artikels Miller-Rabin-Test. Dort steht, dass sich der Algorithmus in der Aussagen "Es ist eine Primzahl" Fehler erlaubt.

--bastian 10:07, 2. Mär 2006 (CET)

Peinlich genug, dass es drei Jahre dauert, bis sich jemand dieses Fehlers annimmt :( --Rat 16:50, 25. Mai 2009 (CEST)

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:59, 4. Jul. 2023 (CEST) (Beantwortet. MfG)

Beispiele "Probabilistische Bestimmung von Pi" und "Numerische Integration"

In der jetzigen Form sind die Beispiele nicht instruktiv und vielleicht sogar ein wenig irreführend. Hauptproblem ist, dass die Konzepte "Randomisierung" und "Approximation von reellen Zahlen" in diesen Beispielen vermischt sind, was für einen Lexikoneintrag zumindest störend ist. Das zweite Problem ist, dass eine Analyse fehlt; im Artikel randomisierte Algorithmen wird ausdrücklich darauf hingewiesen, dass eine Abschätzung von Rechenzeit und/oder Fehlerwahrscheinlichkeit dazugehört, während man sonst von heuristischen Algorithmen spricht. Hier ein Vorschlag, wie das für die Berechnung von Pi aussehen könnte, analoges gilt für numerische Integration:

Das betrachtete Problem lautet:

Eingabe: natürliche Zahl n

Ausgabe: die ersten n Stellen der Zahl Pi

Algorithmus: (stark verkürzt) Führe den derzeit im Artikel genannten Algorithmus mit N=???? Iterationen aus.

Analyse: Benutze Chernoff-Schranke, um zu zeigen, dass die Fehlerwahrscheinlichkeit (die Wahrscheinlichkeit, dass die Ausgabe nicht die ersten n Stellen von Pi sind) durch einen festen Wert (z.B. 0,5) beschränkt ist.

Habe im Moment keine Zeit, das auszuführen (also eine Formel für N anzugeben, so dass die Fehlerwahrscheinlichkeit höchstens 0,5 ist), vielleicht kann dies einer der Autoren von Approximation von Pi bzw. Numerische Integration nachholen.

Die Analyse ist natürlich auch wichtig, um zu sehen, ob das Verfahren überhaupt praktikabel ist, was nützt es, wenn man für die Berechnung von n Stellen etwa 2^{2^n}} Schritte braucht?

--Deesy 15:09, 1. Mär 2006 (CET)

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:59, 4. Jul. 2023 (CEST) (Verjährt. Siehe die Fachliteratur. MfG)

Monte Carlo für Englisch mostly correct?

Ich lese immer wieder, dass es sich auf die Spielhöllen in Monte Carlo bezieht. Dass es etwas mit "mostly correct" (meist richtig) zu tun haben soll, möchte ich bezweifeln. Hat jemand hierfür einen Hinweis? Ansonsten schlage ich vor, diese Erklärung zu entfernen. Stern 21:46, 26. Mär 2006 (CEST)

Natürlich ist dies keine Übersetzung, sondern nur eine Merkregel, anhand derer man sich den Unterschied zwischen Las-Vegas-Algorithmen und Monte-Carlo-Algorithmen merken kann. Das zu erklären, ist hier viel zu umständlich, also habe ich diese "Übersetzung" entfernt.

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:59, 4. Jul. 2023 (CEST) (Zur Geschichte siehe Monte-Carlo-Simulation. MfG)

Anwendung von Chernoff-Schranken auf "Probabilistische Bestimmung der Zahl Pi"

Hier die oben angedachte Abschätzung von N, sodass Pi mit einer Fehlerwahrscheinlichkeit von höchstens 0,5 auf k Stellen genau berechnet wird:

Die Chernoff-Ungleichung besagt: Seien X_1,...,X_N unabhängige 0-1-Zufallsvariablen mit Prob(X_i=1)=p und Prob(X_i=0)=1-p. Sei X=X_1+...+X_N. Dann ist E[X]=np und für alle \delta\in(0,1) gilt:Prob (X<=(1-\delta) E[X]) <= e^{-E[X]\delta^2 /2}. Für das Überschreiten des Erwartungswertes um einen Faktor (1+\delta) gibt es eine ähnliche Formel. (Sorry, dass ich die Formeln nur in Latex-Notation darstelle.)

Im Beispiel Approximation von Pi ist N die Anzahl der Iterationen und X_i die Zufallsvariable, die angibt, ob in der i-ten Iteration ein Punkt innerhalb oder außerhalb des Einheitskreises getroffen wird, also ist p=\pi/4. Wenn Pi auf k Dezimalstellen genau berechnet werden soll, wählen wir \delta=10^{-k}. Weiterhin ist E[X]=N\pi/4.

Wir wollen nun die Wahrscheinlichkeit, Pi auf weniger als k Dezimalstellen genau zu berechnen, auf einen Wert von höchstens 0,5 bringen. Wir vernachlässigen Fall, dass die Approximation zu groß wird, und betrachten nur den Fall, dass die Approximation kleiner/gleich (1-\delta) \pi/4 wird. Die Summe von X_1,...,X_N wird in diesem Fall kleiner/gleich (1-\delta) N\pi/4. Nach der Chernoff-Ungleichung erhalten wir den Ansatz

e^{-N (\pi/4) (\delta^2 /2) \leq 0,5.

Auflösen nach n und Einsetzen von \delta liefert

n >= 8*10^{2k}*(ln 2) / \pi.

Wenn wir also Pi mit dem beschriebenen Verfahren mit einer Wahrscheinlichkeit von mindestens 0,5 auf gerade einmal 10 Stellen hinter dem Komma genau berechnen wollen, benötigen wir nach dieser Abschätzung 1,7*10^20 Iterationen. D.h., wenn wir eine solche Berechnung auf einem heutigen Rechner starten, werden wir das Ende nicht mehr erleben.

Was lernen wir daraus? Ein Ad-hoc-Verfahren wie das im Artikel beschriebene ist nicht unbedingt gut. Das Beispiel ist eher ein Beispiel, wie man es nicht machen sollte. Soll das in dem Artikel bleiben?

Dieselbe Frage stellt sich zum Beispiel "Numerische Integration". Ich habe das Gefühl, dass auch die neu eingefügten Bilder nicht hilfreich für das Verständnis sind. Die Qualität des Verfahrens ist zumindest zweifelhaft. Vielleicht hat der Autor ja Begründungen, warum das Verfahren besser als beispielsweise die Simpson-Formel zur Numerischen Integration sein soll. Dann sollte dies erklärt werden, anderenfalls sollte auch des zweite Beispiel gelöscht werden.

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:59, 4. Jul. 2023 (CEST) (Verjährt. Keine Antworten. Keine Signatur. Bitte neuer Kommentar. MfG)

Woher kommt der Name Monte-Carlo-Algorithmus?

Unter der Gefahr dass die Frage bereits gestellt wurde (bei mir zumindest gehört das zu einer der erste Fragen): Warum heißt der Monte-Carlo-Algorithmus eigentlich so? Weiß da jemand was genaueres zu?

Siehe https://en.wikipedia.org/wiki/Monte_Carlo_method#History (MC Geschichte fehlt meines Erachtens auf der DE Seite)

"It was at that time that I [N Metropolis] suggested an obvious name for the statistical method-a suggestion not unrelated to the fact that Stan had an uncle who would borrow money from relatives because he "just had to go to Monte Carlo."" [THE BEGINNING of the MONTE CARLO METHOD by N Metropolis] - https://fas.org/sgp/othergov/doe/lanl/pubs/00326866.pdf --LS (Diskussion) 17:08, 13. Aug. 2019 (CEST)

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:59, 4. Jul. 2023 (CEST) (Zur Geschichte siehe Monte-Carlo-Simulation. MfG)

Namensherkunft

Woher der Name "Monte-Carlo-Algorithmus" stammt interessiert mich auch, speziell in Anlehnung an den "Las-Vegas-Algorithmus", der eine andere Art von randomisierten Algorithmus darstellt. Falls das jemand weiss, bitte nicht zögern und einfach in die Tastatur hauen. - Markus, 80.219.7.18 17:58, 12. Jan. 2008 (CET)

Siehe https://en.wikipedia.org/wiki/Monte_Carlo_method#History (MC Geschichte fehlt meines Erachtens auf der DE Seite)

"It was at that time that I [N Metropolis] suggested an obvious name for the statistical method-a suggestion not unrelated to the fact that Stan had an uncle who would borrow money from relatives because he "just had to go to Monte Carlo."" [THE BEGINNING of the MONTE CARLO METHOD by N Metropolis] - https://fas.org/sgp/othergov/doe/lanl/pubs/00326866.pdf --LS (Diskussion) 17:08, 13. Aug. 2019 (CEST)

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:45, 4. Jul. 2023 (CEST) (Beantwortet.)

--17387349L8764 (Diskussion) 16:45, 4. Jul. 2023 (CEST)

Quellen zur Namensherkunft

Laut dem Glossar des Complexity Zoos (http://qwiki.stanford.edu/wiki/Zoo_Glossary) stammt der Ausdruck Monte-Carlo-Algorithmus von Metropolis und Ulam und der Ausdruck Las-Vegas-Algorithmus von Babai. Von der Arbeit von Babai ist ein pdf verfügbar (http://people.cs.uchicago.edu/~laci/lasvegas79.pdf). Letzteres interpretiere ich nach kurzem Scannen so, dass Babai einfach einen anderen Namen für eine spezielle Sorte von Algorithmen einführen wollte. Konsistent hiermit ist die Erklärung in http://answers.google.com/answers/threadview?id=232876, nach der der Name Monte-Carlo-Methode auf Ulams Vorliebe für Poker zurückgeht. Vielleicht kann dies ja noch jemand mit anderen Quellen verifizieren.

Falls das jemand in den Artikel einarbeiten möchte, sollte sie/er bei dieser Gelegenheit auch obige Anmerkungen zur Effizienz der Monte-Carlo-Methoden für die Berechnung von Pi und die numerische Integration berücksichtigen und diese löschen oder zumindest die Unsinnigkeit des Ansatzes deutlich machen.

Siehe https://en.wikipedia.org/wiki/Monte_Carlo_method#History (MC Geschichte fehlt meines Erachtens auf der DE Seite)

"It was at that time that I [N Metropolis] suggested an obvious name for the statistical method-a suggestion not unrelated to the fact that Stan had an uncle who would borrow money from relatives because he "just had to go to Monte Carlo."" [THE BEGINNING of the MONTE CARLO METHOD by N Metropolis] - https://fas.org/sgp/othergov/doe/lanl/pubs/00326866.pdf --LS (Diskussion) 17:09, 13. Aug. 2019 (CEST)

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:45, 4. Jul. 2023 (CEST) (Beantwortet. MfG)

--17387349L8764 (Diskussion) 16:45, 4. Jul. 2023 (CEST)

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen

Also ich find diesen Abschnitt über Komplexitätsklassen ja hoch interessant aber was hat das mit dem Thema zu tun?

Im Ganzen Abschnitt wird nicht auf Monte-Carlo-Algorithmen eingegangen. Das sollte gelöscht oder in einen neuen Artikel gebracht werden.--82.83.102.36 19:45, 17. Jan. 2011 (CET)

Wieso? Nach der Definition in der Einleitung wird hier jeder Algorithmus, der Zufallszahlen verwendet, bei den Monte-Carlo-Algorithmen mitgezählt. Also gelten auch diese Komplexitätsklassen für alle Monte-Carlo-Algorithmen. Oder habe ich jetzt was falsch verstanden? --PeterFrankfurt 02:57, 18. Jan. 2011 (CET)

Jeder Algo, der Zufallszahlen verwendet, wird als MC-Algo gezählt? Wo ist das definiert? MfG --17387349L8764 (Diskussion) 16:55, 4. Jul. 2023 (CEST)

Definition?

Die Definition und die allgemeine Beschreibung bezieht sich nur auf Beispiele wie Primzahltests. Bei der wichtigen Anwendung Berechnung hochdimensionaler Integrale passt das alles nicht: Was soll dann ein "falsches Ergebnis" sein, das erlaubt ist? Wenn eine reelle Zahl berechnet werden soll, ist das Ergebnis immer "falsch", egal welchen Algorithmus man nimmt. Es geht eher darum, ein zufälliges Ergebnis zu liefern, das eine "gute" Schätzfunktion für den exakten Wert ist. Kennt jemand eine bessere/allgemeinere Beschreibung der Monte-Carlo-Methoden in der Literatur? -- HilberTraum 20:18, 19. Dez. 2011 (CET)

Literatur auf beiden Seiten (-Simulation) und hier verbessert. Die Aufteilung ist m. E. unglücklich. MfG

Dieser Abschnitt kann archiviert werden. 17387349L8764 (Diskussion) 16:47, 4. Jul. 2023 (CEST) (Beantwortet.)

--17387349L8764 (Diskussion) 16:47, 4. Jul. 2023 (CEST)

Bitte Verlinkung korrekt setzen

die Verlinkung Fehlerwahrscheinlichkeit führt auf eine BKseite. Bitte exakt verlinken. --Pm (Diskussion) 15:25, 19. Dez. 2012 (CET)

Verlinkt mittlerweile auf Fehler 1. Art. MfG --17387349L8764 (Diskussion) 16:52, 4. Jul. 2023 (CEST)

Monte-Carlo-Direktsimulation [Direct Simulation Monte Carlo , DSMC]

Wie ordnet sich die Monte-Carlo-Direktsimulation [Direct Simulation Monte Carlo , DSMC] ein? --Cepheiden (Diskussion) 14:53, 27. Feb. 2021 (CET)

Valider Punkt. Hier ein Buchkapitel dazu. Oder ist das eine "MC-Simulation"? Die Aufteilung des einen Thema in Simulation/Algorithmus macht es nicht einfacher. MfG --17387349L8764 (Diskussion) 16:51, 4. Jul. 2023 (CEST)