Skip to content

Instantly share code, notes, and snippets.

@sathomas

sathomas/README.md

Last active August 27, 2016 23:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sathomas/f6bc9b3dbf26146a1c3082fed18413a3 to your computer and use it in GitHub Desktop.
Save sathomas/f6bc9b3dbf26146a1c3082fed18413a3 to your computer and use it in GitHub Desktop.
Download ZIP
Variations on a Random Walk
Raw
README.md

Can seemingly trivial differences at a small scale have noticeable effects at larger scales? Certainly, as we've learned from chaos theory. This visualization considers another perspective on the same question. It shows the results of three variations of a random walk. The difference between the variations might seem insignificant, yet the resulting large-scale behavior is not at all the same.

Raw
README2.md

Can seemingly trivial differences at a small scale have noticeable effects at larger scales? Certainly, as we've learned from chaos theory. This visualization considers another perspective on the same question. It shows the results of three variations of a random walk. The difference between the variations might seem insignificant, yet the resulting large-scale behavior is not at all the same.

Simulating a Random Walk

The visualization simulates three variations of a random walk. All of the variations have much in common:

  1. A particle starts at the origin (x=0, y=0) and proceeds for 25,000 steps.

  2. At each step, the particle chooses a random direction; all directions are equally probable.

  3. At each step, the particle also chooses a distance to move in the selected direction. The average (mean) value for that distance is the same (0.1) for all variations.

  4. The particle moves to the new position determined by the direction and distance, and the simulation advances to the next step.

  5. The simulation keeps track of how far the particle has moved from its starting position; it records the furthest position that the particle reaches during the 25,000 steps. (Note that this is not the same as the position in which the particle ends the simulation.)

  6. The simulation repeats 1,000 times for all three variations.

The only difference between the variations is how the particle chooses a distance for each step.

  • In the "Constant" variation, the particle always chooses the same distance, 0.1. The mean value of this choice is, of course, 0.1.

  • In the "Exponential" variation, the particle chooses a random distance from an exponential distribution with scale 0.1, which has a mean value of 0.1.

  • In the "Power Law" variation, the particle chooses a random distance from a Pareto distribution with shape 2 and scale 0.05. This distribution also has a mean value of 0.1.

