Here is the song “Let it go” from the Disney movie “Frozen” performed by Idina Menzel. This is not “classical music” per se, although there is a long tradition of classical music in films. However, the real reason I picked it is because it may be the first and only use of the word “fractal” in a pop song.
Month: June 2015
Sampling from a probability distribution
When simulating any system with randomness, sampling from a probability distribution is necessary. Usually, you’ll just need to sample from a normal or uniform distribution and thus can use a built-in random number generator. However, for the time when a built-in function does not exist for your distribution, here’s a simple algorithm.
Let’s say you have some probability density function (PDF) on some domain and you want to generate a set of numbers that follows this probability law. This is actually very simple to do although those new to the field may not know how. Generally, any programming language or environment has a built-in random number generator for real numbers (up to machine precision) between 0 and 1. Thus, what you want to do is to find a way to transform these random numbers, which are uniformly distributed on the domain to the random numbers you want. The first thing to notice is that the cumulative distribution function (CDF) for your PDF, is a function that ranges over the interval , since it is a probability. Thus, the algorithm is: 1) generate a random number between o and 1, and 2) plug it into the inverse of . The numbers you get out satisfy your distribution (i.e. ).
If you’re lucky enough to have a closed form expression of the inverse of the CDF then you can just plug the random numbers directly into your function, otherwise you have to do a little more work. If you don’t have a closed form expression for the CDF then you can just solve the equation for . Newton’s method will generally converge very quickly. You just loop over the command x = x – (P(x)-r)/rho(x) until you reach the tolerance you want. If you don’t have a closed form expression of the CDF then the simplest way is construct the CDF numerically by computing the N dimensional vector , for some discretization parameter such that . If the PDF is defined on the entire real line then you’ll have to decide on what you want the minimum and maximum (through ) to be. If the distribution has thin tails, then you just need to go out until the probability is smaller than your desired error tolerance. You then find the index such that is closest to (i.e. in Julia you could use findmin(abs(v[j]-r))) and your random number is .
Here is why the algorithm works. What we are doing is transforming the PDF of , which we can call , to the desired PDF for . The transformation we use is . Thus, or . Now, is just 1 on the interval and is the PDF of as expected. Thus, inverting the CDF for uniform random numbers always gives you a new set of random numbers that satisfies the new PDF. Trivial perhaps, but really useful.
Erratum: 2019-04-05. It was pointed out to me that my algorithm involving direct summation of the CDF had some errors. I hope they have now been corrected.
Selection of the week
American violinist Rachel Barton Pine playing Pietro Locatelli’s Sonata Op 6 No 12 for solo violin. This piece was composed in 1737!
Here is another side of Rachel Barton Pine playing with her heavy metal band Earthen Grave
Selection of the week
Joaquin Rodrigo’s Concierto de Aranjuez played by guitarist John Williams and the BBC Symphony Orchestra conducted by Paul Daniel at the BBC Proms 2005.
Selection of the Week
Hungarian pianist András Schiff plays a lost piece by Johannes Brahms composed in Göttingen in 1853.
Christopher Hogwood and Schiff discuss the piece here.
Talk in Göttingen
I’m currently in Göttingen, Germany at the Bernstein Sparks Workshop: Beyond mean field theory in the neurosciences, a topic near and dear to my heart. The slides for my talk are here. Of course no trip to Göttingen would be complete without a visit to Gauss’s grave and Max Born’s house. Photos below.