Skip to content

Instantly share code, notes, and snippets.

@tpogden

tpogden/README.md

Last active April 3, 2016 18:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tpogden/f6bab858b9db154aae8d80979623baed to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tpogden/f6bab858b9db154aae8d80979623baed to your computer and use it in GitHub Desktop.
Download ZIP
Monte Carlo Integration 1
Raw
README.md

Monte Carlo integration of the function $f(x) = x^2$ on the interval $\left[ 0, 1 \right]$ on $\mathbb{R}$. The correct result is $1/3$. How close is the numerically computed result?

We sample $N = 1000$ points on the plane $(x,y) \in ([0,1], [0,1])$ and define an acceptance function

$$ A(x,y) = \begin{cases} 1 & \text{if} ~ y \leq f(x) \\ 0 & \text{else} \end{cases} $$

then we approximate

$$ I = \int_a^b {f(x) ~\mathrm{d}x } $$

where in this case $a = 0$ and $b = 1$, as

$$ I = \frac{(b - a)}{N} \sum_i^N A(x_i). $$

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<html>
<head>
<title>MC Integration</title>
<script src="http://d3js.org/d3.v3.min.js"></script>
<style>
/* Colors
White: rgba(245,243,242,1);
Black: rgba(53,48,47,1);
Red: rgba(189,54,19,1);
Grey: rgba(113,107,105,1);
Light: rgba(208,199,198,1);
*/
body {
font-family: "Helvetica", sans-serif;
font-size: 10px;
}
.axis {
font: 10px sans-serif;
}
.axis path,
.axis line {
fill: none;
stroke: #000;
shape-rendering: crispEdges;
}
.point {
fill: rgba(189,54,19,1);
stroke: white;
}
.point-fade {
fill: rgba(208,199,198,0.5);
stroke: white;
}
.path {
fill: none;
stroke: rgba(113,107,105,1);
stroke-width: 2px;
}
</style>
<body>
<script>
(function() {
// Function to integrate
function f(x) { return x*x; }
// function f(x) { return Math.sqrt(1 - x*x); }
var num_points = 1000;
var num_path_steps = 100;
var path_step = 1.0/num_path_steps;
var drawDelay = 1000;
var minDrawDelay = 1;
var fadeDur = 500;
var margin = {top: 20, right: 20, bottom: 40, left: 40},
width = 944 - margin.left - margin.right, // was 512
height = 480 - margin.top - margin.bottom;
var x = d3.scale.linear()
.range([0, width])
.domain([0, 1]);
var y = d3.scale.linear()
.range([height, 0])
.domain([0, 1]);
var xAxis = d3.svg.axis()
.scale(x)
.orient("bottom");
var yAxis = d3.svg.axis()
.scale(y)
.orient("left");
// Draw SVG
var svg = d3.select("body").append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
// X axis
svg.append("g")
.attr("class", "x axis")
.attr("transform", "translate(0," + height + ")")
.call(xAxis);
// Y axis
svg.append("g")
.attr("class", "y axis")
.call(yAxis);
// Path
path_xy = d3.range(num_path_steps+1)
.map(function(i) { return [i*path_step, f(i*path_step)]; });
// Accessor function
var lineFunction = d3.svg.line()
.x(function(d) { return x(d[0]); })
.y(function(d) { return y(d[1]); })
.interpolate("cardinal");
svg.append("path")
.datum(path_xy)
.attr("class", "path")
.attr("d", lineFunction);
var data_xy = d3.range(num_points)
.map(function() { return [Math.random(), Math.random()]; });
var data_under = d3.range(num_points)
.map(function(i) {
return data_xy[i][1] < f(data_xy[i][0]); });
// Sum values in an array via reduce()
var sum = data_under.reduce((a, b) => a + b);
console.log(sum);
var success = 0;
// Walker number in top right
var trialsText = svg.append("text")
.attr("id", "trials-text")
.attr("class", "svg-small-text")
.style("text-anchor", "start")
.attr("x", 20)
.attr("y", 4);
// Walker number in top right
var intText = svg.append("text")
.attr("id", "int-text")
.attr("class", "svg-small-text")
.style("text-anchor", "start")
.attr("x", 20)
.attr("y", 24);
function drawPoints(data_xy, data_under, j) {
setTimeout(function() {
d3.select('#trials-text').text("Trials: " + (j+1));
d3.select('#int-text').text("Integral: " + (success/(j+1)).toFixed(4));
// console.log("Point:" + j);
// console.log("Under?" + data_under[j]);
// console.log("delay " + drawDelay);
var circle = svg.append("svg:circle")
.transition()
.ease("bounce")
.attr("class", "point")
.attr("cx", function () { return x(data_xy[j][0]); } )
.attr("cy", function () { return y(data_xy[j][1]); } )
.attr("r", 8);
if (data_under[j]) {
circle.transition()
.duration(fadeDur)
.attr("r", 4);
success++;
}
else {
circle.transition()
.duration(fadeDur)
.style("opacity", 0.25)
.attr("r", 4);
}
j++;
if (j < data_xy.length) {
drawPoints(data_xy, data_under, j);
}
// Accelerate by shrinking drawDelay on each step.
drawDelay = Math.max(minDrawDelay, Math.floor(drawDelay*0.95));
}, drawDelay);
}
drawPoints(data_xy, data_under, 0);
})();
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment