31:T8dd,Fig1 = { const w = Math.min(640, width), h = 200 const margin = {top: 30, right: 20, bottom: 40, left: 35} const svg = d3.select(DOM.svg(w, h)); const data = d3.range(0,30.1,.1).map(n => [n, volume(r, n)]) const x = d3.scaleLinear().domain([0, 30]).range([margin.left, w - margin.right]) const y = d3.scaleLinear().domain(d3.extent(data.map(d => d[1]))).range([h - margin.bottom, margin.top]) const line = d3.line() .x(d => x(d[0])) .y(d => y(d[1])) svg.style("overflow", "visible").style("font-family", "sans-serif").style("font-size", "12px") svg.append("g") .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y).ticks(5)); svg.append("g") .attr("transform", `translate(0,${h - margin.bottom})`) .call(d3.axisBottom(x).ticks(5)); svg.selectAll("g line, g path").attr("stroke", "#aaa") svg.selectAll("g text") .attr("fill", "#aaa") // .style("font-family", '"PT Serif", serif') .style("font-size", "12px") svg.append("path") .datum(data) .attr("fill", "none") .attr("stroke", "black") .attr("stroke-width", 1.5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") .attr("d", line); svg.append("line") .attr("x1", x(n)) .attr("x2", x(n)) .attr("y1", y.range()[0]) .attr("y2", y.range()[1]) .attr("stroke", "steelblue") .attr("stroke-width", 1.5) svg.append("text") .text(`Volume of n-ball of radius ${r}`) .attr("y", "1em") // .attr("font-size", "16px") svg.append("text") .text("Dimensions (n)") .attr("y", h) .attr("dy", "-3px") .attr("x", w - margin.right) // .attr("font-size", "16px") .style("text-anchor", "end") svg.append("text") .text(n) .attr("x", x(n)) .attr("y", h - margin.bottom) .attr("dy", "17.5px") // .style("font-size", "12px") .style("fill", "steelblue") .style("font-weight", "bold") .style("text-anchor", "middle") svg.append("text") .text(volume(r,n).toFixed(2)) .attr("x", margin.left) .attr("dx", "-9px") .attr("y", y(volume(r,n))) .attr("dy", "5px") // .style("font-size", "12px") .style("fill", "steelblue") .style("font-weight", "bold") .style("text-anchor", "end") return svg.node(); }32:T6a8,md`The ${tex`\Gamma`} in the denominator is the [gamma function](http://mathworld.wolfram.com/GammaFunction.html), which generalizes the factorial ${tex`(x-1)!`} to work on non-integer real and complex numbers. (Note that this gives a volume of 1 for 0 dimensions; I’m not sure this has any geometrical interpretation.) In two dimensions the volume equation reduces to the more familiar equation for the area of a circle, ${tex`\pi r ^ 2`}; in three dimensions, the volume of a sphere, ${tex`\frac{4}{3} \pi r ^ 3`}. You may not be used to going higher than that. But “a set of points equidistant from a point” and “a set of points within some distance from a point” can apply to any number of dimensions, even if you can’t quite picture it. The former, the hollow shell, is called a sphere; the latter, i.e. everything within, is called a ball. (“Ball” doesn’t sound very technical, lol!) What you think of as a solid sphere is a “3-ball”; its surface is a “2-sphere”, like you walk the surface of the Earth in two dimensions. Looking again at the equation above, the factorial in the denominator grows extraordinarily fast as dimension increases. That may satisfy you, algebraically. But one way to think about this geometrically is that corners start to dominate. There get to be a lot of corners, and they grow very fast, and the middle sorta stays small. Maybe you can picture this in your mind just going from a circle to a sphere. Or we can flatten out a ball of any dimension into slices, taking a crude uniform sample of five points along each dimension. The first dimension is laid out horizontally, the second vertically, the third horizontally again, and so on.`33:Tda7,Fig2 = { const w = Math.min(width, 640), h = w, dim = Math.floor(dimension); const context = DOM.context2d(w, h, 1); var r = 2 var data = getPoints(dim, r) if(dim % 2 == 0) { var w0 = d3.interpolate(w, w / r / 2.4)(dimension % 1) } else { var w0 = w } var dx = d3.range(3).map(() => 0) for(var i = Math.ceil(dim / 2) - 1; i >= 0; i--) { if(i == Math.ceil(dim / 2) - 1) { dx[i] = w0 / r / 2.4 } else { dx[i] = dx[i+1] / r / 3 } } var dr = dx[0] / 3 context.clearRect(0,0,w,h) context.fillStyle="#000000" context.translate(w/2, h/2) data.forEach(d => { context.fillStyle = distance(d) <= r ? "black" : "#eee" context.beginPath() context.arc( d[0] * dx[0] + (d[2] || 0) * dx[1] + (d[4] || 0) * dx[2], (d[1] || 0) * dx[0] + (d[3] || 0) * dx[1] + (d[5] || 0) * dx[2], dr, 0, 2*Math.PI ) context.fill() }) context.translate(-w/2, -h/2) context.fillStyle = '#000000' context.font = '24px Oswald'; let str = `${dim}-ball` if(dim == 1) str += ' (line)' if(dim == 2) str += ' (circle)' if(dim == 3) str += ' (sphere)' context.fillText(str, 0, 30) context.font = '16px PT Serif' if(dim == 1) { context.textAlign = 'end' context.fillText(`Each circle is a point on the line ⤴`, w - dr, h/2 + dr + 40) context.fillText(`(There are no corners yet! The 1-ball fills the space.)`, w - dr, h/2 + dr + 65) context.textAlign = 'center' context.fillText('–r', w/2 - 2 * dx[0], h/2 - dr - 20) context.fillText('–r / 2', w/2 - 1 * dx[0], h/2 - dr - 20) context.fillText('0', w/2, h/2 - dr - 20) context.fillText('r / 2', w/2 + 1 * dx[0], h/2 - dr - 20) context.fillText('r', w/2 + 2 * dx[0], h/2 - dr - 20) } else if(dim == 2) { context.fillText(`(Just a very low-resolution circle!)`, 0, 55) context.textAlign = 'end' context.fillText(`Gray points are “in the corners”`, w, 100) context.fillText(`Black points are inside the ball`, w, 125) } else if(dim == 3) { context.textAlign = 'center' context.fillText('z = –r', w/2 - 2 * dx[1], h/2 - 3 * dx[0]) context.fillText('z = –r / 2', w/2 - 1 * dx[1], h/2 - 3 * dx[0]) context.fillText('z = 0', w/2, h/2 - 3 * dx[0]) context.fillText('z = r / 2', w/2 + 1 * dx[1], h/2 - 3 * dx[0]) context.fillText('z = r', w/2 + 2 * dx[1], h/2 - 3 * dx[0]) context.fillText('Imagine each square block of points as a slice of the sphere', w/2, h/2 + 4 * dx[0]) context.fillText('(and get ready to imagine another dimension of slices stacked vertically).', w/2, h/2 + 4 * dx[0] + 25) context.fillText('A lot more gray corners already! Just you wait...', w/2, h/2 + 4 * dx[0] + 100) } else if(dim == 4) { context.textAlign = 'center' context.fillText('Now 2D slices are stacked both horizontally and vertically.', w/2, h/2 + 4 * dx[0] + 100) context.fillText('Also, lots more corner. You’re getting the idea.', w/2, h/2 + 4 * dx[0] + 125) } else if(dim == 5) { context.textAlign = 'center' context.fillText('Now we again have five slices, each of which is four dimensions.', w/2, h/2 - 4 * dx[0] - 125) context.fillText('The one in the middle is the 4-ball.', w/2, h/2 - 4 * dx[0] - 100) context.fillText('For r = 1, this would have the maximum volume.', w/2, h/2 + 4 * dx[0] + 100) context.fillText('Let’s go one more...', w/2, h/2 + 4 * dx[0] + 125) } yield context.canvas; }34:T73d,md`The main thing to watch is the ratio of black to gray. It goes down! (Please don’t literally count up the ratio; it’s just an illustrative approximation, the truth being famously irrational.) All the gray is in the circumscribed cube; only the black is in the ball. There’s more and more corner. Less ball. OK. Got it. ${previews([{ path: "@tophtucker/concentration-of-measure", thumbnail: "5557526720f92d9330da01e8b923b23856a87d5cf772dae18b181487f799d9f4", title: "Addendum: Concentration of measure", date: "2020-01-16" }])} Note that the volume goes to zero even thought every point in the ${tex`(n-1)`}-ball is also in the ${tex`n`}-ball. E.g., every point in the circle is just at ${tex`z = 0`} in the sphere, and so on. And yet it eventually goes to zero. This may feel unfair! And indeed, there are still just as many points (i.e., infinite). But their measure is hurt by being infinitesimal along the new axis. A line segment has some length in one dimension, but as soon as you measure in two dimensions it has no area at all! Unfair but true. Each new dimension adds new points — but wherever the length of a ${tex`(n-1)`}-dimensional cross-section along the ${tex`n`}th dimension is less than 1, which is eventually almost everywhere, it will shrink the contribution to the total volume. The cube contains every point where every coordinate is less than one unit from the origin, whereas the ball contains every point where every coordinate _combined_ is less than one unit from the origin. The latter is more restrictive, so the corners of the former stick farther out. In the square circumscribing the unit circle, the vertices are just a bit farther: one unit up, one unit across, take the diagonal, that’s the Pythagorean theorem, square root of 2, about 1.4. It stacks up and up with each additional dimension:` 35:Ta34,Fig3 = { const maxDim = 20 const angle = n => n === 1 ? 0 : Math.asin(1/Math.sqrt(n)) + angle(n-1) const radiansToDegrees = 360 / (2 * Math.PI) const dims = d3.range(maxDim).map(d => d+1) const w = Math.min(640, width), h = 100 const svg = d3.select(DOM.svg(w, h)) .style("overflow", "visible") .style("position", "relative") .style("z-index", "-1"); const line = d3.line().x(d => scale(d[0])).y(d => scale(d[1])) const scale = d3.scaleLinear().range([0,100]) const opacityScale = d3.scaleLinear().domain([0,-2.5]).range([1,0]) const rotateScale = d3.scaleLinear() .domain(dims) .range(dims.map(d => -angle(Math.floor(d)) * radiansToDegrees)) svg.append("text").text("Distance to cube vertex:") .attr("y", "45") .attr("fill", "steelblue") .style("font-family", "sans-serif") .style("font-size", "14px") svg.append("text").text(`Radius of inscribed ${Math.floor(dim)}-ball:`) .attr("y", "75") .style("font-family", "sans-serif") .style("font-size", "14px") svg.append("path") .datum([[0,0], [1,0]]) .attr("d", line) .attr("stroke", "black") .attr("transform", "translate(200, 70)") const g = svg.append("g") .attr("transform", `translate(200, 40) rotate(${rotateScale(dim)})`) dims.forEach(d => { let g2 = g.append("g") .attr("transform", `rotate(${angle(d) * radiansToDegrees})`) g2.append("rect") .attr("width", 12) .attr("height", 12) .attr("x", scale(Math.sqrt(d)) - 12) .attr("opacity", d <= dim - 0.5 ? opacityScale(d - dim + 0.5) : 0) .attr("stroke", "black") .attr("fill", "none") g2.append("path") .datum([[0,0],[Math.sqrt(d),0]]) .attr("d", line) .attr("stroke", d == Math.floor(dim) ? "steelblue" : "black") .attr("stroke-width", d == Math.floor(dim) ? 2 : 1) .attr("opacity", d <= dim ? opacityScale(d - dim) : 0) g2.append("path") .datum([[Math.sqrt(d),0],[Math.sqrt(d),1]]) .attr("d", line) .attr("stroke", "black") .attr("opacity", d <= dim - 0.5 ? opacityScale(d - dim + 0.5) : 0) g2.append("text") .text("r") .attr("x", scale(Math.sqrt(d))) .attr("dx", "5px") .attr("y", scale(0.5)) .attr("opacity", d <= dim - 0.5 ? opacityScale(d - dim + 0.5) : 0) .style("font-style", "italic") if(d === 1) { g2.append("text") .text("r") .attr("x", scale(0.5)) .attr("dy", "-5px") .attr("opacity", d <= dim ? opacityScale(d - dim) : 0) .style("font-style", "italic") } }) return svg.node() }36:T4dc,md`Hopefully this is beginning to feel... obvious, or banal. That means you’re getting it! But I think it’s important to simultaneously hold onto the feeling of initial surprise, for empathy and epistemic calibration. As the corners get really, really far away from the center, people sometimes say high-dimensional cubes are “pointy”, because low-dimensional pointy things have corners far from the center. But also note that the ${tex`n`}-ball is still tangent to every wall of the circumscribing hypercube (visible as the one lone point at the far left, right, top, bottom, etc. of every ${tex`n`}-ball in Fig. 2). Those are the tangent points. And so, people also sometimes feel like, well, if those points touch, but there’s so much corner, then it sorta feels like the _ball_ is pointy in high dimensions. So people throw around “pointy” and “spiky” a lot, even though both the ${tex`n`}-ball and the ${tex`n`}-cube are still convex! We just borrow the intuition from a different kind of more-familiar low-dimensional shape. So e.g. [Michael Nielsen points out](http://cognitivemedium.com/tat/) that the mathematician [Vitali Milman](https://en.wikipedia.org/wiki/Vitali_Milman) likes to draw high-D stuff like this:`37:T914,Fig4 = html`