In all variations, the average value for the step increment is the same; however, as the chart shows, the results can differ significantly.

Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Variations on a Random Walk</title>
<script src="https://d3js.org/d3.v3.min.js"></script>
<link href='http://fonts.googleapis.com/css?family=Varela'
rel='stylesheet' type='text/css'>
<style>
body {
color: #444;
font-family: Varela,sans-serif;
}
.axis {
font-size: 13px;
}
.axis path, .axis line {
fill: none;
stroke: #888;
shape-rendering: crispEdges;
}
.legend {
font-size: 14px;
}
.fixed.legend { fill: #ca0000; }
.exponential.legend { fill: #7ebd00; }
.power.legend { fill: #007979; }
circle {
fill-opacity: 1;
-webkit-transition: all 500ms linear;
-moz-transition: all 500ms linear;
-ms-transition: all 500ms linear;
-o-transition: all 500ms linear;
transition: all 500ms linear;
}
circle.fixed { fill: #ca0000; }
circle.exponential { fill: #7ebd00; }
circle.power { fill: #007979; }
.fixed circle.exponential, .fixed circle.power,
.exponential circle.fixed, .exponential circle.power,
.power circle.fixed, .power circle.exponential {
fill-opacity: 0;
}
ellipse {
fill-opacity: 0;
stroke-opacity: 0;
-webkit-transition: all 500ms linear;
-moz-transition: all 500ms linear;
-ms-transition: all 500ms linear;
-o-transition: all 500ms linear;
transition: all 500ms linear;
}
ellipse.fixed { stroke: #ca0000; }
ellipse.exponential { stroke: #7ebd00; }
ellipse.power { stroke: #007979; }
.fixed ellipse.fixed,
.exponential ellipse.exponential,
.power ellipse.power {
stroke-opacity: 1;
}
.notes {
font-size: 13px;
-webkit-transition: all 500ms linear;
-moz-transition: all 500ms linear;
-ms-transition: all 500ms linear;
-o-transition: all 500ms linear;
transition: all 500ms linear;
}
.notes.fixed, .notes.exponential, .notes.power {
fill-opacity: 0;
}
.fixed .notes, .exponential .notes, .power .notes {
fill-opacity: 0;
}
.fixed .notes.fixed, .exponential .notes.exponential, .power .notes.power {
fill-opacity: 1;
}
.notes.fixed { fill: #ca0000; }
.notes.exponential { fill: #7ebd00; }
.notes.power { fill: #007979; }
</style>
</head>
<body>
<div id="graph"></div>
<script>
// Standard D3.js set up
var margin = {top: 40, right: 40, bottom: 40, left: 40},
width = 636 - margin.left - margin.right,
height = 476 - margin.top - margin.bottom;
var svg = d3.select("#graph").append("svg")
.attr("height", height + margin.left + margin.right)
.attr("width", width + margin.top + margin.bottom);
var chart = svg.append("g")
.attr("transform",
"translate(" + margin.left + "," + margin.top + ")"
);
// We're going to select parameters to give a
// nice -100 to 100 domain for both scales.
var xScale = d3.scale.linear()
.range([0,width])
.domain([-100, 100]);
var yScale = d3.scale.linear()
.range([height,0])
.domain([-100, 100]);
// Standard axes for x-y scatter plot.
var xAxis = d3.svg.axis()
.scale(xScale)
.orient("bottom");
chart.append("g")
.attr("class", "axis")
.attr("transform", "translate(0," + height + ")")
.call(xAxis);
var yAxis = d3.svg.axis()
.scale(yScale)
.orient("left");
chart.append("g")
.attr("class", "axis")
.call(yAxis);
// Title for the chart.
chart.append("text")
.attr("x", width/2)
.attr("y", 0)
.style("text-anchor", "middle")
.text("Farthest Position Reached");
// Bare bones legend.
chart.append("text")
.classed("legend fixed", true)
.attr("x", width)
.attr("y", 20)
.attr("cursor", "default")
.style("text-anchor", "end")
.text("Constant •")
.on('mouseover', function() { svg.classed('fixed', true); })
.on('mouseout', function() { svg.classed('fixed', false); });
chart.append("text")
.classed("legend exponential", true)
.attr("x", width)
.attr("y", 40)
.attr("cursor", "default")
.style("text-anchor", "end")
.text("Exponential •")
.on('mouseover', function() { svg.classed('exponential', true); })
.on('mouseout', function() { svg.classed('exponential', false); });
chart.append("text")
.classed("legend power", true)
.attr("x", width)
.attr("y", 60)
.attr("cursor", "default")
.style("text-anchor", "end")
.text("Power Law •")
.on('mouseover', function() { svg.classed('power', true); })
.on('mouseout', function() { svg.classed('power', false); });
// Details on hover.
chart.append("text")
.classed("notes", true)
.attr("x", width)
.attr("y", height - 10)
.style("text-anchor", "end")
.text("(hover over legend for details, click anywhere to re-run)");
chart.append("text")
.classed("notes fixed", true)
.attr("x", width/2)
.attr("y", height - 10)
.style("text-anchor", "middle");
chart.append("text")
.classed("notes exponential", true)
.attr("x", width/2)
.attr("y", height - 10)
.style("text-anchor", "middle");
chart.append("text")
.classed("notes power", true)
.attr("x", width/2)
.attr("y", height - 10)
.style("text-anchor", "middle");
// Simulation code - random number generation
// Utilities to generate random numbers
function dexp(scale) {
return -scale * Math.log(Math.random());
};
function dpareto(shape, scale) {
return scale / Math.pow((1 - Math.random()), 1.0 / shape);
};
// Utilities to calculate statistics
function mean(arr) {
return arr.reduce(function(a,b) {return a+b;}, 0)/arr.length;
}
function stdev(arr, arrMean) {
arrMean = arrMean || mean(arr);
return Math.sqrt(mean(arr.map(function(a) {return Math.pow(a - arrMean, 2);})));
}
// Single simulation run. Returns the
// maximum distance reached for a single
// simulation run. Input parameter is
// class of random distribution to use for
// each incremental step distance. Values:
//
// - `fixed`
// - `exponential`
// - `power`
function singleRun(distClass) {
var pt = [0,0],
maxPt = [0,0]
maxDist = 0,
meanStep = 0.1;
for (var i=0; i<25000; i++) {
var radius, theta;
// Choose a direction at random (uniform distribution)
theta = 2 * Math.PI * Math.random(),
// Choose a distance based on distribution but with
// consistent mean
radius = distClass === "power" ? dpareto(2, meanStep/2) :
(distClass === "exponential" ? dexp(meanStep) : meanStep);
// Calculate the new point
pt[0] += radius * Math.cos(theta);
pt[1] += radius * Math.sin(theta);
// How far is the new point from the origin?
var dist = Math.sqrt(Math.pow(pt[0],2) + Math.pow(pt[1],2));
// If new point is farthest, remember it.
if (dist > maxDist) {
maxPt[0] = pt[0];
maxPt[1] = pt[1];
maxDist = dist;
}
}
// Add a point on the chart for the fartheset position
chart.append("circle")
.classed(distClass, true)
.attr("r", 1)
.attr("cx", xScale(maxPt[0]))
.attr("cy", yScale(maxPt[1]));
// Return the distance of the farthest point.
return maxDist;
}
// Full simulation (multiple runs).
function simulate() {
// Remove old results from chart
chart.selectAll('circle, ellipse').remove();
// Keep track of the farthest positions reached
// so we can calculate statistics.
var fixed = [], exponential = [], power = [];
for (var n=0; n<1000; n++) {
fixed[n] = singleRun("fixed");
exponential[n] = singleRun("exponential");
power[n] = singleRun("power")
}
// Calculate summary statistics for each distribution.
var fixedMean = mean(fixed),
fixedStdev = stdev(fixed, fixedMean),
exponentialMean = mean(exponential),
exponentialStdev = stdev(exponential, exponentialMean),
powerMean = mean(power),
powerStdev = stdev(power, powerMean);
// Add ellipses for mean values.
chart.append("ellipse")
.classed("fixed", true)
.attr('rx', xScale(fixedMean) - xScale(0))
.attr('ry', yScale(0) - yScale(fixedMean))
.attr('cx', xScale(0))
.attr('cy', yScale(0));
chart.append("ellipse")
.classed("exponential", true)
.attr('rx', xScale(exponentialMean) - xScale(0))
.attr('ry', yScale(0) - yScale(exponentialMean))
.attr('cx', xScale(0))
.attr('cy', yScale(0));
chart.append("ellipse")
.classed("power", true)
.attr('rx', xScale(powerMean) - xScale(0))
.attr('ry', yScale(0) - yScale(powerMean))
.attr('cx', xScale(0))
.attr('cy', yScale(0));
// Update detailed notes.
chart.select('.notes.fixed')
.text("Constant step increment, farthest distance: μ = " +
fixedMean.toFixed(2) + ", σ = " + fixedStdev.toFixed(2));
chart.select('.notes.exponential')
.text("Exponentially-distributed step increment, farthest distance: μ = " +
exponentialMean.toFixed(2) + ", σ = " + exponentialStdev.toFixed(2));
chart.select('.notes.power')
.text("Power law step increment, farthest distance: μ = " +
powerMean.toFixed(2) + ", σ = " + powerStdev.toFixed(2));
}
d3.select('body').on('click', simulate);
simulate();
</script>
</body>
</html>
Raw
thumbnail.lnk
http://jsdatav.is/img/thumbnails/randomwalk.png
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment