# quantum physics, traffic, chicken eyes, random matrices, and ...?

January 27, 2018 9:37 PM Subscribe

In Mysterious Pattern, Math and Nature Converge, Natalie Wolchover for

The statistical properties of the city transport in Cuernavaca (Mexico) and random matrix ensembles[PDF]

Physics, stability, and dynamics of supply networks.

Headways in traffic flow: remarks from a physical perspective.

László Erdős and Horng-Tzer Yau to receive 2017 AMS Eisenbud Prize

Random matrices: The Universality phenomenon for Wigner ensembles

"Is this all just a fluke, this apparent link between matrix eigenvalues, nuclear physics, zeta zeros, and Mexican busses?"

At the Far Ends of a New Universal Law [previously]

A simple derivation of the Tracy–Widom distribution of the maximal eigenvalue of a Gaussian unitary random matrix

A Bird’s-Eye View of Nature’s Hidden Order

In the eye of a chicken, a new state of matter comes into view

Random scalar fields and hyperuniformity

Hyperuniformity of critical absorbing states

The Weyl-Heisenberg ensemble: hyperuniformity and higher Landau levels

Physicists Uncover Geometric ‘Theory Space’

From Prime Numbers to Nuclear Physics and Beyond

*Quanta*In 1999, while sitting at a bus stop in Cuernavaca, Mexico, a Czech physicist named Petr Šeba noticed young men handing slips of paper to the bus drivers in exchange for cash. It wasn’t organized crime, he learned, but another shadow trade: Each driver paid a “spy” to record when the bus ahead of his had departed the stop. If it had left recently, he would slow down, letting passengers accumulate at the next stop. If it had departed long ago, he sped up to keep other buses from passing him. This system maximized profits for the drivers. And it gave Šeba an idea. “We felt here some kind of similarity with quantum chaotic systems,” explained Šeba’s co-author, Milan Krbálek, in an email.

The statistical properties of the city transport in Cuernavaca (Mexico) and random matrix ensembles[PDF]

Physics, stability, and dynamics of supply networks.

Headways in traffic flow: remarks from a physical perspective.

László Erdős and Horng-Tzer Yau to receive 2017 AMS Eisenbud Prize

Random matrices: The Universality phenomenon for Wigner ensembles

"Is this all just a fluke, this apparent link between matrix eigenvalues, nuclear physics, zeta zeros, and Mexican busses?"

At the Far Ends of a New Universal Law [previously]

In 1972, the biologist Robert May devised a simple mathematical model that worked much like the archipelago. He wanted to figure out whether a complex ecosystem can ever be stable or whether interactions between species inevitably lead some to wipe out others. By indexing chance interactions between species as random numbers in a matrix, he calculated the critical “interaction strength” — a measure of the number of flotsam rafts, for example — needed to destabilize the ecosystem. Below this critical point, all species maintained steady populations. Above it, the populations shot toward zero or infinity.Tracy-Widom Distribution and its Applications[PDF]

Little did May know, the tipping point he discovered was one of the first glimpses of a curiously pervasive statistical law.

A simple derivation of the Tracy–Widom distribution of the maximal eigenvalue of a Gaussian unitary random matrix

A Bird’s-Eye View of Nature’s Hidden Order

“It’s extremely beautiful just to look at these patterns,” he said. “We were kind of captured by the beauty, and had, purely out of curiosity, the desire to understand the patterns better.” He and his collaborators also hoped to figure out the patterns’ function, and how they were generated. He didn’t know then that these same questions were being asked in numerous other contexts, or that he had found the first biological manifestation of a type of hidden order that has also turned up all over mathematics and physics.Avian photoreceptor patterns represent a disordered hyperuniform solution to a multiscale packing problem

In the eye of a chicken, a new state of matter comes into view

Random scalar fields and hyperuniformity

Hyperuniformity of critical absorbing states

The Weyl-Heisenberg ensemble: hyperuniformity and higher Landau levels

Physicists Uncover Geometric ‘Theory Space’

Their findings indicate that the set of all quantum field theories forms a unique mathematical structure, one that does indeed pull itself up by its own bootstraps, which means it can be understood on its own terms.see also:

As physicists use the bootstrap to explore the geometry of this theory space, they are pinpointing the roots of “universality,” a remarkable phenomenon in which identical behaviors emerge in materials as different as magnets and water. They are also discovering general features of quantum gravity theories, with apparent implications for the quantum origin of gravity in our own universe and the origin of space-time itself.

From Prime Numbers to Nuclear Physics and Beyond

So people that do procedural generation (especially for games) have noted that if you generate 2d points uniformly at random, those points often happen to cluster up in seemingly non-random ways. So they use poisson disk sampling instead. But I wonder if it might be possible to even out the distribution using the mutual "repulsion" of eigenvalues.

posted by Jpfed at 9:53 PM on January 27, 2018 [2 favorites]

posted by Jpfed at 9:53 PM on January 27, 2018 [2 favorites]

Random matrix ensembles and universality always sounded like one of the big new topics in pure mathematics that I couldn't find a good starting point to understand. This looks great, thanks for the post!

posted by a car full of lions at 10:02 PM on January 27, 2018

posted by a car full of lions at 10:02 PM on January 27, 2018

What a great lead article o mantot! I've just granulated it for my tweeps with annotations relating to the informal economy patterns I've observed on three continents

posted by infini at 10:03 PM on January 27, 2018

posted by infini at 10:03 PM on January 27, 2018

Now I come here to ponderously pontificate circumlocutoraly on one point:

My own choice of complex adaptive system is the value web of informal trade created by established traders - demand, supply, support services such as transport & forex, and various other relationships of trusted give and take as the basic microsystem or node in the more complex regional trading ecosystem as is prevalent in developing countries such as those in the East African Community.

The fact that its more human, less technologically and infrastructurally mediated means that the intuition that the scientists are missing in their random numbers is that which makes us human i.e. the patterns of human give and take make it easier to see the complex whole and undertand it in a way tht perhaps a matrix may not offer.

