# Short: Probabilities

For this thought experiment, let’s equate a probability of 1 (100% chance, a certainty) with the diameter of the observable universe. The diameter of the observable universe is about 93 billion light-years (because, during the 13.8 billion years since it started, the universe has been steadily expanding). With this analogy, let’s consider some probabilities!

According to the National Weather Service, your odds of being struck by lightning this year (if you live in the US, that is) are 1 in 1,042,000. Less than one in a million. One part in a million of the diameter of the universe is 93,000 light-years, which is far enough to take you outside the Milky Way, but on a cosmic scale, absolutely tiny.

The odds of winning the jackpot with a single ticket in the U.S. Powerball lottery are around 1 in 292 million. That’s like 318 light-years set against the diameter of the universe. 318 light-years is a long way. Even so, it’s an almost-reasonable distance. Most of the brighter stars you see in the night sky are closer than that. That’s almost the Sun’s neighborhood. Compared to the entire universe. Maybe that’s why they say the lottery is for suckers…

The odds of being struck by lightning three times in your lifetime are, mathematically, 1 in 1,000,000,000,000,000,000. The actual odds are even lower, since there’s a non-zero chance that you’ll be killed by a lightning strike, making getting another impossible. If your odds of dying in a lightning strike are 10%, then your odds of surviving are 9/10, and your odds of surviving the first two so you can get the third are (1 in a million) * (9/10) * (1 in a million) * (9 in 10) * (1 in a million), or about 81 in one hundred million trillion.That’s 81 in 100,000,000,000,000,000,000. That’s roughly the diameter of the Earth-moon system compared to the diameter of the universe.

The odds of putting 100 pennies in a cup, shaking them up, and scattering them so they all land flat, and then having every single coin come up heads, are 1 in 1, 267, 650, 600, 228, 229, 401, 496, 703, 205, 376. That’s the diameter of a grain of sand compared to the entire universe. Literally.

Get a standard deck of cards. Take out the jokers and the instructions. Shuffle the deck and pick a card at random. Do this 25 times. The odds of picking the jack of clubs every single time are like a proton compared to the visible universe.

If you pick 43 letters at random, the odds of forming the string

actisceneielsinoreaplatformbeforethecastlef

(that is, the first 43 letters of Hamlet) are as small as one Planck length (which is the smallest unit of distance that ever gets used in actual physics) compared to the visible universe. For reference, a Planck length is ten million trillion times smaller than a proton, which is itself a trillion times smaller than a grain of salt.

Incidentally, if you assembled random 43-letter strings, you would have to do it

32, 143, 980, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000

times to have a 99% chance of producing the first 43 letters of Hamlet in one of them. But a human bard did it in, at most, a couple hundred tries. Isn’t that weird? More probability stuff (and black hole stuff) to come!

Standard
Uncategorized

# The curse of dimensionality.

(The coolest part of this article will be that “The Curse of Dimensionality” is an actual legitimate term from computer science, even though it sounds like something from H.P. Lovecraft’s nightmares. But it’s a real scientific thing. Take a look.)

I like cellular automata. A cellular automaton is a bunch of cells arranged on some kind of grid. Each cell has a “state” variable. Each time-step, it decides which state to go into next according to a rule which looks at its current state and the state of all the cells around it. It’s about as simple as a computer simulation gets, but even in one dimension, it can produce amazing psychedelic patterns like this one:

(The picture is two-dimensional, of course. Each timestep, the one-dimensional line of cells is rendered as a line of colored pixels, with its distance from the top increasing as time goes on. Click on the picture to get a version that isn’t all compressed and horrible.)

It doesn’t take much processing power to run a program like this. For instance, a 1-D cellular automaton with 1,000 cells and 8 possible states would only require 1,000 bytes of memory.

2-D automata take up a little more space, but they can still run smooth as butter on most computers, especially with neat, streamlined code. In two dimensions, an 8-state cellular automaton on a grid measuring 1,000 by 1,000 (1,000,000 cells) would only require a megabyte.

But you know me. I don’t like it when things are easy. I like it when things are weird. What if, for instance, we imagined a 3-dimensional cellular automaton? Here, each cell has 27 neighbors (itself and the cells adjacent to it and touching its corners and edges). If this cube of cells measured 1,000 cells on an edge (and each cell could still be in one of 8 states), then the cellular automaton would need 1 gigabyte of memory. I’m old enough to remember when that was an impressive amount, and indeed, processing a gigabyte of at 30 frames per second takes a bit of power. More power than a Pentium III chip had in 1999, at least.

But couldn’t we go bigger? OF COURSE! In a 4-dimensional cellular automaton, every cell has 81 neighbors, we’ve got a trillion cells, a terabyte of data (you’re probably going to need an extra hard drive), and our throughput would strain even a modern graphics card.