`38:T449,{ const width = 900, height = 55, svg = d3.select(this || html``); let fn = n => ( t => [ Math.pow(Math.sin(t), n), Math.pow(Math.cos(t), n), ] ) let data = d3.range(3, 20, 0.5) .map(n => fn(n)) .map(fn => d3.range(0, Math.PI/2, 0.1).concat(Math.PI/2).map(t => fn(t))) let path = d3.line() .x(d => d[0]*20) .y(d => d[1]*20) let opacity = d3.scaleLinear() .domain([0,19]) .range([1,0]) .clamp(true) svg.selectAll("g").data(data).enter() .append("g") .attr("transform", (d,i) => `translate(${i * 50},30)`) .each(function(d,i) { d3.range(0,360,90).forEach(t => { d3.select(this).append("path").attr("d", path) .style("fill", "none") .style("stroke", "black") .style("transform", `rotate(${t}deg)`) .style("opacity", opacity(i)) }) }) return svg.node() }39:T5c0,md`## The Median is not the Message I want to emphasize that _this is not trivia_. Granted, you are not gonna be kicking around a lot of ${tex`n`}-balls on the street with the neighborhood kids for ${tex`n`} much bigger than three, but high dimensional geometry is totally relevant to your very own everyday life when the dimensions in question are dimensions of data. The whole reason this initially came up with Colin is that he works on the [PyMC](https://github.com/pymc-devs/pymc3) stats package and these high-D pathologies become overwhelmingly important when you’re trying to model some statistical landscape with like a thousand dimensions. One good illustration of this is that in a high-dimensional multivariate random normal distribution (with identity covariance matrix), most of the mass ends up coming to be found in a sort of donut at some distance from the middle. There’s very little mass in the middle. Of course the origin is still the mean, median, and mode — the problem is that the middle is just so dang small, and there’s _so much space_ as you go a little further out. So if you’re just looking at the distribution of distances from the middle, most are a ways out, and more so the more dimensions you’re in. You can see this begin to happen in the first few dimensions by flattening and collecting the points to look at their distribution of distances from the center, as if swinging them around the origin on a fixed-length arm.`3a:Td1c,Fig5 = { const height = 250, svg = d3.select(this || html``); let n = 3, scale = d3.scaleLinear() .domain([0,4]) .range([0, width/n/2]), mouse = [0,0] function attachData(d) { let points = d3.range(1000).map(() => { let cartesian = [ d3.randomNormal()(), d > 0 ? d3.randomNormal()() : 0, d > 1 ? d3.randomNormal()() : 0 ] return { cartesian, spherical: cartesianToSpherical(cartesian), coords: cartesian } }) let simulation = d3.forceSimulation(points) .force("x", d3.forceX(function(d) { return scale(d.spherical.r); }).strength(1)) .force("y", d3.forceY(0)) .force("collide", d3.forceCollide(1)) .stop(); for (var i = 0; i < 120; ++i) simulation.tick(); return points } if(!this) { let dimEnter = svg.selectAll("g.dimension") .data(d3.range(n).map(attachData)) .enter() .append("g") .attr("class", "dimension") dimEnter.append("line") .attr("y1", 0) .attr("y2", 0) .attr("x1", -width/n/2) .attr("x2", width/n/2) .style("stroke", "#eee") dimEnter.append("text") .text((d,i) => `${i+1}D`) .attr("x", -scale.range()[1]) .attr("y", -scale.range()[1]*.67) .style("font-weight", "bold") svg.append("text").text("avg.") .attr("id", "avgLabel") .style("fill", "#aaa") .attr("y", height/2) .attr("dy", "1em") .attr("opacity", 0) } svg.selectAll("g.dimension") .call(render) svg.on("mousemove", function() { mouse = d3.mouse(this); svg.selectAll("circle") .attr("transform", d => d.coords[2] ? "translate(" + d.coords[2]*5*mouse[0]/width + ", " + d.coords[2]*5*mouse[1]/height + ")" : null ) }) function render(selection) { selection.each(function(data, index) { let sel = d3.select(this) .attr("transform", "translate(" + width * (0.16 + 0.33 * index) + ", " + height / 2 + ")") let circle = sel.selectAll("circle") .data(data) circle.exit().remove() circle.enter() .append("circle") .merge(circle) .each(function(d) { let iTheta = d3.interpolate(d.spherical.theta, Math.PI/2)(1 - theta) let iPhi = d3.interpolate(d.spherical.phi, 0)(1 - phi) d.coords = sphericalToCartesian({ r: d.spherical.r, theta: iTheta, phi: iPhi }) this.setAttribute("r", Math.max(.1, 1 + d.coords[2]/5)); this.setAttribute("cy", -scale(d.coords[0])); this.setAttribute("cx", scale(d.coords[1])); this.setAttribute("transform", d.coords[2] ? "translate(" + d.coords[2]*5*mouse[0]/width + ", " + d.coords[2]*5*mouse[1]/height + ")" : null ) if(theta == 0 && phi == 0) { d3.select(this) .transition() .attr("cx", d => d.y) } }) svg.select("#avgLabel").transition().attr("opacity", theta == 0 && phi == 0 ? 1 : 0) }) } return svg.node() }3b:T4ec,Fig6 = { const w = Math.min(640, width), h = 200, margin = 20, rand = d3.randomNormal(), context = DOM.context2d(w, h, 1), n = 10, scale = d3.scaleLinear() .domain([0, 4]) .range([0, .55 * h]), data = d3.range(n).map(attachData) context.strokeStyle = "#eeeeee" context.fillStyle = "#000000" context.font = '16px PT Serif' context.beginPath(); context.moveTo(0, h - margin); context.lineTo(w, h - margin); context.stroke(); context.translate(w / (2*n), h - margin) data.forEach((d,i) => { d.forEach(dd => { context.beginPath(); context.arc(dd.y, -scale(dd.r), 1, 0, Math.PI * 2) context.fill(); }) context.fillText(`${2 * i + 1}D`, -10, 15) context.translate(w / n, 0) }) function attachData(d) { let points = d3.range(200).map(() => ({r: distance(d3.range(2 * d + 1).map(d => rand()))}) ) let simulation = d3.forceSimulation(points) .force("x", d3.forceX(function(d) { return scale(d.r); }).strength(1)) .force("y", d3.forceY(0)) .force("collide", d3.forceCollide(1)) .stop(); for (var i = 0; i < 60; ++i) simulation.tick(); return points } return context.canvas; }3c:Ta43, md`Every time you add a dimension, it contributes some random non-negative component to the magnitude of the vector. When you add a third dimension perpendicular to the screen, you can’t initially see the point’s displacement along that axis — but it is probably displaced somewhat, and when you rotate that onto the visible plane, you’ll see it’s a little farther from the origin, every time. The yawning cavity that opens up under those points to the right should hit close to home: when you examine the full rich world, taken all together, in the nearest vicinity of your expectations, you will find almost nothing there. Of course the great triumph and salvation of science is that the world is largely separable into domains where expectations work extremely well; none of this is a surprise or a challenge to that. But perhaps it helps inch toward bridging the conceptual vocabulary between the extraordinary effectiveness of statistics and the enduring experience of the ineffable. There’s the old joke that the average family has 2.2 kids, but no single family has 2.2 kids, God willing. Of course, that’s just because discrete distributions can still be said to have real-valued central tendencies, but bear with me. Consider the other aspects of their being: their ages, genders, sexes, heights, locations, vocations, avocations, pets, hobbies, politics, faiths, vices, possessions, books, dreams, crimes, secrets, memories, loves. Imagine the most normal person you know. Really think about it for a minute! Then reflect on how you feel about that person: it is _normal_, for them to be so normal? You don’t walk around in a high-dimensional space, but you’d certainly be described in one. The center is all alike, but every corner is a corner in its own way. This helps to formalize certain intuitions. Finding yourself right in the middle is as strange as being way, way out on the tails. Almost nobody _is_ what people typically _are_. This is not an exception to the [mediocrity principle](https://en.wikipedia.org/wiki/Mediocrity_principle) so much as it is an unpacking: you are average, _on average_. After he was diagnosed with mesothelioma and confronted by its median mortality of eight months, Stephen Jay Gould [quoted](http://www.stephenjaygould.org/library/gould_median-isn't-the-message.html) Hilaire Belloc: “Statistics are the triumph of the quantitative method, and the quantitative method is the victory of sterility and death.” (Gould died seventeen years later.) My point is rather that, with the right framing, it is fully consistent with all the vitality of life.`3d:T10e4,md`## Further reading Eric Weisstein’s MathWorld entries “[Ball](http://mathworld.wolfram.com/Ball.html)” and “[Hypersphere](http://mathworld.wolfram.com/Hypersphere.html)” are a great place to start, as is the [Wikipedia entry](https://en.wikipedia.org/wiki/Volume_of_an_n-ball). And of course there is a very long tail of similar blog posts; I liked this one, “[Spiky Spheres](http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres)”, and the discussion on [Hacker News](https://news.ycombinator.com/item?id=3995615). Colin has written a [summary of the phenomenon](https://colindcarroll.wordpress.com/2012/07/11/volume-of-balls/), and has talked about it in the context of [difficulties it presents for Monte Carlo Markov Chains (MCMC)](https://colindcarroll.com/talk/hamiltonian-monte-carlo/): “in ten million samples from a twenty dimensional cube, none of them were inside the unit hypersphere.” He also pointed me to [this excellent talk by Michael Betancourt, also on MCMC](https://www.youtube.com/watch?v=VnNdhsm0rJQ), with quotes like “in high dimensions, every point is really far away from the typical set”. I’m obviously a sucker for quotes like that but it’s not clear I’m responsible enough to be talking about them, given that I don’t understand the “[typical set](https://en.wikipedia.org/wiki/Typical_set)”. But I can’t go too wrong by just quoting, right? In his words, at 12:45, with this lovely chart: > ![Michael Betancourt on the typical set](https://raw.githubusercontent.com/tophtucker/assets/master/2017-02-observable/typical-set-sm.png) > “Imagine over there at ${tex`|q| = 0`} we have the mode, and the tail is over at large ${tex`q`}, moving away from the mode. The [Gaussian] density is gonna fall off exponentially quickly: large at the mode, falls off really quickly. But the volume increases exponentially fast — and this exponential growth actually gets exponentially _faster_ as you go into higher and higher dimensions. And so what happens is we have these two competing forces: the volume wants to focus us to large ${tex`q`}; the density wants to focus us towards the mode; and the probability mass, the product of those two things, the thing that’s actually contributing to this expectation, is gonna balance out in the middle. This region, where all the probability mass concentrates, is what we call the typical set.” John D. Cook has often written about related observations: “[corners stick out more in high dimensions](https://www.johndcook.com/blog/2017/07/19/corners-stick-out-more-in-high-dimensions/)”; “[the advantage of formal software validation methods is that they let you explore the corners](https://www.johndcook.com/blog/2016/07/11/formal-methods-let-you-explore-the-corners/)”; “[nearly all the area in a high-dimensional sphere is near the equator](https://www.johndcook.com/blog/2017/07/13/concentration_of_measure/)” (cf. [concentration of measure](https://en.wikipedia.org/wiki/Concentration_of_measure)); and a [meta post](https://www.johndcook.com/blog/2017/07/24/is-most-volume-in-the-corners-or-not/) clarifying some of the relationships among the previous points. Finally, I’ll gesture vaguely in the direction of Stuart Kauffman’s writings on “[the adjacent possible](https://www.edge.org/conversation/the-adjacent-possible)”, “[order for free](https://www.edge.org/conversation/stuart_a_kauffman-chapter-20-order-for-free)”, “[the Galilean spell](https://www.edge.org/conversation/stuart_a_kauffman-breaking-the-galilean-spell)”, “[re-enchantment](https://www.edge.org/response-detail/23801)” and [a whole bunch of stuff on philosophy of mind](https://www.edge.org/conversation/five-problems-in-the-philosophy-of-mind). There’s a provocative recurring thread in there along the lines of: life constantly expands its own parameter space, such that the roughest contours of its evolution cannot even be stated in advance; it creates unpredictable new niches even as it fills them, fractal-like. So I will close on the note that it may be in the definitional nature of life to aggressively expand not only in space, but into new dimensions, in a formal and rigorous way that I am personally too bullshitty to fully articulate. But that’s the corner I backed myself into.`3e:T523,md`## Notes This notebook is still rough and rambling with far too many words per picture. It’s not clear for whom it’s written. It’s ill-paced, skittering between plodding and scatterbrained. I’m prone to conflation. The code is slow and unoptimized; in particular, I should re-do Fig. 5 in canvas (and add more dimensions as soon as I figure out the hyperspherical coordinate math). I’d like to highlight the tangent points in Fig. 2, as well as negative contributions to volume (the importance of being above or below 1). The reactivity of the second paragraph is awkward for many values of r. I got a little baffled about how to name recurring variables that I didn’t want to actually be linked or synced. I aspire to do something dynamic with the spiky spheres. The fact that I don’t talk more about (and illustrate) concentration of measure and the typical set shows how poorly I actually understand all this. It strikes me that it’s hard to “sprinkle” a notebook with little inline graphical furniture in the way that, say, Jennifer Daniel used to with Businessweek. But maybe that’s where other tagged template literals could come in; I just used Markdown for all the text. Oh, and it was [more like a year and a half ago](https://twitter.com/tophtucker/status/776895517095788546).`3f:T416,md`#### Update January 2021 ([diff](https://observablehq.com/compare/186d0a530f33f278@1695)) Three years later I’ve finished an addendum on [concentration of measure](https://next.observablehq.com/@tophtucker/concentration-of-measure). I’ve also updated the lead illustration, added labels to sliders, removed a few overeager exclamation points, and clarified a few paragraphs. This was one of my first Observable notebooks; looking back, I admire the design philosophy of “just a bunch of simple sliders driving animations.” I’ve enjoyed the Twitter discussion over the years: [replies](https://twitter.com/tophtucker/status/961313307931168768), [quotes tweets](https://twitter.com/tophtucker/status/961313307931168768/retweets/with_comments), [links](https://twitter.com/search?q=https%3A%2F%2Fobservablehq.com%2F%40tophtucker%2Ftheres-plenty-of-room-in-the-corners&src=typed_query). If I have more time I’d like to: - Illustrate “as if swinging them around the origin on a fixed-length arm” - Illustrate spikiness somehow `40:T417,// Header illustration getIllo = () => { const w = width + 28, h = 250; const context = DOM.context2d(w, h, 1); const goingIn = Math.random() > 0.5; const getRandomColor = () => Math.random() > 0.75 ? "white" : `hsl(${Math.random() * 360},50%,50%)`; context.canvas.style.margin = "0 -14px 0 -14px"; context.canvas.style.position = "relative"; context.canvas.style.zIndex = "-1"; context.canvas.style.imageRendering = "pixelated"; context.globalCompositeOperation = "xor"; const data = d3.range(10).map(d => ({ cx: Math.random() * w, cy: Math.random() * h, r: (Math.random() * h) / 4, c: getRandomColor(), t0: Math.random() * 2000 })); let dr = goingIn ? 4 : 1; d3.timer(t => { if (t > 5000) return true; data.forEach(d => { if (t < d.t0) return; context.strokeStyle = d.c; context.beginPath(); context.arc(d.cx, d.cy, d.r, 0, Math.PI * 2); context.stroke(); d.r += dr; dr *= goingIn ? 0.995 : 1.01; }); }); return context.canvas; }41:[{"id":"4200cdcccfc52fffc9c97b665adacde51c2b73b2eb6b8d2bf3be1bded413ff63da720ef3cf9eb6866c5091c0ced8110fd84fcf5fd0d6c3200bb8ec3e5ad4dc79","href":"https://static.observableusercontent.com/files/4200cdcccfc52fffc9c97b665adacde51c2b73b2eb6b8d2bf3be1bded413ff63da720ef3cf9eb6866c5091c0ced8110fd84fcf5fd0d6c3200bb8ec3e5ad4dc79","name":"angle-10000d.png","type":"image/png","lastModified":1707092966558.768,"size":14788}] 2f:{"title":"There’s Plenty of Room in the Corners","cells":[{"id":0,"value":"md`