So, while the article is valuable to my own work, it also relieves me to have read it and to reflect upon my own research from the lens it offers additionally.

What the article didn't make clear for me was whether each matrix has its own pattern which emerges or whether all the matrices were showing the same exact pattern regardless of their randomness.

posted by infini at 10:15 PM on January 27, 2018 [4 favorites]

*"Scientists have yet to develop an intuitive understanding of*(quanta article)**why this**particular random-yet-regular pattern, and not some other pattern, emerges for complex systems."My own choice of complex adaptive system is the value web of informal trade created by established traders - demand, supply, support services such as transport & forex, and various other relationships of trusted give and take as the basic microsystem or node in the more complex regional trading ecosystem as is prevalent in developing countries such as those in the East African Community.

The fact that its more human, less technologically and infrastructurally mediated means that the intuition that the scientists are missing in their random numbers is that which makes us human i.e. the patterns of human give and take make it easier to see the complex whole and undertand it in a way tht perhaps a matrix may not offer.

So, while the article is valuable to my own work, it also relieves me to have read it and to reflect upon my own research from the lens it offers additionally.

**tl;dr**- I saw the same patterns emerge in rural Philippines, rural India, rural Kenya, rural Malawi, etc etc and because the complex system was an informal human one, it was easier to tease out factors that drove certain responses to certain conditions and separate elements related to language/history/culture from patterns related to uncertainty of income and lack of infrastructure and development.What the article didn't make clear for me was whether each matrix has its own pattern which emerges or whether all the matrices were showing the same exact pattern regardless of their randomness.

posted by infini at 10:15 PM on January 27, 2018 [4 favorites]

**Jpfed**, that would be simply repulsion of points. I don't know of a layman's explanation of the phenomenon of 'eigenvalue repulsion', but it emerges from the spectrum of a disordered (or even perturbed) system. It's not something you put in by hand. The chicken eye pattern may be more in your line - it seems to contain repulsion rules in real space.

Thanks for the post! Dunno if others care for technical papers interspersed with the pop sci but you gets a thumbs up from me.

posted by tirutiru at 10:20 PM on January 27, 2018 [2 favorites]

*granulated it for my tweeps with annotations*

Am fine with the maths in the post but this is uh like a Sumerian limerick.

*...whether each matrix has its own pattern which emerges or whether all the matrices were showing the same exact pattern regardless of their randomness.*

Strictly speaking, `randomness` of a single matrix is undefined. It is a property of an ensemble - a set of matrices whose entries are generated by the same probabilistic process. For example take a large symmetric matrix of random real numbers and diagonalize it to get the eigenvalues. You are now in the Orthogonal ensemble and the eigenvalues appear to repel each other with a 1/r potential, sort of like electric charges. Map the distribution of eigenvalues and you get a Wigner semi-circle law - one of those curious discoveries applicable far beyond it's original constraints.

posted by tirutiru at 10:42 PM on January 27, 2018 [2 favorites]

*Jpfed, that would be simply repulsion of points.*

Yeah, in procedural generation the points can come from wherever. It's the results that matter. So couldn't you generate a random complex matrix, find the eigenvalues (which will be complex), and use the real parts of the eigenvalues for x coordinates and imaginary parts for y coordinates? That should generate mutually-repelled points. In retrospect it sounds like some computational heavy lifting, so probably not worth it.

I don't know of a layman's explanation of the phenomenon of 'eigenvalue repulsion'

I don't know of a layman's explanation of the phenomenon of 'eigenvalue repulsion'

Here's a stab: Take a rubber sheet and use a marker to put a dot on it. The location of that dot relative to the center of the sheet is the state of the system. Now we're going to play around with the sheet. If someone stretches the sheet so the dot is still in the same direction from the center of the sheet, but it's just closer or farther, the location of that dot represents an eigenvector for that kind of stretching. The ratio of the new distance to the center versus the original distance from the center is the eigenvalue for that dot.

Now, let's imagine a three dimensional bulk slab of stretchy material and put bubbles in it. You can manipulate this slab in a more ways. But still, there will be some set of bubbles that, for a particular kind of stretching, only get moved further from the origin, and each of those bubbles will have some distance ratio (eigenvalue).

But for random matrices (random amounts of turning/stretching/squishing about each axis), the distance ratios tend to be different from one another.

Is that a reasonable summary?

posted by Jpfed at 10:46 PM on January 27, 2018 [6 favorites]

That's a good geometric picture of eigenvalues. But we need statistical properties that generally depend on the

Much of the work in the post is an effort in the opposite direction. You posit some properties of the eigenvalue spectrum (from numerical observation/theory/whatever) and try to find reasonable probability rules for matrices that could lead to it. This is an open-ended problem - which makes it very attractive!

posted by tirutiru at 11:17 PM on January 27, 2018 [5 favorites]

*differences*between eigenvalues. For example if the matrix is perturbed (randomly) and some eigenvalue moves a bit, then the neighbouring eigenvalues tend to make way by moving away from it. And this repulsion can be quantified precisely. You can see a simple version of it by playing with a quantum system with a few energy levels.Much of the work in the post is an effort in the opposite direction. You posit some properties of the eigenvalue spectrum (from numerical observation/theory/whatever) and try to find reasonable probability rules for matrices that could lead to it. This is an open-ended problem - which makes it very attractive!

posted by tirutiru at 11:17 PM on January 27, 2018 [5 favorites]

*This technique is enabling scientists to understand the structure and evolution of the Internet. Certain properties of this vast computer network, such as the typical size of a cluster of computers, can be closely estimated by measurable properties of the corresponding random matrix. “People are very interested in clusters and their locations, partially motivated by practical purposes such as advertising,” Vu said.*

Jesus wept. Hey, I bet we could use this to sell more ads!

posted by thelonius at 11:22 PM on January 27, 2018 [8 favorites]

