3 ms·

"Simulation" in this case is just numeric integration the hard way, even though there's a closed form solution. This is a calculus problem, not a programming p

by adamtj 12y ago

"Simulation" in this case is just numeric integration the hard way, even though there's a closed form solution. This is a calculus problem, not a programming problem. After you solve the real problem, the programming is trivial. If you don't solve the real problem, you can't really be sure your simulation gives you the correct answer. Exponential decay is a lot like compound interest. Simulating this problem is like computing interest by compounding yearly instead of continuously. It's not hard for those methods to differ by a factor of two or ten or even more. You can't really know if your simulation will be affected without doing the math anyway.

Florin_Andrei 12y ago
Well, when computing power is plentiful, sometimes it's easier to just simulate the heck out of it. (shrug) Back in the day, I was curious about the ratio between the volume of an N-dimensional sphere, divided by the volume of the N-dimensional cube that contains it, as a function of N. I'm sure there might be an exact solution somewhere (it's basically the volume of the N-sphere of radius 0.5) but I was too lazy to look it up. Instead, I just did a trivial one-page Monte Carlo shoot-em-up with a lot of points. It converged quickly to a good estimate. For the curious, as N goes up, the volume of the N-sphere is a smaller and smaller fraction of the volume of the N-cube containing it. It kinda blew my mind when I saw the result, but then it started to make sense (in higher dimensions there's more ways for space to be "wasted" in the corners).
- gjm11 12y ago
  Yup, there's an exact solution. It turns out that the volume of the n-dimensional unit ball is pi^(n/2) / (n/2)!. (The factorial function generalizes to numbers that aren't integers. For half-integers you get a rational number times sqrt(pi). E.g., if n=3 then we need (3/2)! which happens to equal 3/4.sqrt(pi), so the volume is 4/3.pi.) So for large n we can use Stirling's approximation. To make the formulas a little shorter I'll write m=n/2. Then the volume of the unit n-ball is V(n) = pi^m/m! ~ pi^m (e/m)^m 1/sqrt(2.pi.m) whereas the volume of the smallest n-cube containing that ball is 2^n, so the ratio is R(n) ~ (pi.e/2m)^m / sqrt(2.pi.m) where, remember, m=n/2. Actually, at this point maybe it's nicer to put things back in terms of n: R(n) ~ sqrt[(pi.e/n)^n/pi.n] When n is large, you should see this as R(n) ~ sqrt[(..../n)^n.....] where the "...."s are the less important bits. So for large n this is going to get small. Concrete not-so-large-n example: let's take n=10. Then R(10) ~= sqrt((pi.e/10)^10/10pi) which happens to be about 0.081. That's pretty accurate -- the exact answer is pi^5/3840, which is about 0.0797. So if you fit a 10-ball snugly inside a 10-cube it'll take up about 1/12 of the space. What if we crank the dimension up? With n=100 the ratio is about 2x10^-55. (A naive Monte Carlo simulation will be unable to distinguish this from zero.) So if you do the ball-inside-cube thing in 100 dimensions, the ball occupies less than one billion-billion-billion-billion-billion-billionth of the volume of the cube. High-dimensional cubes are really, really spiky.
  - mturmon 12y ago
    Totally true. It's a useful heuristic approximation that n! ~ (n/e)^n That is, multiplying the "n" factors from 1...n is close to multiplying (n/e) upon itself "n" times. The actual Stirling approximation is just a sqrt(2 pi n) bigger than the above, and usually it's fine to throw that away (as above).
JHonaker 12y ago
The point of the simulation portion was really to just explain that even though you know almost nothing about the theoretical behavior (from a probabilistic point of view) you can just apply what happens at each time point over and over to get an idea of how it behaves. For example, using basically the same process of building from a base case to simulating a system, a few months ago, I was interested in determining roughly how many packs of cards from a certain game I would need to open to be reasonably sure I would have all card in the set. I took some probabilities that I'd gotten from other people opening hundreds of packs, and used that to simulate opening one pack. I then performed about a thousand runs of opening packs until I got every card and recorded the number of packs it took each time. In the end I got a really nice normal distribution of the estimate of the mean number of packs it would take to get every card (hooray for the central limit theorem!).
im2w1l 12y ago
Discrete time and continuous time exponential models can be converted from and to each other, so that they will agree anytime the discrete time model is defined.