There’s Plenty of Room in the Corners

\n${getIllo()}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"{\n let vols = d3.range(30).map(d => volume(r, d));\n let maxVol = vols.indexOf(d3.max(vols));\n return md`One time, maybe a year ago, my friend [Colin](https://twitter.com/colindcarroll) casually mentioned that in high dimensions, the volume of a sphere goes to zero. \n\nIt happens for any fixed radius, but for a radius of ${r}, the volume starts at ${\n r === 1 ? 2 : vols[1].toFixed(2)\n } for 1 dimension (imagine a line from −${r} to ${r}), then ${\n r === 1 ? tex`\\pi` : vols[2].toFixed(2)\n } for 2 dimensions (what you’d normally call the area of a circle), then ${vols[3].toFixed(\n 2\n )} for 3 dimensions (a colloquial sphere)${\n r <= 0.8 ? '; so, it' : ', and then'\n } _peaks_ at ${vols[maxVol].toFixed(\n 2\n )} for ${maxVol} dimensions, and approaches zero thereafter:`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":977,"value":"viewof r = slider({min: 0.5, max: 2, step: 0.05, value: 1, title: \"Radius\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":979,"value":"viewof n = slider({min: 0, max: 30, step: 1, value: 3, title: \"Dimension\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":981,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":974,"value":"md`I was astounded! How had I lived so long without knowing such a profound and basic truth? For [like](https://twitter.com/tophtucker/status/90944159535476736) [six](https://twitter.com/tophtucker/status/621041809511305216) [years](https://twitter.com/tophtucker/status/771848545649455104) I’d been curious about the [curse of dimensionality](https://en.wikipedia.org/wiki/Curse_of_dimensionality) and [Big Sky Theory](https://en.wikipedia.org/wiki/Big_sky_theory), but didn’t realize it reached such a catastrophic climax. I became obsessed, asking Colin about it all time, and remain obsessed, and all my intuition about it, as far as that goes, I owe to him (and obviously any errors are my own).\n\nHere’s the equation for the volume in ${tex`n`} dimensions, and the corresponding code used for this notebook:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1220,"value":"{\n let v = volume(r,n)\n return tex`V_n = \\frac{\\pi^{n/2}R^n}{\\Gamma(1+\\frac{1}{2}n)} \\implies V_{${n}} = \\frac{\\pi^{${n/2}}${r}^{${n}}}{\\Gamma(${1+.5*n})} ${v % 1 < 0.01 && v > .9 ? `= ${Math.round(v)}` : `\\\\approx ${v.toFixed(3)}...`}`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":919,"value":"volume = (r, n) => (Math.PI ** (n / 2) * r ** n) / gamma(1 + (1 / 2) * n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1181,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"md`_Slide to the right to see points along each axis from balls of increasing dimension._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":225,"value":"viewof dimension = slider({min: 1, max: 6, step: 0.01, value: 1, title: \"Dimension\", format: () => \"\"})\n // html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":450,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1430,"value":"{\n let d = Math.floor(dim)\n return tex`\\sqrt{${d3.range(d).map(d => 'r^2').join(' + ')}} ${Math.sqrt(d) % 1 === 0 ? ' = ' + Math.sqrt(d) : '= \\\\sqrt{' + d + '}r \\\\approx ' + Math.sqrt(d).toFixed(2)}r`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1280,"value":"viewof dim = slider({min: 1, max: 20, step: 0.05, value: 1, title: \"Dimension\", format: d => Math.floor(d)})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1284,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1279,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":482,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":485,"value":"md`God, it’s beautiful! (Don’t ask me what the ${tex`u_1`} is, it’s from a [conference poster](https://mathoverflow.net/posts/26010/revisions).) The danger with Fig. 2 is that you start to squint and just feel like the ball is fading away at the edges. But those tangent points are important! It’s almost like... like what if we just took the circle, and took all those higher-dimensional corner points and, uh, just jam them in there, in the corners, you see....`","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"{\n const width = 900,\n height = 25,\n \t\tsvg = d3.select(this || html``);\n \n let fn = n => (\n t => [\n Math.pow(Math.sin(t), n) + Math.sin(t),\n Math.pow(Math.cos(t), n) + Math.cos(t),\n ]\n )\n \n let data = d3.range(1, 30, 1)\n .map(n => fn(n))\n \t.map(fn => d3.range(0, Math.PI/2, 0.1).concat(Math.PI/2).map(t => fn(t)))\n \n let path = d3.line()\n \t.x(d => d[0]*10)\n \t.y(d => d[1]*10)\n \n svg.selectAll(\"g\").data(data).enter()\n \t.append(\"g\")\n \t.attr(\"transform\", (d,i) => `translate(${i * 50},30)`)\n \t.each(function(d) {\n \td3.range(0,360,90).forEach(t => {\n d3.select(this).append(\"path\").attr(\"d\", path)\n .style(\"fill\", \"none\")\n .style(\"stroke\", \"black\")\n .style(\"transform\", `rotate(${t}deg)`)\n })\n })\n \n return svg.node()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":599,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":494,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":851,"value":"md`_First, collapse the third dimension with the “theta” slider. Observe the donutification of the rightmost distribution. Then, collapse the second dimension with the “phi” slider._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":817,"value":"viewof theta = slider({\n min: 0,\n max: 1,\n step: 0.01,\n value: 1,\n title: \"Theta\",\n format: d => `${Math.floor(360 * d)}º`\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":815,"value":"viewof phi = slider({\n min: 0,\n max: 1,\n step: 0.01,\n value: 1,\n title: \"Phi\",\n format: d => `${Math.floor(360 * d)}º`\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":812,"value":"md`Look at the distributions of distance-from-center once you collapse both theta and phi. The higher the dimension, the farther the center of mass is from the origin. Remember, the origin is still the average! But more and more of the mass gets to be _farther_ from the average!`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1526,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":1525,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":1496,"value":"{\n const w = width + 28, h = 500;\n const context = DOM.context2d(w, h, 1);\n const getRandomColor = () => `hsl(${Math.random()*360},50%,50%)`\n\n context.canvas.style.margin = \"0px -14px 0 -14px\";\n context.canvas.style.position = \"relative\";\n context.canvas.style.zIndex = \"-1\";\n context.canvas.style.imageRendering = \"pixelated\";\n context.globalAlpha=0.2;\n context.globalCompositeOperation = \"xor\";\n \n const data = d3.range(10).map(d => ({\n cx: Math.random() * w,\n cy: Math.random() * h,\n r: Math.random() * h/4,\n c: getRandomColor(),\n t0: Math.random() * 2000\n }))\n \n d3.timer((t) => {\n if(t < 2500 || t > 4000) return\n context.globalAlpha=0.2;\n data.forEach(d => {\n if(t < d.t0) return\n context.strokeStyle=d.c\n context.beginPath();\n context.arc(d.cx, d.cy, d.r, 0, Math.PI*2)\n context.stroke()\n d.r += 1\n })\n })\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":636,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"},{"id":933,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs"},{"id":1937,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs"},{"id":2022,"value":"**Update February 2024**\n\nCheck out the distribution of angles between points placed randomly on a hypercube in 10000D, [by Martin Thomas](https://martin-thoma.com/curse-of-dimensionality/), via [Liz](https://twitter.com/inerati/status/1754211935179178011), who says: “High dimensional hypercubes are basically all edge there’s very very little space like ‘inside’ the cube”:\n\n${await FileAttachment(\"angle-10000d.png\").image({width: 340})}","pinned":false,"hidden":false,"mode":"md"},{"id":463,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"sum = arr => arr.reduce((acc, cur) => acc + cur, 0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"product = arr => arr.reduce((acc, cur) => acc * cur, 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":105,"value":"distance = arr => Math.sqrt(sum(arr.map(d => Math.pow(d, 2))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":778,"value":"cartesianToSpherical = cartesian => ({\n r: distance(cartesian),\n theta: Math.acos(cartesian[2] / distance(cartesian)),\n phi: Math.atan2(cartesian[1], cartesian[0]) //atan2 for weird quadrant stuff!\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":780,"value":"sphericalToCartesian = spherical => [\n spherical.r * Math.sin(spherical.theta) * Math.cos(spherical.phi),\n spherical.r * Math.sin(spherical.theta) * Math.sin(spherical.phi),\n spherical.r * Math.cos(spherical.theta)\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":916,"value":"// https://stackoverflow.com/a/15455055/120290\ngamma = z =>\n Math.sqrt((2 * Math.PI) / z) *\n Math.pow((1 / Math.E) * (z + 1 / (12 * z - 1 / (10 * z))), z)","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"// Gets the point samples for the dots in Figure 2\ngetPoints = (dim, r) => {\n let getRange = () => d3.range(-r, r + 1, 1);\n return d3\n .range(dim - 1)\n .reduce(\n (acc, cur) => d3.cross(acc, getRange(), (a, b) => a.concat(b)),\n getRange().map(d => [d])\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1828,"value":"// Adds title and value label to basic HTML range slider\nslider = ({ min, max, step, value, title, format = d => d }) => {\n const form = html``;\n const label = form.querySelector(\".value\");\n form.oninput = () =>\n (label.innerText = format((form.value = form.i.valueAsNumber)));\n form.oninput();\n return form;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":685,"value":"$40","pinned":true,"hidden":false,"mode":"ojs"},{"id":1645,"value":"style = html``","pinned":true,"hidden":false,"mode":"ojs"},{"id":1668,"value":"import {previews} from \"@tophtucker/reflecting-on-vote-cones\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":52,"value":"d3 = require('d3')","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W41","stdlib":"1","titling":"auto"}