This is what I wish I had studied. If I make it to old age I will go back to school and take all my field experience with me and do some work on it. There are some hard rules about how energy flows through biological systems that are there but we have not discovered them yet and it fascinates me. I haven't read all these papers, thanks!

posted by fshgrl at 11:23 PM on January 27, 2018 [2 favorites]

posted by fshgrl at 11:23 PM on January 27, 2018 [2 favorites]

This, btw, is why I think the current AI neural networks and other programmes will never be anything but toys. They are too resource rich to develop into anything resembling real life (which I'm 100% fine with, I think it's a terrible idea). That's not how complexity develops.

posted by fshgrl at 11:26 PM on January 27, 2018 [1 favorite]

posted by fshgrl at 11:26 PM on January 27, 2018 [1 favorite]

11:15, restate my assumptions: 1. Mathematics is the language of nature. 2. Everything around us can be represented and understood through numbers. 3. If you graph these numbers, patterns emerge. Therefore: There are patterns everywhere in nature.

posted by radwolf76 at 11:27 PM on January 27, 2018 [6 favorites]

posted by radwolf76 at 11:27 PM on January 27, 2018 [6 favorites]

>

I like the definition of randomness based on Kolmogorov Complexity, as popularized by Gregory Chaitin.

The algorithmic complexity of an output is the minimum size of a program needed to generate that output. A random output is one where the minimum size of the program is equal to the size of the output. IE: the output is algorithmically uncompressible.

This notion of randomness is defined for a single object. It means the object has no structure to exploit for compression. Also, it provides a nice definition for understanding, as our ability to devise a smaller program to compress a certain output.

posted by I-Write-Essays at 12:12 AM on January 28, 2018 [1 favorite]

*Strictly speaking, `randomness` of a single matrix is undefined.*I like the definition of randomness based on Kolmogorov Complexity, as popularized by Gregory Chaitin.

The algorithmic complexity of an output is the minimum size of a program needed to generate that output. A random output is one where the minimum size of the program is equal to the size of the output. IE: the output is algorithmically uncompressible.

This notion of randomness is defined for a single object. It means the object has no structure to exploit for compression. Also, it provides a nice definition for understanding, as our ability to devise a smaller program to compress a certain output.

posted by I-Write-Essays at 12:12 AM on January 28, 2018 [1 favorite]

Also, when you apply this idea to an ensemble of states as the output, we get our probabilistic notion of randomness back again, and it becomes easy to understand the difference between true randomness and pseudo-randomness.

posted by I-Write-Essays at 12:37 AM on January 28, 2018 [1 favorite]

posted by I-Write-Essays at 12:37 AM on January 28, 2018 [1 favorite]

Algorithmic complexity is not relevant to random matrix theory, since we only care about ensemble averages. For that matter everything may as well be pseudo random since no expectation value can tell the difference.

posted by tirutiru at 2:12 AM on January 28, 2018 [2 favorites]

posted by tirutiru at 2:12 AM on January 28, 2018 [2 favorites]

this type of thing is extremely cool. it seems like its heyday was in the 90s, though, and as someone who is too young for that, i've noticed that this broad area ("network science", "complex systems") has something of a bad reputation among researchers.

some of it comes from "engineer's disease", there were a lot of physicists who would look at some interesting real world phenomenon, declare it equivalent to an Ising glass or something, derive some theorems, and then claim to have "solved" the problem, immensely annoying the actual scientists.

also some of the biggest names in the field are extremely prone towards unjustified hype and ruthless self-promotion as well (not going to name names, but one of them starts with "Bara" and ends with "bási"). and there are a ton of papers that were just wrong.

it's obviously still an extremely important field of study, though. the problem is just that so many "universal" patterns of behavior in complex systems have turned out to be bullshit. at the same time, given what we can see about the world, it seems that there must be such patterns!

maybe analyzing the spectra of random matrices is the way to do this. it seems pretty plausible; spectral graph theory is really powerful in lots of areas. as somebody said on Metafilter before, we should never be surprised when the eigenvalues of something turn out to be meaningful.

power-laws and random graph processes seem plausible too, though, so i don't know what to believe.

posted by vogon_poet at 2:17 AM on January 28, 2018 [11 favorites]

some of it comes from "engineer's disease", there were a lot of physicists who would look at some interesting real world phenomenon, declare it equivalent to an Ising glass or something, derive some theorems, and then claim to have "solved" the problem, immensely annoying the actual scientists.

also some of the biggest names in the field are extremely prone towards unjustified hype and ruthless self-promotion as well (not going to name names, but one of them starts with "Bara" and ends with "bási"). and there are a ton of papers that were just wrong.

it's obviously still an extremely important field of study, though. the problem is just that so many "universal" patterns of behavior in complex systems have turned out to be bullshit. at the same time, given what we can see about the world, it seems that there must be such patterns!

maybe analyzing the spectra of random matrices is the way to do this. it seems pretty plausible; spectral graph theory is really powerful in lots of areas. as somebody said on Metafilter before, we should never be surprised when the eigenvalues of something turn out to be meaningful.

power-laws and random graph processes seem plausible too, though, so i don't know what to believe.

posted by vogon_poet at 2:17 AM on January 28, 2018 [11 favorites]

*You are now in the Orthogonal ensemble and the eigenvalues appear to repel each other with a 1/r potential, sort of like electric charges. Map the distribution of eigenvalues and you get a Wigner semi-circle law - one of those curious discoveries applicable far beyond it's original constraints.*

tirutiru, given my last college course was in the 1980s, would I be wrong in thinking this is similar to bell curve behaviour and outcomes? i.e. similar span of applicability with a similar diagrammatic explanation?

posted by infini at 2:47 AM on January 28, 2018 [1 favorite]

I-Write-Essays:

Doesn't this mean that most practical pseudo-random number generators have extremely low randomness?

posted by clawsoon at 2:49 AM on January 28, 2018

