16

I don't think it's fair to compare Riemann Integration to Monte Carlo. First off, using the usual Riemann sums for integration is a terrible way of computing integrals, especially those that oscillate wildly or are just plain naughty in certain areas. Just look at $d=1$. Riemann integration is $O(1/n)$ whereas the Trapezoid rule gives $O(1/n^2)$, assuming ...


11

Well I guess you answered the question yourself, minus the intuitive explanation. If you do accept that the "Reimann integration" error will be like O($ {} \frac{1}{n^{1/d}} $) and the MC error like $ {} \frac{C}{\sqrt{n}} $, then it's obvious that MC will in general give lower errors for $ \mathbb d > 2$. The only thing that I suppose might still ...


9

What you did is just a Monte Carlo scheme to compute the integral $$\int_{D} x^2+y^2 dxdy$$ with $D=\{(x,y)| x^2+y^2 < 1\}$, which defines a quarter of a disk with unit radius in the XY plane. But this integral is also easily computed in polar coordinates as $$\int_{\theta=0}^{\theta=\pi/2}\int_{r=0}^{r=1} r^3drd\theta = \frac{\pi}{8} \; .$$ The ...


8

We are trying to use Monte Carlo Simulation to find: $$\displaystyle \int_0^\infty \dfrac 34 x^4e^{-x^{3/4}}\,dx$$ As you have discovered, the infinite limits are problematic. We can do several things to overcome this Approach 1: A naive approach is to plot the function given that it has a decaying exponential which tends to zero very quickly. If we plot ...


7

In general, there is (as far as I know) only one universally applicable sampling method. It goes by the name of "conditional distribution method", "conditional inverse method" or "conditional sampling". Depending on the specific type of copula, other simulation methods can be available. 1) Conditional distribution method I'll limit myself to the 2D case, ...


6

The algorithm for the Monte-Carlo approach is the following. Generate $n$ uniform random points $x_n \in (0, 1)$ Set $\displaystyle I = \dfrac{1}{n} \sum_{i = 1}^n x_n^2$ We can then compare the error from the exact value versus the result from the Monte Carlo approach. Depending on how we coded up the Monte-Carlo Method, we can also estimate the error. ...


6

Strictly speaking, MCMC means constructing a Markov chain which has some desired property (usually either a prespecified equilibrium distribution or a prespecified expectation) and then numerically drawing samples from it. If you are given a Markov chain it is really just called Monte Carlo simulation. Anyway, at each fixed time $t$, the value of the chain ...


5

An uniform distribution on a sphere can be calculated like this : $\theta_0 = 2\pi \text{Rand}()$ $\theta_1 = \arccos( 1- 2 \text{Rand}())$ $x = R \sin(\theta_0)\sin(\theta_1)$ $y = R \sin(\theta_0)\cos(\theta_1)$ $z = R \sin(\theta_1)$ Source : http://mathproofs.blogspot.fr/2005/04/uniform-random-distribution-on-sphere.html Another approach that may be ...


5