by adamtj 12y ago

Florin_Andrei 12y ago

Well, when computing power is plentiful, sometimes it's easier to just simulate the heck out of it. (shrug) Back in the day, I was curious about the ratio between the volume of an N-dimensional sphere, divided by the volume of the N-dimensional cube that contains it, as a function of N. I'm sure there might be an exact solution somewhere (it's basically the volume of the N-sphere of radius 0.5) but I was too lazy to look it up. Instead, I just did a trivial one-page Monte Carlo shoot-em-up with a lot of points. It converged quickly to a good estimate. For the curious, as N goes up, the volume of the N-sphere is a smaller and smaller fraction of the volume of the N-cube containing it. It kinda blew my mind when I saw the result, but then it started to make sense (in higher dimensions there's more ways for space to be "wasted" in the corners).

gjm11 12y ago
Yup, there's an exact solution. It turns out that the volume of the n-dimensional unit ball is pi^(n/2) / (n/2)!. (The factorial function generalizes to numbers that aren't integers. For half-integers you get a rational number times sqrt(pi). E.g., if n=3 then we need (3/2)! which happens to equal 3/4.sqrt(pi), so the volume is 4/3.pi.) So for large n we can use Stirling's approximation. To make the formulas a little shorter I'll write m=n/2. Then the volume of the unit n-ball is V(n) = pi^m/m! ~ pi^m (e/m)^m 1/sqrt(2.pi.m) whereas the volume of the smallest n-cube containing that ball is 2^n, so the ratio is R(n) ~ (pi.e/2m)^m / sqrt(2.pi.m) where, remember, m=n/2. Actually, at this point maybe it's nicer to put things back in terms of n: R(n) ~ sqrt[(pi.e/n)^n/pi.n] When n is large, you should see this as R(n) ~ sqrt[(..../n)^n.....] where the "...."s are the less important bits. So for large n this is going to get small. Concrete not-so-large-n example: let's take n=10. Then R(10) ~= sqrt((pi.e/10)^10/10pi) which happens to be about 0.081. That's pretty accurate -- the exact answer is pi^5/3840, which is about 0.0797. So if you fit a 10-ball snugly inside a 10-cube it'll take up about 1/12 of the space. What if we crank the dimension up? With n=100 the ratio is about 2x10^-55. (A naive Monte Carlo simulation will be unable to distinguish this from zero.) So if you do the ball-inside-cube thing in 100 dimensions, the ball occupies less than one billion-billion-billion-billion-billion-billionth of the volume of the cube. High-dimensional cubes are really, really spiky.
- mturmon 12y ago
  Totally true. It's a useful heuristic approximation that n! ~ (n/e)^n That is, multiplying the "n" factors from 1...n is close to multiplying (n/e) upon itself "n" times. The actual Stirling approximation is just a sqrt(2 pi n) bigger than the above, and usually it's fine to throw that away (as above).

JHonaker 12y ago

The point of the simulation portion was really to just explain that even though you know almost nothing about the theoretical behavior (from a probabilistic point of view) you can just apply what happens at each time point over and over to get an idea of how it behaves. For example, using basically the same process of building from a base case to simulating a system, a few months ago, I was interested in determining roughly how many packs of cards from a certain game I would need to open to be reasonably sure I would have all card in the set. I took some probabilities that I'd gotten from other people opening hundreds of packs, and used that to simulate opening one pack. I then performed about a thousand runs of opening packs until I got every card and recorded the number of packs it took each time. In the end I got a really nice normal distribution of the estimate of the mean number of packs it would take to get every card (hooray for the central limit theorem!).

im2w1l 12y ago

Discrete time and continuous time exponential models can be converted from and to each other, so that they will agree anytime the discrete time model is defined.