But let’s go BIGGER! I like the number 6, so let’s imagine a cellular automaton in 6 dimensions. Every cell has 729 neighbors adjacent to it. (Remember the good old days, back in 2 dimensions, when every cell had a measly 9 neighbors?). We’re going to need 1 million hard drives to store all those 8-bit numbers (there are 1,000,000,000,000,000,000 of them, after all), and we’re going to need a supercomputer more powerful than any currently in existence to handle the 60 exaFLOPS needed to maintain a smooth 60-FPS framerate. We will also need an air conditioning unit the size of a house, but don’t we always when I’m around?

But this is baby stuff. When scientists talk about high-dimensional mathematics, they’re not talking about hypercubes in 4 or 6 dimensions. They’re talking about crazy curves and datasets in, say, 256 dimensions! 256-D sounds like fun, so let’s go there!

Okay. I think I went too far. Again. For a start, every cell in our 256-D automaton will have 139008452377144732764939786789661303114218850808529137991604824430036072629766435941001769154109609521811665540548899435521 neighbors, which is more than a googol, which is a LOT. Second, the full 1,000 by 1,000 by 1,000 (by 1,000 until you hit 256) automaton would require

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

bytes to store. That’s 768 zeroes. We’re talking numbers without names here.

What the hell happened? I mean, 256 isn’t exactly a small number. It’s certainly larger than the number of pounds of cilantro you’d want to eat, but it’s hardly huge.

Well, that’s the Curse of Dimensionality. A cube’s N-dimensional “content” (which is an analogue for 3-dimensional volume or 2-dimensional area) is equal to S^N, where S is the length of an edge. And as anybody who’s ever played with numbers knows, throwing exponents into things makes numbers get scary very fast.

And there’s another odd problem that you don’t notice much in two or three dimensions. A circle with a diameter of 2 has an area of (approximately) 3.142, while a square with an edge length of 2 has an area of 4. The ratio of square area to circle area is 1.273. A sphere with a diameter of 2 has a volume of 4.189, while a cube with an edge length of 2 has a volume of 8. The ratio is now 1.910. Well, the ratio keeps going up. And it goes up FAST. A 256-dimensional cube with edge length 2 has a hyper-volume (content) of 115792089237316195423570985008687907853269984665640564039457584007913129639936, which is a lot. Meanwhile, a 256-dimensional sphere with a diameter of 2 has a content of 1.1195×10^-152. That’s an absurdly small number. 1.1195×10^-152 universe diameters (and in case you forgot, the universe is so large that trying to fit its size into your head would probably physically kill you) is ten million trillion trillion trillion trillion trillion trillion trillion times smaller than the smallest distance which makes any physical sense (Side note: isn’t it weird that there’s a smallest physically-sensible distance? Reality has a finite resolution!)

What this all boils down to is that the vast majority of a hyper-cube’s content is in its corners. And, as anybody who’s ever tried to dust a room knows, corners are a pain in the ass. Which is why it’s so hard to work on data-sets in high-dimensional space.

Here’s another interesting fact. I was talking about Lovecraftian horrors at the start. And, although he gets binned as a horror writer, he was actually kind of a horror/sci-fi writer. He liked thinking about non-Euclidean geometry and extra dimensions and other such stuff that was wild and revolutionary at the time. Before I go get some much-needed sleep (I keep having weird dreams about having to take tests so I can work at a pizza parlor. Trust me, they’re exhausting.), let’s work out just how large a 256-dimensional creature would be.

A human being contains approximately 7×10^27 atoms. That’s a lot. If we take (7×10^27)^(1/3) (the cube root), we get how many atoms would lie along the edge of a cube with that many atoms. A cube about the density of a human containing about the same amount of stuff as a human would be 40 centimeters on an edge (Don’t try to imagine ways to make a human into a perfect cube. None of them are nice.) What about a 6-dimensional human? Well, because you can pack so much stuff into a 6-cube, a creature with as many atoms as a human and the same approximate atom-to-atom distance as a human would form a cube 8.7 microns on an edge, about as large as a medium-large bacterium or a human cell. In 256 dimensions, you’d actually run out of atoms before you ran out of places to put them. Imagine you put down one atom at one corner of a big 256-D grid. Then, you start putting atoms in the neighboring cells. Well, in 256-D, there are 115792089237316195423570985008687907853269984665640564039457584007913129639935 neighboring cells, which is more than the number of atoms in a person, so our 256-D human would be no more than two atoms across (no larger than a molecule, in other words) along any dimension.

I don’t know about you, but I’ve succeeded in tripping all the circuit breakers in my head. I’m going to lie down. But I’ll see you again soon, after I find something else headache-inducing to think about.

Standard