*I like the definition of randomness based on Kolmogorov Complexity, as popularized by Gregory Chaitin. The algorithmic complexity of an output is the minimum size of a program needed to generate that output.*Doesn't this mean that most practical pseudo-random number generators have extremely low randomness?

posted by clawsoon at 2:49 AM on January 28, 2018

*This is what I wish I had studied.*

My first college admission was for Physics Honours, but after one term I dropped out, did more A levels and went for engineering. Sometimes when parts of my brain randomly collide, like this thread, I feel pleasure that has no name ;p

posted by infini at 2:52 AM on January 28, 2018 [1 favorite]

*Hey, I bet we could use this to sell more ads!*

Ozymandias comes to mind.

posted by infini at 2:53 AM on January 28, 2018 [2 favorites]

*though, so i don't know what to believe.*

Stick to believing we've worked out why the pay as you go business model works so well in the developing country context, the complex adaptive systems of trade are documentable and visible, and definitely not as chaotic and random as researchers would have you believe.

posted by infini at 2:57 AM on January 28, 2018

>

If you know my algorithm and my seed, then you can generate the same output as I do with 100% accuracy, so this indeed does not seem very random to me. If you use a more random seed, then you have to include the size of the program for generating that seed as part of your algorithm. If it's based on the current time, then the program for calculating the current time is quite large. If I assume that the time at which the program is ran is given, it's once again no better than having a static seed. A pseudorandom algorithm is only as random as the method for generating its seed, and so you have companies like CloudFlare using a wall of lava lamps, which can be said to be quite random.

posted by I-Write-Essays at 3:22 AM on January 28, 2018 [2 favorites]

*Doesn't this mean that most practical pseudo-random number generators have extremely low randomness?*If you know my algorithm and my seed, then you can generate the same output as I do with 100% accuracy, so this indeed does not seem very random to me. If you use a more random seed, then you have to include the size of the program for generating that seed as part of your algorithm. If it's based on the current time, then the program for calculating the current time is quite large. If I assume that the time at which the program is ran is given, it's once again no better than having a static seed. A pseudorandom algorithm is only as random as the method for generating its seed, and so you have companies like CloudFlare using a wall of lava lamps, which can be said to be quite random.

posted by I-Write-Essays at 3:22 AM on January 28, 2018 [2 favorites]

*Or, like random.org, atmospheric noise.*

...so you have companies like CloudFlare using a wall of lava lamps, which can be said to be quite random.

posted by lumensimus at 3:50 AM on January 28, 2018 [2 favorites]

*If you know my algorithm and my seed, then you can generate the same output as I do with 100% accuracy, so this indeed does not seem very random to me.*

I think randomness is a statistical measure of the distribution of values in the output, for pseudo-random number generators, and has nothing to do with a guarantee that the values are generated in a non-deterministic way.

posted by thelonius at 5:14 AM on January 28, 2018

wow

posted by stinkfoot at 5:41 AM on January 28, 2018 [1 favorite]

posted by stinkfoot at 5:41 AM on January 28, 2018 [1 favorite]

>

If you restrict yourself to first-order reasoning, having your output fit a Gaussian distribution may be enough, but at a second order, where you consider the ensemble of ensembles, that distribution is concentrated at a single point, unless you also include non-determinism. This is the difference between weak (pseudo-) randomness and strong randomness, which should be random at all orders.

posted by I-Write-Essays at 6:08 AM on January 28, 2018 [1 favorite]

*"I think randomness is a statistical measure of the distribution of values in the output, for pseudo-random number generators, and has nothing to do with a guarantee that the values are generated in a non-deterministic way."*If you restrict yourself to first-order reasoning, having your output fit a Gaussian distribution may be enough, but at a second order, where you consider the ensemble of ensembles, that distribution is concentrated at a single point, unless you also include non-determinism. This is the difference between weak (pseudo-) randomness and strong randomness, which should be random at all orders.

posted by I-Write-Essays at 6:08 AM on January 28, 2018 [1 favorite]

*that distribution is concentrated at a single point,*

Do you mean that if everything fits a Gaussian curve, it's not properly random? Because there are plenty of physically random non-deterministic systems that exhibit that (or exponential curves, or whatever). Non-determinism doesn't imply equal distribution of state transition over possible space: ask a lump of uranium. Any 'random' system, pseudo or not, abides by rules, whether they're set by physics or intellect, and determinism or non-determinism may not be important or even detectable in whatever you measure as output quality.

Or am I misunderstanding you?

posted by Devonian at 6:31 AM on January 28, 2018

What I'm suggesting is that just fitting a Gaussian distribution is not sufficient for strong randomness. This condition, alone, can't distinguish between pseudorandomness and thermal noise. If you take the distribution of ensembles produced by a given pseudorandom algorithm and seed, it is not random. To be random at all orders, I think adding non-determinism is enough.

posted by I-Write-Essays at 6:38 AM on January 28, 2018

posted by I-Write-Essays at 6:38 AM on January 28, 2018

I'd like to amend what I said by not focusing so much on the specific distribution, since a gaussian distribution is not a thermal distribution. My point is not so much which distribution a pseudorandom algorithm produces, but the idea that strong randomness should continue to look random at higher orders.

posted by I-Write-Essays at 6:57 AM on January 28, 2018

posted by I-Write-Essays at 6:57 AM on January 28, 2018

I should clarify, I meant something along the lines of "power laws seem plausible [but have turned out to be mostly hype and bullshit]". It's hard to evaluate research especially when no one in science or science reporting has any particular incentive for honesty.

posted by vogon_poet at 7:59 AM on January 28, 2018

posted by vogon_poet at 7:59 AM on January 28, 2018

*Doesn't this mean that most practical pseudo-random number generators have extremely low randomness?*

As this example shows, randomness is a subjective concept, contingent on the prior knowledge of the observer. Given the seed, the entropy is zero. Without knowing the seed or the PRNG algorithm, the entropy is probably close to whatever distribution is being simulated. Knowing the PRNG algorithm, the entropy is probably a bit lower, depending on how much analysis of the algorithm has been done.

