Upload
ngoquynh
View
214
Download
0
Embed Size (px)
Citation preview
Fakultät für PhysikInstitut für Experimentelle Teilchenphysik
www.kit.eduKIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
Günter Quast
WS 18/19
Vorlesung:
Rechnernutzung in der Physik
Simulation mit der Monte Carlo-Methode
Organisatorisches
Bitte melden Sie sich im Studierendenportal zur Veranstaltung Rechnernutzung in der Physik an !
Zusammenfassung: Bedeutung der MC-Methode
Die Monte-Carlo-Methode (auch „MC-Simulation“) - abgeleitet vom Namen der durch ihr Spielkasino berühmten Stadt Monte Carlo -ist eine auf (Pseudo-)Zufallszahlen basierende numerische Methode zur
● Integration in hochdimensionalen Räumen
● Bestimmung der Eigenschaften von Verteilungen von Zufallszahlen (z.B. von Messgrößen in Experimenten)
● Nachbildung von komplexen Prozessen (z.B. in Thermodynamik, Wirtschaft oder von experimentellen Apparaturen, u.v.a.)
I. Erzeuge Folge von Zufallszahlen r1 , r2, …, rm, gleichverteilt in ]0,1].
II. Transformiere diese zur Erzeugung einer anderen Sequenz x1 , x2, …, xn , die einer Verteilungsdichte f(x) folgen (Anm.: xi können auch Vektoren sein !)
III. Aus den xi werden dann Eigenschaften von f(x) bestimmt
Vorteil: einfache Operationen mit den xi ersetzen sehr viel komplexere Operationen auf den Verteilungsdichten
Grundsätzliche Vorgehensweise:
Übersicht
● Grundsätzliches zur MC-Methode● MC als Integrationsverfahren● Zufallszahlen aus dem Computer
heute: ● Zufallszahlen mit beliebiger Verteilungsdichte● Anwendungsbeispiele
Erzeugung von Zufallszahlen mit beliebiger Verteilungsdichte
Funktionen von ZufallszahlenComputerexperiment:
Häufigkeitsverteilung von
...r = np.random.rand(10000)t = -np.log(1-r)
plt.hist(t, 30, normed=1)
plt.show()
Wir erhalten exponentiell verteilte Zufallszahlen t !
Regel für die Transformation von Verteilungsdichten
Erklärung:
Erhalt der Wahrscheinlichkeit
Anm.: t=log(r) statt t=log(1-r) ergibt identisches Ergebnis (warum?)
Funktionen von Zufallszahlen allgemein
Für mehrdimensionale Wahrscheinlichkeitsdichten wird
zur Jacobi-Determinante:
Wahrscheinlichkeitsdichte von x multipliziert mit dem Betrag der Ableitung der Inversen Funktion a-1(u)
Ganz analog zur Transformation von Volumenelementen bei mehrdimensionalen Integralen
„Transformationsmethode“ zur Erzeugung von Zufallszahlen
Den Zusammenhang zwischen der ursprünglichen Verteilungsdichte f(r) und
derjenigen einer Transformation t(r) können wir ausnutzen, um
beliebig verteilte Zufallszahlen zu erzeugen:
Welche Transformation t(r) liefert g(t) ?
Die gesuchte Transformation ist die Inverse der Verteilungsfunktion G von g
Anm: Das Verfahren ist nur dann (effizient) praktikabel, wenn die gesuchte Verteilungsdichte integrierbar und das Integral invertierbar ist !
Beispiele Transformationsmethode
Dreieck-Verteilung
Exponentialverteilung
Paar von Gauß-verteilten Zahlen
Anm.: 1-r kann durch r ersetzt werden
Breit-Wigner-Verteilung
Log-Weibull -Verteilung
Erzeugung diskreter Verteilungen
Das gezeigte Verfahren funktioniert auch für diskrete Verteilungen
Durch Summation aller Bins der diskretenVerteilung erhält man die Verteilungsfunktion, repräsentiert als eindimensionales Feld S(j)
Eine Zufallszahl ri wird demjenigen Bin jzugeordnet, das dem kleinsten der S(j) mit ri >S(j) entspricht
Beispiel Poisson-Verteilung
Verteilungen aus Histogrammen
Allgemein kann die Transformationsmethode auch zur Erzeugung von Zufallszahlenverteilungen aus vorgegebenen Histogrammen verwendet werden:
gleichverteilte Zufallszahl ri bestimmt das Bin k
Der Rest ri - S(k-1) kann zur Interpolation innerhalb des Bins verwendet werden
Auch für mehr-dimensionale Verteilungen:
bilde für jedes i: Randverteilung gi = ∑ hij
(also Projektion von hij in j)
berechne Summenverteilungen über j
generiere i und dann für gegebenes i eine Bin-Nummer j
Quelle: Wikipedia
von Neumann'sches Rückweisungsverfahren
Ein allgemein anwendbares, aber nicht immer effizientes Verfahren geht so:
x
y=f(x)
xmax xmin
Beispiel: Kreisbogen als Verteilungsdichte f(x)
- Verteilungsdichte wird in Rechteck („Box“) eingeschlossen
- erzeuge gleichförmig in der Box verteilte Paare von Zufallszahlen (xi, yi)
- x-Werte aus Paaren mit y < f(x) werden akzeptiert ( mit einer Wahrscheinlichkeit f(x) / fmax )
Die Häufigkeitsverteilung der akzeptierten x-Werte folgt der gewünschten Verteilung
Anm: Im gezeigten Beispiel funktioniert das Verfahren effizient; Wenn die Verteilung steil abfällt und Werte für x→∞ benötigt werden, kann die Zahl der verworfenen Zufallszahlen unakzeptabel groß werden.
Anwendungsbeispiel: 2d-Verteilung aus Bild
Auch aus Histogrammen lassen sich Stichproben erzeugen, die gemäß der vorgegebenen Häufigkeit verteilt sind.
...#open an imageimg=Image.open('image.jpeg')# img.show()print "image size:", img.size[0], img.size[1]pix=img.load()
def rand_fromImage(): # return pixel coordinate with a probability # proportional to brightness of the pixel r0=np.random.uniform() r1=np.random.uniform() i=int(img.size[0] * r0 - 0.5) j=img.size[1] -1 – int(img.size[1] * r1 - 0.5) r,g,b = pix[i,j] # brightness of pixel if(3*255*np.random.uniform() > r+b+g): return r0, r1...
Script Distribution-fromImage.pyRückweisungs-Schritt
Hier ein Beispiel, bei dem die Wahrscheinlichkeit der Helligkeit eines Pixels in einem Bild entspricht:
Majoranten-Verfahren (engl. Importance Sampling)
Verbesserte Wegwerfmethode:
Wenn eine Funktion m(x) mit m(x) > f(x) für alle x existiert und x=M-1(r) hinreichend leicht bestimmbar ist (d.h.Stammfunktion von m ist invertierbar)
– generiere xi=M-1(r2i) und eine weitere Zufallszahl r2i+1 ∈ [0,1] – akzeptiere xi, wenn r2i+1 ∙ m(x) < f(x) ist (für jeden Wert von x wird ein Bruchteil (m(x) -f(x) ) / f(x) an x-Werten verworfen)
Die akzeptierten Werte von x sind gemäß f(x) verteilt.
Beispiel: mit Hilfe von zwei Majoranten kann ein Planck'sches Strahlungs- spektrum effizient erzeugt werden.
Verfahren zur Varianzreduktion
Subtraktion eines analytisch lösbaren Funktionsanteils f(x)
Stratified Sampling („geschichtete“ Stichprobe)
Hohe (niedrige) Ereignisrate in Bereichen von hohem (niedrigem) Interesse (z.B. in der Nähe von Singularitäten und in Ausläufern)
Integration für eine leicht modifizierte Funktion gm ( x i)
Verwende Gewichte zur Berechnung
Wird in der Teilchenphysik extrem häufig verwendet, z.B. Abschätzung der Auswirkung systematischer Unsicherheiten auf das Endergebnis
Funktioniert auch mit negativen Gewichten
Beispiel gaußverteilte Zufallszahlen
Problem: ∫ exp(-x2) dx nur numerisch bestimmbar
( in C, C++ über die Funktion verfügbar)
Gauß-Funktion in 2 Dimensionen in Polarkoordinaten analytisch integrierbar:
Verteilungsfunktion des Radialteils lässt sich nach r auflösen – d.h. können Transformationsmethode anwenden !
Erzeuge zwei gleichverteilte Zufallszahlen u1, u2 ]∈] 0,1] , setze x1= √(-2ln u1) cos(2π u2) x2= √(-2ln u1) sin(2π u2) , x1 und x2 sind standardnormalverteilt
Gleichverteiung in Φ, Radialverteilung integrierbar mit r dr = ½ dr2
=>
Effizienteres Verfahren (s. V. Blobel)
(Beispiel für die Kombination aus Transformations- und Rückweisungsverfahren)
1. erzeuge zwei gleichverteilte Zufallszahlen u1, u2 ∈ [0,1[ setze v1:= 2u1 -1 , v2 := 2u2-12. v2=v12 + v22 3. falls v2 ≥ 1 → gehe zu 1 (Rückweisungsschritt)
(akzeptierte Werte von v1, v2 gleichverteilt innerhalb des Einheitskreises)
4. z1= v1 √(-2 ln(v2) /v2 ) z2= v2 √(-2 ln(v2) / v2 ) z1 und z2 sind dann unabhängig voneinander standard-normalverteilt
Normalverteilte Zufallszahlen mit Erwartungwert μ und Standardabweichung σ erhält man durch die Transformation x = σ z + μ
Trigonometrische Funktionen sind numerisch aufwändig, ein etwas effizienteres Verfahren geht so:
Erzeugung korrelierter, gaußverteilter Zufallszahlen
Gaußverteilung in n Dimensionen:
x0: n ErwartungswerteV: Kovarianz-Matrix mit (n2+n)/2 unabhängigen Parametern |V|=det V ist die Determinante von V
Sei B = V-1, schreibe B als Produkt aus Dreiecksmatrizen: B = DT D („Cholesky-Zerlegung“)
Setzte dann =>
Das ist die Verteilung von n unkorrelierten , Gauß-verteilten Zufallszahlen u
Damit ist die Vorgehensweise klar: 1. würfle n unabhängige Gauß-verteilte Zufallszahlen u 2. transformiere Vektor u:
Zwischenrechnung für zwei Dimensionen
mit D21=0
Blobel/Lohrmann Abschnitte 5.4 und 3.6
Cholesky-Zerlegung:
Korrelierte gaußverteilte Zufallszahlen in 2 Dimensionen
Daraus ergibt sich für die Erzeugung von zwei korrelierten Zufallszahlen x1, x2 mit - Erwartungswerten μ1 , μ2
- Standardabweichungen σ1 , σ2 und - Korrelation ρ
Details s. z.B. Blobel / Lohrmann
Darstellung eines 2d-Histogramms, gefüllt mit 75% korrelierten, standard-normal- verteilten Zufallszahlen ( s. Beispiel rangauss2d.C bzw. rangauss2d-pyroot.py )
besondere MC-Methode: Bootstrapping
Sich an den Schuhriemen (oder, wie Münchhausen) an den eigenen Haaren aus dem Sumpf ziehen
??? Bestimmung der statistischen Unsicherheit von T bei unbekannter Verteilungsdichte ???
Gesucht: Funktionen T( {xi } ) einer Stichprobe {xi }
Für T = Mittelwert oder T = Varianz gibt es allg. Formeln.
Für Median, Quantile, Ergebnis einer Parameteranpassung etc. gibt es allerdings keine allg. analytischen Formeln.
Ausweg „Toy-MC“: Ziehen vieler vergleichbarer Stichproben k aus angenommener Verteilung der Grundgesamtheit - jeweils Tk bestimmen, Varianz von T aus Varianz der Tk .
→ Bootstrapping (B. Efron, 1979)
BootstrappingIdee: Verwende neu gemischte Versionen der beobachteten Stichprobe statt einer angenommenen Verteilungsdichte der Grundgesamtheit !
Die Methode besteht also darin, weitere Stichproben zu gewinnen, die so aussehen, wie die Daten auch hätten aussehen können !Damit können statistische Unsicherheiten ohne Zusatzannahmen aus den beobachten Daten bestimmt werden.
Ziehen vieler Stichproben aus der beobachteten Stichprobe mit Zurücklegen
manche Werte der ursprünglichen Stichprobe kommen gar nicht vor, andere mehrmals – das ist genau so gewollt !
Bootstrapping ist eine Resampling-Methode
Beispiele solcher „zweifelhaften“ Zusatzannahmen:
- Punkteverteilung bei Prüfungen ist gaußverteilt
- Klausurnoten sind gaußverteilt
- Zahl der Beobachtungen eines seltenen Phänomens ist so groß, dass von einer Gaußverteilung ausgegangen werden kann. - Gauß ist immer gut, wenn man sonst nichts weiß
Hauptanwendung: Parameterfreie Hypothesentests in Wirtschafts- und Sozialwissenschaften
Beispiel Bootstrapping
Bei geringem Stichprobenumfang könnte man alle möglichen Kombinationen untersuchen,
Bei großen Stichproben wählt man eine sehr große Anzahl zufällig ausgewählter neuer Proben durch Ziehen mit Zurücklegen aus den Originaldaten
1 3
5 26Origialdaten
35
1
1
2 Beispiel einer neu erzeugten Bootstrap-Probe
52
1
5
6ein weiteres Beispiel
5 5 55 5
auch möglich, aber extrem selten
Beispiel Bootstrapping in python
python:
t_bs = numpy.random.choice(t, size=n)
erzeugt aus der beobachteten Strichprobe t durch Ziehen mit Zurücklegen („resampling with replacement“) eine neue Stichprobenvariante
Bootstrapping ist sehr einfach zu realisieren:
Original-Stichprobe {xi }, i =1, …, l der Länge l :
ziehe zufällig l Indizes k ϵ { 1, …, l }
{ xk } ist weitere Stichprobe
typischerweise werden einige Tausend solcher Resamplings erzeugt und statistisch ausgewertet.
Bootstrapping am Beispiel
Beispiel von eben: fünf aus der vorderen Stichprobe durch Resampling gewonnene Varianten der Stichprobe
Problem: Ausläufer der Verteilung sind meist unterrepräsentiert !
bootstrapIllu.py
Beispiel: Konfidenzintervalle für Mittelwert
Beispiel: 30 gaußverteilte Zahlen
10 000 Bootstrap-Samples
Vergleich: Bootstrap-Verteilung mit Gauß-Verteilung um den Mittelwert der Orignaldaten bootstrap.py
Fazit:
Bootstrapping reproduziertdas mit der „klassischen“Methode bestimmte Konfidenzintervall ± μ 1 (68%). σ
Zufallszahlen per Software
Zufallszahlen in python
Das Paket numpy.random stellt zahlreiche Verteilungsdichten zur Verfügung,
hier eine Auswahl: binomial(n, p[, size])
chisquare(df[, size])
exponential([scale, size])
lognormal([mean, sigma, size])
multinomial(n, pvals[, size])
multivariate_normal(mean, cov[, size])
normal([loc, scale, size])
poisson([lam, size])
power(a[, size])
standard_cauchy([size])
standard_exponential([size])
standard_normal([size])
standard_t(df[, size])
triangular(left, mode, right[, size])
uniform([low, high, size])
http://docs.scipy.org/doc/numpy/reference/routines.random.html
Zufallszahlen in Root
Root-Klasse TRandom zur Erzeugung von Zufallszahlen
– einfacher, linear kongruenter Generator mit Periodenlänge 109
– schnell – niedrigste Bits nicht unkorreliert ! Daher nicht in statistischen Studien verwenden !
Statt dessen TRandom1 ( RANLUX-Algorithmus, Periodenlänge ~10171, langsam)
TRandom2 ( Periodenlänge ~1025, schnell)
TRandom3 ( Mersenne-Twister Alg., Periodenlänge ~10600, akzeptabel schnell)
verwenden !
Methoden liefern Zufallszahlen gemäß Exp(tau) Integer(imax) Gaus(mean,sigma) Rndm() Uniform(x1) Landau(mpv,sigma) Poisson(mean) Binomial(ntot,prob) und viele mehr
Zufallszahlen in Root (2)
Globaler Zeiger TRandom *gRandom in Root initialisiert Sehr nützlich, um immer die gleiche Folge von Zufallszahlen innherhalb eines Root-Programms zu verwenden.
// TRandom durch TRandom3 ersetzen gRandom = new TRandom3(seed);
Man kann auch auch einen eigenen (lokalen) Generator initialisieren: TRandom3 *myrandom=new TRandom3(seed);
Methode SetSeed(UInt_t seed=0) zur Initialisierung seed=0: Systemuhr zur Initialisierung (jede Zahlenfolge anders) seed !=0: feste Zahlenfolge, abhängig vom Wert von seed
Zufallszahlen in Root (3)
Root-Klassen enthalten bequeme Möglichkeit, Zufallszahlen zu erzeugen, die gemäß einer FunktionTF1, TF2 oder
einem Histogramm TH1, TH2 verteilt sind: Methoden GetRandom() für TH1, TF1 GetRandom2() für TH2, TF2 GetRandom3() für TH3, TF2
Achtung: für Funktionen TFi werden die Zufallszahlen ebenfalls über Histogramme mit einer Anzahl von Punkten fNpx erzeugt.
Beispiel: simuliertes Higgs-Boson in Proton-Proton - Kollisionen
Can you see the Higgs?
MC angewandt in allen Berechnungsschritten:
- Wechselwirkung der Partonen
- Parton-Schauer
- Hadronisierung
- Wechselwirkungen im Detektor
- Detektor-Antwort
- Datenrekonstruktion
- statistische Datenanalyse