(This implements ShawnD's answer to the question you link to). We can write down a recurrence for $a_n$: The probability that after $n$ spins we have not seen 5 consecutive reds, and the last spin was not red. $b_n$: The probability that after $n$ spins we have not seen 5 consecutive reds, and the sequence so far ends with one red. $c_n$: The probability ...


5

The average of a function on an interval $[a,b]$ is $$\frac{1}{b-a} \int_a^b f(x) \ dx$$ but here $b-a=1$. So $ \int_0^1 f(x) \ dx$ is indeed the average of $f$ on $[0,1]$.


4

As you say, one primary reason to choose an MC method is precisely that you don't use the same numbers of points. That said, we assume we must use $n$ samples. Your essential question is "does choosing $n$ points randomly do better or worse than putting them on a grid?" The answer is: it depends. On two key things. What sort of function are you integrating?...


4

The solution below assumes that we know how to take $r$-th roots, where $r$ is rational. I do not consider it a good solution. Use the obvious Monte Carlo estimation of $\int_1^3 \frac{dx}{x}$ to estimate $\ln 3$. Call this estimate $r$. Then $\ln 3\approx r$, and therefore $3\approx e^r$. Now calculate $3^{1/r}$.


4

I suspect the intent is for $f(x)$ to be a probability distribution function, a CDF, or some other function that is always between $0$ and $1$. If that constraint is added, then the function $I(x)$ just gives you the area under the curve $f(x)$ from $0$ to $x$, and that area is contained in the box bounded by $X=(0,x)$ and $Y=(0,1)$. If you then pick a ...


4

In my opinion, the tricky bit is to figure out a way of sampling the space of walks that you are interested in. Luckily, the problem is a classic one in polymer physics (e.g. modelling a 2d ideal polymer on a square lattice between fixed points), with an added constraint. Well, actually the constraints are two: the lengths of the segments in both ...


4

This is a very good question. For one-dimensional integrals, there are two ways we could approach it. Method 1: This is the approach in the other link you listed. Pick $n$ randomly distributed points $x_1, x_2, \ldots, x_n$ in the interval $a \le x \le b$. Determine the average value of the function $\displaystyle f_{avg} = \dfrac{1}{n} \sum_{i = 1}^n f(x_i)...


4

I don't know what you mean by a theoretical confidence interval, perhaps a confidence interval where you use the value of $\sigma$ which is known in advance? As for the empirical confidence interval, that would be $$\left (\overline{X}-\frac{t_{N,\alpha} S}{\sqrt{N}},\overline{X}+\frac{t_{N,\alpha} S}{\sqrt{N}} \right )$$ where $\overline{X}$ is the sample ...


4

You have an incorrect statement in your summation: you should have $$\displaystyle W_t - W_s = \sqrt{\Delta t} \cdot \sum_{n = 1+s/\Delta t}^{t/\Delta t} Z_n$$ and the variance of this is $$\Delta t \cdot \dfrac{t-s}{\Delta t} = t-s$$ as you would hope


4

Here is a function that will give you a vector of points uniformly distributed over the required triangular region: function [rv]=RandTri(m) % function to generate an output array of M x,y coordinates uniformly % distributed over the upper triangle within the unit square rv=rand(2,m); rv1t=rv(1,:)+(rv(2,:)<rv(1,:)).*(-rv(1,:)+rv(2,:)); rv(2,:)=rv(...


4

What is the correct way to interpret the code I have written? Your program correctly simulates the following probability (if you divide your first output by the number of samples, to obtain the relative frequency): $$\begin{align} &P(\{X_4>X_3\}\cap\{X_2>X_3\}\cap\{X_3>0.1\})\\ &=\int_{-\infty}^\infty P(\{X_4>X_3\}\cap\{X_2>X_3\}\cap\{...


4

For very large $n$, as in a simulation, a reasonable 95% confidence interval for the estimate $\hat p = k/n$ of the proportion of the points inside the circle is of the form $$\hat p \pm 1.96\sqrt{\frac{\hat p(1-\hat p)}{n}}.$$ So the approximate margin of simulation error is $1.96\sqrt{\frac{\hat p(1-\hat p)}{n}}.$ We have $Var(\hat p) = Var(k/n) = (1/n^...


4

Your region of integration is a right triangle that is half of the square $[0,1]\times [0,1]$ below the line $y=x$. As such you should have $y \in [0,x]$. However, you should not take $y=rand*x$ as that will have points much more densely packed for small $x$. You should just throw random numbers for each of $x$ and $y$ then throw out any where $y \gt x$.


4

Your program looks fine except that there's too much indentation before samples.append(new_t). That line shouldn't be conditional on the if statement; a sample is generated regardless of whether you accept or reject. By the way, you're using ”performance“ in an unorthodox way. In this context it's usually used to mean speed; judging from the ...


3

Five simple contenders: 1. Arc-Sine(0,1) distribution Draw your pseudo-random samples from an Arc-Sine(0,1) distribution, with pdf: $$ f(x) = \frac{1}{\pi \sqrt{1-x} \sqrt{x}}$$ which is nested by a $Beta(\frac12,\frac12)$ distribution. Here is a plot of the pdf: 2. Semi-circle (up) $$f(x) = 2 - \frac{8 \sqrt{(1-x)x}}{\pi}$$ 3. U-quadratic $$f(x) = 3(...


3

I should be able to offer some insight here, at least for the Propp-Wilson algorithm, as I studied it for my dissertation. "Coupling" is an important concept here. This is, I think, where the whole "share a single random number generator" statement comes from. To answer your questions: Do "several Markov chains ... share a single random-number generator" ...


3

This is somewhat reminiscent of the "Knapsack problem". As we know, it is NP-complete, so no algorithm exists to solve it fast. I am not going to try to prove that this problem is NP-complete, but it certainly looks that way. You can however solve it in exponential time like this: Generate all combinations (this will be $n_A * n_B * \cdots * n_F$ ...


3

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\...


3

The performance of the Metropolis method depends heavily on the class of trial Metropolis steps considered. (In this 1-D case, on the step size among which you choose your trial step.) If the step size is very large, the Metropolis method behaves like the accept-reject method. If the step size is too small, then you run into the problem of long correlation ...


3

I'll show you a different example, from which you should hopefully be able to work out your problem. I'm going to approximate the area of a circle of radius 1. Firstly, my $x$ and $y$ coordinates will range from -1 to 1. n=10000; x=(1-(-1))*rand(n,1)+(-1); y=(1-(-1))*rand(n,1)+(-1); Now one of these points $(x,y)$ is inside the circle if the distance from ...


Only top voted, non community-wiki answers of a minimum length are eligible