posted by Coventry at 8:18 AM on January 28, 2018 [3 favorites]

*some of it comes from "engineer's disease", there were a lot of physicists who would look at some interesting real world phenomenon, declare it equivalent to an Ising glass or something, derive some theorems, and then claim to have "solved" the problem, immensely annoying the actual scientists.*

also some of the biggest names in the field are extremely prone towards unjustified hype and ruthless self-promotion as well (not going to name names, but one of them starts with "Bara" and ends with "bási"). and there are a ton of papers that were just wrong.

it's obviously still an extremely important field of study, though. the problem is just that so many "universal" patterns of behavior in complex systems have turned out to be bullshit. at the same time, given what we can see about the world, it seems that there must be such patterns!

also some of the biggest names in the field are extremely prone towards unjustified hype and ruthless self-promotion as well (not going to name names, but one of them starts with "Bara" and ends with "bási"). and there are a ton of papers that were just wrong.

it's obviously still an extremely important field of study, though. the problem is just that so many "universal" patterns of behavior in complex systems have turned out to be bullshit. at the same time, given what we can see about the world, it seems that there must be such patterns!

Yeah I'm going to read this stuff and give it a fair chance, but I'm mindful of (for example) the number of systems biology papers I've read where some algorithm vomited out a big graph of gene interaction spaghetti with nothing to back it up. As you say there can be engineer's disease among physicists and mathematicians - there can also be fear of maths among biologists (including reviewers and editors) that lets this stuff be published without understanding its limitations. That Barabási Nature Biotechnology paper that I presume you're alluding to is a classic example.

posted by kersplunk at 9:24 AM on January 28, 2018 [3 favorites]

They had me at chicken eyes and Alhambra tile patterrns but, left me with my shoe soles melting through the doorsteps of infinity.

posted by Oyéah at 10:15 AM on January 28, 2018 [4 favorites]

posted by Oyéah at 10:15 AM on January 28, 2018 [4 favorites]

*Doesn't this mean that most practical pseudo-random number generators have extremely low randomness?*

As this example shows, randomness is a subjective concept, contingent on the prior knowledge of the observer. Given the seed, the entropy is zero.

As this example shows, randomness is a subjective concept, contingent on the prior knowledge of the observer. Given the seed, the entropy is zero.

This is confusing. Kolmogorov complexity defines randomness of strings as having to do with

*existence*of a Turing machine, and that's objective. It's

*information*that's subjective. And this is ignoring all the confusing debates about how people conceptualize probability and randomness, like the sleeping beauty paradox, etc.

posted by polymodus at 11:57 AM on January 28, 2018

A bit into the article I knew I'd read it before. Was it on the blue previously?? Second time around, still a nice read and thanks, OP, for some rainy day links.

Re: random numbers. I remember hearing a story about an advertisement tucked into the back of a science journal in 60's. It offered a thousand random numbers for $5 or something like that -- an inviting offer, given the technology of the day. Behind the ad was an entrepreneurial student staying late to sweep up the computer labs, collecting piles of discarded chads from the computer punch cards. For your money you'd get an envelope filled with a scoop full of the teensy tiny numbers.

Re: buses and math. The anecdote about the professor in Cuernavaca reminded me of my time in Russia, boarding a bus in Krasnoyarsk with some friends. As they showed me the numbers on a standard Russian bus ticket, they explained that a common superstition held that if the sum of the first three numbers on your ticket equaled the sum of the last three numbers on your ticket, good luck was coming your way. Now, we might not have been calculating eigenvalues and random matrices at the bus stop, but we were definitely cutting our teeth on some probability calculations, trying to quantify our chances of having a lucky day.

And, from someone who is enjoying this article (and the smart MeFi comments) as a pleasant diversion from some grinding Sunday-afternoon-have-to-do-it-before-my-job-tomorrow math, let me say that there's not much sweeter than spontaneous bus-math.

posted by Theophrastus Johnson at 12:04 PM on January 28, 2018 [3 favorites]

Re: random numbers. I remember hearing a story about an advertisement tucked into the back of a science journal in 60's. It offered a thousand random numbers for $5 or something like that -- an inviting offer, given the technology of the day. Behind the ad was an entrepreneurial student staying late to sweep up the computer labs, collecting piles of discarded chads from the computer punch cards. For your money you'd get an envelope filled with a scoop full of the teensy tiny numbers.

Re: buses and math. The anecdote about the professor in Cuernavaca reminded me of my time in Russia, boarding a bus in Krasnoyarsk with some friends. As they showed me the numbers on a standard Russian bus ticket, they explained that a common superstition held that if the sum of the first three numbers on your ticket equaled the sum of the last three numbers on your ticket, good luck was coming your way. Now, we might not have been calculating eigenvalues and random matrices at the bus stop, but we were definitely cutting our teeth on some probability calculations, trying to quantify our chances of having a lucky day.

And, from someone who is enjoying this article (and the smart MeFi comments) as a pleasant diversion from some grinding Sunday-afternoon-have-to-do-it-before-my-job-tomorrow math, let me say that there's not much sweeter than spontaneous bus-math.

posted by Theophrastus Johnson at 12:04 PM on January 28, 2018 [3 favorites]

In the context of cryptography at least, a secure PRNG is designed to not leak information about its internal state, so an attacker doesn't have a way to predict the next value or recover the seed. If you break that assumption you can usually break the encryption.

But if you have a simple PRNG that's used in a videogame you can probably extract the seed just by observing it.

A secure PRNG and a completely insecure one probably have about the same Kolmogorov complexity though, other than the secure one having a more sophisticated algorithm.

posted by BungaDunga at 12:11 PM on January 28, 2018 [1 favorite]

But if you have a simple PRNG that's used in a videogame you can probably extract the seed just by observing it.

