Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Elegant six-page proof reveals the emergence of random structure

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 178 posts

Re: Elegant six-page proof reveals the emergence of random structure

#31

Post by thomasahle »

thaumasiotes wrote: post #28
thomasahle wrote: post #7

Earlier quoted context omitted.

The interesting thing a out graph properties (like the emergence of connectivity, giant components, Hamiltonian paths etc.) is that they happen as "phase transitions". A classic example is cuckoo hashing: You want to know how many edges the random graph of hashes can have before it contains a cycle, since that's when you need to rehash into a larger table. You might expect that this number is "pretty random" in that…

> However it turns out that it very predictably happens exactly when the graph gets to a certain size. In the same way as 1000 coin flips very predictably have 450-550 heads. > What's so cool about the theorem is thst it proves _any_ property you can think of has _some_ sudden threshold like that. ...like what? The example you give, of the number of heads yielded from 1000 coin flips, doesn't have a sudden threshold…

You are right. We have to define the notion of sudden. It works like this: As n goes to infinity you have 100% chance of 49% heads or more, but 0% chance of 51% or more.

Re: Elegant six-page proof reveals the emergence of random structure

#32

Post by Cerium »

thaumasiotes wrote: post #28
thomasahle wrote: post #7

Earlier quoted context omitted.

The interesting thing a out graph properties (like the emergence of connectivity, giant components, Hamiltonian paths etc.) is that they happen as "phase transitions". A classic example is cuckoo hashing: You want to know how many edges the random graph of hashes can have before it contains a cycle, since that's when you need to rehash into a larger table. You might expect that this number is "pretty random" in that…

> However it turns out that it very predictably happens exactly when the graph gets to a certain size. In the same way as 1000 coin flips very predictably have 450-550 heads. > What's so cool about the theorem is thst it proves _any_ property you can think of has _some_ sudden threshold like that. ...like what? The example you give, of the number of heads yielded from 1000 coin flips, doesn't have a sudden threshold…

In the coin flip scenario, the intrinsic properties of a coin result in a threshold of 50% which above a certain scale, is very "sharp" or sudden in the transition. Compare this to a hash table or queuing theory, where a certain amount of capacity works well up to a certain point, then it falls apart. If you can design a random test which will display that property, then you can determine it before the fact without having a way to directly calculate that property, like we do for coin tosses.

Re: Elegant six-page proof reveals the emergence of random structure

#33

Post by Sniffnoy »

plaguepilled wrote: post #27

Here's a direct link to the preprint if you want to skip the fluff: https://arxiv.org/abs/2203.17207

Hm, they prove the existence of a K, but don't put any explicit bounds on it. Someone's going to have to proof-mine this one...

Re: Elegant six-page proof reveals the emergence of random structure

#34

Post by thaumasiotes »

da39a3ee wrote: post #23
tsunamifury wrote: post #2

Can someone explain to my why proving random graphing can produce known shapes is important? Because this seems absurdly obvious to any layman. Why is this a complex proof? I’m guessing it’s more that they proved the thresholds for these shapes being formed more than why?

If you think something is absurdly obvious you usually need to re-read what you've read.

No. It's not that rare for absurdly obvious things to get published to great fanfare.

I'm still bitter about "De Morgan's Laws". There are two of them:

1. If two things are not both true, then one or more of them is false.

2. If neither of two things is true, then both of them are false.

Of course this is obvious to everyone. Writing it down did not merit having it named after yourself. I guarantee many other people had also written it down earlier.

Re: Elegant six-page proof reveals the emergence of random structure

#37

Post by thehappypm »

thaumasiotes wrote: post #34
da39a3ee wrote: post #23

Earlier quoted context omitted.

If you think something is absurdly obvious you usually need to re-read what you've read.

No. It's not that rare for absurdly obvious things to get published to great fanfare. I'm still bitter about "De Morgan's Laws". There are two of them: 1. If two things are not both true, then one or more of them is false. 2. If neither of two things is true, then both of them are false. Of course this is obvious to everyone. Writing it down did not merit having it named after yourself. I guarantee many other people…

Obligatory xkcd: https://xkcd.com/2042/

Re: Elegant six-page proof reveals the emergence of random structure

#38

Post by thaumasiotes »

thehappypm wrote: post #37
thaumasiotes wrote: post #34

Earlier quoted context omitted.

No. It's not that rare for absurdly obvious things to get published to great fanfare. I'm still bitter about "De Morgan's Laws". There are two of them: 1. If two things are not both true, then one or more of them is false. 2. If neither of two things is true, then both of them are false. Of course this is obvious to everyone. Writing it down did not merit having it named after yourself. I guarantee many other people…

Obligatory xkcd: https://xkcd.com/2042/

The art museum visitor would be unambiguously correct in the case of De Morgan's laws. Rolle's Theorem depends on some fairly tricky setup work.

But for an even more obvious theorem that was actually difficult to prove (Rolle's theorem isn't), see https://en.wikipedia.org/wiki/Jordan_curve_theorem

("Any path which begins in the interior of a closed curve, and ends in the exterior of the same curve, must cross the curve at some point.")

Re: Elegant six-page proof reveals the emergence of random structure

#39

Post by yesenadam »

thaumasiotes wrote: post #38
thehappypm wrote: post #37

Earlier quoted context omitted.

Obligatory xkcd: https://xkcd.com/2042/

The art museum visitor would be unambiguously correct in the case of De Morgan's laws. Rolle's Theorem depends on some fairly tricky setup work. But for an even more obvious theorem that was actually difficult to prove (Rolle's theorem isn't), see https://en.wikipedia.org/wiki/Jordan_curve_theorem ("Any path which begins in the interior of a closed curve, and ends in the exterior of the same curve, must cross the cur…

From that link:

"The first formal proof of the Jordan curve theorem was created by Hales in the HOL Light system, in January 2005, and contained about 60,000 lines. Another rigorous 6,500-line formal proof was produced in 2005 by an international team of mathematicians using the Mizar system. Both the Mizar and the HOL Light proof rely on libraries of previously proved theorems, so these two sizes are not comparable."

Re: Elegant six-page proof reveals the emergence of random structure

#40

Post by ineptech »

I'm trying to visualize this. I go to Wolfram Alpha and type "chance of getting 504 heads in 1000 coin flips" and see the answer is about 1/40, and when I change 504 to 505 I see the odds are about 1/41 - only slightly worse.

Then I check the differences between 524 and 525 and I see that the odds are decreasing much more sharply (1/400, 1/459). The little graph they helpfully provided shows what's happening: I've moved from the flattish "top" of the Bernoulli distribution to the steepish "slope" of the distribution. And at larger numbers still, the differences between adjacent numbers become negligible again as I reach the flattish "trough" at the edge of the distribution. You could say that the top of the distribution has values that are all pretty similar to each other, the bottom values are also similar to each other, and sides are a region where small differences are comparatively much more important.

Is this roughly what the article means when it discusses thresholds? The rather sharp transition from "both pretty likely" to "the second one is a lot less likely" to "both pretty unlikely"? And if so, how sharply would the slope of the distribution have to change to qualify as being a threshold?

Post reply on HN