A secure PRNG and a completely insecure one probably have about the same Kolmogorov complexity though, other than the secure one having a more sophisticated algorithm.

posted by BungaDunga at 12:11 PM on January 28, 2018 [1 favorite]

*...a thousand random numbers for $5 or something like that*

For free, you can have A Million Random Digits with 100,000 Normal Deviates

posted by thelonius at 12:14 PM on January 28, 2018

*This is confusing. Kolmogorov complexity defines randomness of strings as having to do with existence of a Turing machine, and that's objective. It's information that's subjective*

Sorry, I did mean information-theoretic entropy, but you're right that what I said is basically useless without clarifying what that is.

*And this is ignoring all the confusing debates about how people conceptualize probability and randomness, like the sleeping beauty paradox, etc.*

Those never amount to anything once you nail down what you're trying to accomplish.

posted by Coventry at 12:33 PM on January 28, 2018 [1 favorite]

One of the authors mentioned in the bootstrap article is Mefi’s Own, although I suspect he is being more useful on a Sunday and thus not reading this thread. The “bootstrap” they use relies on restricting to a set of theories that are “conformal” (That is, more or less, they look the same at any scale), and then exploiting that property to turn the problem of studying theory space into an optimization problem that can be done numerically.

I’d also say that the physics development in field theory more directly related to random matrices is the Sachdev-Ye-Kitaev (SYK model). It is really an ensemble of models, each with a bunch of fermions whose interaction strengths are drawn from some distribution. The ensemble model is thus solvable, so physicists have been using it as a toy model a lot in the past couple of years. I can’t find a good popular-press article about it though, but maybe someone else knows of one.

posted by nat at 12:43 PM on January 28, 2018 [1 favorite]

I’d also say that the physics development in field theory more directly related to random matrices is the Sachdev-Ye-Kitaev (SYK model). It is really an ensemble of models, each with a bunch of fermions whose interaction strengths are drawn from some distribution. The ensemble model is thus solvable, so physicists have been using it as a toy model a lot in the past couple of years. I can’t find a good popular-press article about it though, but maybe someone else knows of one.

posted by nat at 12:43 PM on January 28, 2018 [1 favorite]

>

In case anyone is curious about the issues with said paper, you could do worse than starting with Lior Pachter &al's biting critique (discussed previously here with contributions from Pachter's coauthor Bray).

posted by Westringia F. at 12:46 PM on January 28, 2018

*That Barabási Nature Biotechnology paper that I presume you're alluding to is a classic example.*In case anyone is curious about the issues with said paper, you could do worse than starting with Lior Pachter &al's biting critique (discussed previously here with contributions from Pachter's coauthor Bray).

posted by Westringia F. at 12:46 PM on January 28, 2018

*I meant something along the lines of "power laws seem plausible [but have turned out to be mostly hype and bullshit]*

Oh my goodness. I don't know much about this area but I'm reading a book called "Scale" by physicist Geoffrey West. Power laws are a central theme. So I would really like to know where the hype and b.s. lie. One example is the Richardson thesis that the casualties from wars throughout history follow a power-law distribution. What's the verdict on that? Another example is city sizes. I was already a little suspicious of that because I checked the population of cities in China and they are obviously not power law distributed.

posted by storybored at 1:11 PM on January 28, 2018

> but maybe someone else knows of one.

This got 2,407 views, so it's popular enough, right?

also

posted by I-Write-Essays at 1:13 PM on January 28, 2018

This got 2,407 views, so it's popular enough, right?

also

posted by I-Write-Essays at 1:13 PM on January 28, 2018

Something that interests me is the fact that just a day or so ago, my brother (who lives in a different area of the country, works in an entirely different field, and is not on this site) sent me a link to an article about quasicrystals. Something something about synchronicity, informal networks, quasicrystal bubble, etc.

Yeah, I want to know what the game-theory and behavioral-economics implications are of all of this. The bus-driver problems are more interesting for me right now than the materials-science implications, because I can do something with the behavioral part of that set of info, whereas I can only marvel and admire the work being done in the realms of materials science or evolutionary biology. Behaviorism was always one of the more interesting areas of psychology for me, and right now I would be interested in anything that stems from that in relation to this, because what it reminds me of is the way informal networks grow, people learn from each other, and behavior spreads.

It seems like part of why scrum works well as a set of practices is that it's a simple system that is balanced out or normalized by self-organization, governed by specific rules. But when you have an organization large enough to have multiple scrum teams and informal and formal relationships between members of those teams, the dynamics of that become much more interesting and perhaps much harder to predict. It makes me wonder whether anyone can point me to studies that predict the behavior of groups and of individuals in complex systems like that, perhaps as related to any of the above. I wonder if anything came out of the studies of corpuses like the Enron emails, for instance, that would be related to or explained by some of these phenomena. I wonder what the threshold of complexity is for systems' ability to exhibit universality.

posted by limeonaire at 1:27 PM on January 28, 2018 [1 favorite]

*My own choice of complex adaptive system is the value web of informal trade created by established traders - demand, supply, support services such as transport & forex, and various other relationships of trusted give and take as the basic microsystem or node in the more complex regional trading ecosystem as is prevalent in developing countries such as those in the East African Community. The fact that its more human, less technologically and infrastructurally mediated means that the intuition that the scientists are missing in their random numbers is that which makes us human i.e. the patterns of human give and take make it easier to see the complex whole and undertand it in a way tht perhaps a matrix may not offer.*Yeah, I want to know what the game-theory and behavioral-economics implications are of all of this. The bus-driver problems are more interesting for me right now than the materials-science implications, because I can do something with the behavioral part of that set of info, whereas I can only marvel and admire the work being done in the realms of materials science or evolutionary biology. Behaviorism was always one of the more interesting areas of psychology for me, and right now I would be interested in anything that stems from that in relation to this, because what it reminds me of is the way informal networks grow, people learn from each other, and behavior spreads.

*In many simple systems, individual components can assert too great an influence on the outcome of the system, changing the spectral pattern. With larger systems, no single component dominates. “It’s like if you have a room with a lot of people and they decide to do something, the personality of one person isn’t that important,” Vu said.*It seems like part of why scrum works well as a set of practices is that it's a simple system that is balanced out or normalized by self-organization, governed by specific rules. But when you have an organization large enough to have multiple scrum teams and informal and formal relationships between members of those teams, the dynamics of that become much more interesting and perhaps much harder to predict. It makes me wonder whether anyone can point me to studies that predict the behavior of groups and of individuals in complex systems like that, perhaps as related to any of the above. I wonder if anything came out of the studies of corpuses like the Enron emails, for instance, that would be related to or explained by some of these phenomena. I wonder what the threshold of complexity is for systems' ability to exhibit universality.

posted by limeonaire at 1:27 PM on January 28, 2018 [1 favorite]

storybored:

The link that vogon_poet posted above discusses power law b.s., if you haven't already followed it. It doesn't give you the tools to tell what's hype unless you have access to the original data, though, which I suspect will always be the case.

posted by clawsoon at 1:31 PM on January 28, 2018

*Power laws are a central theme. So I would really like to know where the hype and b.s. lie.*The link that vogon_poet posted above discusses power law b.s., if you haven't already followed it. It doesn't give you the tools to tell what's hype unless you have access to the original data, though, which I suspect will always be the case.

posted by clawsoon at 1:31 PM on January 28, 2018

>

This sounds like a property of thermal systems. However, human social networks contain supernodes, and phenomena such as the Friendship Paradox, and Majority Illusion, so I'm not sure it should behave the same way.

>

Is this the kind of thing you're thinking of?

The Social-Network Illusion That Tricks Your Mind

The "Majority Illusion" in Social Networks

posted by I-Write-Essays at 1:38 PM on January 28, 2018 [1 favorite]

*With larger systems, no single component dominates.*This sounds like a property of thermal systems. However, human social networks contain supernodes, and phenomena such as the Friendship Paradox, and Majority Illusion, so I'm not sure it should behave the same way.

>

*It makes me wonder whether anyone can point me to studies that predict the behavior of groups and of individuals in complex systems like that, perhaps as related to any of the above.*Is this the kind of thing you're thinking of?

The Social-Network Illusion That Tricks Your Mind

The "Majority Illusion" in Social Networks

posted by I-Write-Essays at 1:38 PM on January 28, 2018 [1 favorite]

The Technology Review article even mentions the Power Law, for extra points.

posted by I-Write-Essays at 1:46 PM on January 28, 2018

posted by I-Write-Essays at 1:46 PM on January 28, 2018

Yessssss, and that

posted by limeonaire at 1:58 PM on January 28, 2018 [2 favorites]

*PLoS One*paper references use of an Erdős-Rényi model, which is one of the things mentioned (PDF) in the initial*Quanta*link as an example of where the universality pattern can be seen. More of that, please! Thank you, I-Write-Essays.posted by limeonaire at 1:58 PM on January 28, 2018 [2 favorites]

Wait, wait, wait, you're telling me this paper about [Paul] Erdős-Rényi models, has as it's first author one László Erdős, who as far as I can tell, is also a Hungarian mathematician, but bears no direct relation to Paul Erdős? I was confused at first that Paul Erdos could have published anything in 2011, a decade and a half after his death, but it's even stranger than that! What is this man's Erdős Number?

posted by I-Write-Essays at 2:14 PM on January 28, 2018 [4 favorites]

posted by I-Write-Essays at 2:14 PM on January 28, 2018 [4 favorites]

This thread is really bringing out MathMetafilter, and I'm here for it.

posted by latkes at 2:18 PM on January 28, 2018 [3 favorites]

posted by latkes at 2:18 PM on January 28, 2018 [3 favorites]

Oh, yay! I work on the bootstrap research mentioned in the last article. It is a lot of fun because it sits right at the intersection of high energy physics and condensed matter physics. It connects to systems in the real world (e.g., the liquid-vapor critical point of water and phase transitions in magnets) so there is lots of experimental data, but viewed in a different way it also teaches us things about how to put together consistent theories of quantum gravity using the holographic "AdS/CFT correspondence".

The research involves studying theoretical "bootstrap" equations whose solutions tell us all the different ways systems can be independent of scale (i.e., zooming in or out) and still be theoretically consistent. It turns out that seemingly different systems, such as boiling water and hot magnets, can have precisely the *same behavior* when they undergo phase transitions, so we really just need to find the different "universality classes" that are possible. But the bootstrap equations are so complicated that to explore the space of solutions we need high performance computing and efficient numerical algorithms. In any case, a tremendous amount of progress studying these equations has been made in the last few years and (in my opinion) it is one of the most exciting research programs in theoretical physics right now.

posted by Poegar Tryden at 3:45 PM on January 28, 2018 [6 favorites]

The research involves studying theoretical "bootstrap" equations whose solutions tell us all the different ways systems can be independent of scale (i.e., zooming in or out) and still be theoretically consistent. It turns out that seemingly different systems, such as boiling water and hot magnets, can have precisely the *same behavior* when they undergo phase transitions, so we really just need to find the different "universality classes" that are possible. But the bootstrap equations are so complicated that to explore the space of solutions we need high performance computing and efficient numerical algorithms. In any case, a tremendous amount of progress studying these equations has been made in the last few years and (in my opinion) it is one of the most exciting research programs in theoretical physics right now.

posted by Poegar Tryden at 3:45 PM on January 28, 2018 [6 favorites]

Three decades into his decorated career, the researcher made a startling admission: All of his scale-free networks had been achieved with the help of CLR. "I was watching TV one afternoon when the commercial came on and I realized how easy it would be to get rid of scale by soaking my networks for a few minutes. It cleaned the rust right up, too. I deeply regret misleading the scientific community into thinking that all of my results were achieved solely using math."posted by clawsoon at 11:05 PM on January 28, 2018 [4 favorites]

*And this is ignoring all the confusing debates about how people conceptualize probability and randomness, like the sleeping beauty paradox, etc.*

Those never amount to anything once you nail down what you're trying to accomplish.

Those never amount to anything once you nail down what you're trying to accomplish.

But that was my point, because that section on Wikipedia has zero citations, uses hedge words and then literally allows at the end that it's not a settled issue. It comes across as pretty dismissive to suggest that philosophers' and theorists' issues don't amount to anything once they use the "proper" (read: standard dogma) concepts. It's an intellectual divide that's not really acknowledged.

posted by polymodus at 11:45 PM on January 28, 2018 [1 favorite]

*tirutiru, given my last college course was in the 1980s, would I be wrong in thinking this is similar to bell curve behaviour and outcomes? i.e. similar span of applicability with a similar diagrammatic explanation?*

Similar only in the sense that the bell curve is a probability distribution too. Its ubiquity is explained by the central limit theorem - if you take a bunch of uncorrelated random numbers then the sum approaches a bell curve.

The post deals with the eigenvalue spectrum of a large matrix - roughly, the scale factors by which it stretches space in certain directions. We can't say much about a single eigenvalue of a small random matrix - but if the dimension is large enough, patterns emerge...

(pop explanations make this stuff seem easier and more widely applicable than it perhaps is, but that's the nature of things)

@

**Poegar Tryden**

A small correction. The boiling phase transition is first order so conformal symmetry/bootstrap etc. do not apply (?)

posted by tirutiru at 12:10 AM on January 29, 2018 [1 favorite]

Well, yes, the water needs to be boiled at the critical pressure (about 218 atmospheres) in order to have a continuous phase transition and pass through the liquid-vapor critical point, but I was trying to keep my explanation brief. :)

posted by Poegar Tryden at 1:04 AM on January 29, 2018

posted by Poegar Tryden at 1:04 AM on January 29, 2018

**limeonaire**, to your questions, I would only add the caveat that I'd look at them having distinguished informal networks in developed country (high tech & infrastructure) from informal networks in less developed conditions.

*because what it reminds me of is the way informal networks grow, people learn from each other, and behavior spreads.*

Culture also matters. For instance informal groups for savings and working capitals are not as prevalent in highly individualist and advanced cultures such as the USA, unlike say rural Kenya.

So, context matters greatly in working out progressive transformation evolution of a microsystem of trade in East Africa versus what passes for SMEs in the US.

posted by infini at 3:16 AM on January 29, 2018 [1 favorite]

*For example if the matrix is perturbed (randomly) and some eigenvalue moves a bit, then the neighbouring eigenvalues tend to make way by moving away from it.*

OK, this was the missing piece. Thanks for this explanation.

If you play around with this toy, you can see a similar repulsion effect in the roots of a polynomial as you move around the coefficients. Maybe they are the same effect, as the matrix perturbation is of course also perturbing the matrix's characteristic polynomial.

posted by Jpfed at 5:48 AM on January 29, 2018

Poegar Tryden, Poetry Garden...interesting.

posted by Oyéah at 9:17 AM on January 29, 2018 [2 favorites]

posted by Oyéah at 9:17 AM on January 29, 2018 [2 favorites]

Wow, that’s probably the first time anyone has ever correctly identified the source of his user name! It’s an inside joke from when we first started dating and passed by a gate that read:

POE | TRY

GAR | DEN

I joked that it made a good barbarian warrior name and it’s been kicked around in various forms for over a decade since.

Probably says something about us when he’s the one with the “poetic” username, while I have the mathy one.

posted by Diagonalize at 10:52 AM on January 29, 2018 [1 favorite]

POE | TRY

GAR | DEN

I joked that it made a good barbarian warrior name and it’s been kicked around in various forms for over a decade since.

Probably says something about us when he’s the one with the “poetic” username, while I have the mathy one.

posted by Diagonalize at 10:52 AM on January 29, 2018 [1 favorite]

*But that was my point, because that section on Wikipedia has zero citations, uses hedge words and then literally allows at the end that it's not a settled issue.*

What I took from that section is that the answer depends on the loss function. To me it seems to make that point in a very precise way, which does not need to depend on an appeal to authority.

*It comes across as pretty dismissive to suggest that philosophers' and theorists' issues don't amount to anything once they use the "proper" (read: standard dogma) concepts. It's an intellectual divide that's not really acknowledged.*

I'm always grateful to learn of useful perspectives from philosophers and theorists. I haven't found much in philosophical discussions of randomness. I do love Gelman & Shalizi's Philosophy and the practice of Bayesian statistics, though arguably they are practitioners indulging in theory and philosophy, there.

posted by Coventry at 12:10 PM on January 29, 2018

Can anyone help me get more of how hyperuniformity relates to a Poisson disk distribution? At the level given in the Quanta article it seems like Poisson disk would be an example.

Like in the "tossing a ring" explanation, doesn't the "variation in number is proportional to the ring's area" come from the fact that uniform noise has some large spatial scale in it? Whereas Poisson disk filters out around DC, so it seems it would meet the criterion.

(Or is there something about hyperuniformity that's being talked about, more than just an example of a distribution?)

posted by away for regrooving at 12:05 AM on January 30, 2018

Like in the "tossing a ring" explanation, doesn't the "variation in number is proportional to the ring's area" come from the fact that uniform noise has some large spatial scale in it? Whereas Poisson disk filters out around DC, so it seems it would meet the criterion.

(Or is there something about hyperuniformity that's being talked about, more than just an example of a distribution?)

posted by away for regrooving at 12:05 AM on January 30, 2018

« Older Consciousness and Conscience | “We have to be twice as careful when talking about... Newer »

This thread has been archived and is closed to new comments

posted by J.K. Seazer at 9:41 PM on January 27, 2018 [3 favorites]