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

161–170 of 178 posts

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

#161

Post by sgillen »

Ar-Curunir wrote: post #157
fallingknife wrote: post #134

Earlier quoted context omitted.

DEI efforts discriminate against Asians like Jinyoung, so yes, I will shit on them.

Not. Necessarily, given that DEI efforts are not one-dimensional. They consider factors like first-generation, geneder, class background, etc. (I am an Asian male, so I really have nothing to selfishly benefit from promoting DEI efforts)

Well, one problem when discussing DEI is there are many implementations of it. My own own departments only considers race or gender, and really only focuses on gender. Although I know many DEI programs really do take a more holistic view of what diversity means.

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

#162

Post by _8j50 »

oh_my_goodness wrote: post #154
_8j50 wrote: post #147

Earlier quoted context omitted.

Thank you, my original comment was for ELI5, I was asking because I didn't know and clarifying like this helps. Wouldn't it be more correct to say arbitrary instead of random?

I think random is often used as a keyword that means "use ideas from probability." Those ideas are tricky and (I think) not well captured by any one word. Example of a tricky situation: Say we play cards. You shuffle the cards well, and you don't show them to me. I might say the order of the deck is random , to indicate that I have no idea which card is in what position. But you might be looking at the faces of the c…

I agree, but in crypto for example they use the term "cryptographically random" as in for the purposes of computing it is not possible to predict the value.

As a complete outsider to the field, I had no idea what is meant by random in a mathematical sense because I thought math was always realistic, as in it mirrors real things, you can't have 2+2=3 because reality doesn't work that way.

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

#163

Post by less_less »

rurban wrote: post #102

As I already commented in the first submission of this article: Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh. This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements wi…

Huh, I was thinking the same thing about a related problem: compressed static maps by solving sparse matrices: https://docs.rs/compressed_map/0.1.0/compressed_map/

To get a concrete bound though, you'd probably need to know what is K.

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

#164

Post by lupire »

scheme271 wrote: post #58
ineptech wrote: post #40

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 mo…

I think it's slightly different. Consider this problem instead, what's the chances of two people sharing the same birthday in a group. It's (365 364 ...*(365-n+1))/(365^n). If you plot this out, it increases exponentially. At n=23 it's about 50%. At around 60, it's a bit more than 99%. It's similar to the other problems, where a given condition can have an arbitrarily high chance of being present at surprisingly low…

That's sigmoid (starts exponential and then smoothly changes into an asymptotically constant)

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

#167

Post by lupire »

ThinkBeat wrote: post #105

I notice that most links on physics, astronomy and math cover pre-prints. Would it not be prudent to wait for the final version. Is all the peer reviews and "fact checking" done prior to the preprint?

Publications don't check facts. They just check formatting and interestingness and plausibility. Peer review is totally separate, not part of publication's pseudo "peer review".

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

#168

Post by lupire »

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…

Knowing that true things are obviously true is easy. The difference between naive and professional mathematician is the ability to be precise enough to avoid knowing that false things are "obviously true".

To wit, what you stated is not De Morgan's law.

> De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic

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

#169

Post by sharpener »

Maybe someone familiar with the graph theory math can help me.

I don't understand why these properties aren't numerically accessible. Why is the estimation necessary?

E.g. Assume N nodes, and edges E can be created at random with redundancy (picking same edge e twice just keeps the prior edge) by picking pairs of points.

Assume N random edge picks are made, then the probability of e.g. a Hamiltonian cycle appearing in those N picks can be calculated.

(My quick back of envelope sketch says P(H-cycle) = N! / N^N , but please consult the expert literature.)

But one can also calculate the probability of a H-cycle given N+1 random picks, N+2 random picks, ... and that appears as = P(H-cycle) * (1 + extra factors that account for increases in other edges not redundantly in the H-cycle)

(Again, my back of envelope sketch for N + 2 picks gives: = P(H-cycle) * ( 1 + 2/(N-1)[N - 3 - 1/N]) , but please consult the expert literature.)

These probabilities would seem to tell a user that given a graph with N nodes and E edges, that if e.g. in the H-cycle case, E > N the user can get an explicit probability for the likelihood of a H-cycle being present.

Are there graph properties that prevent this approach being viable?

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

#170

Post by feral »

scoot wrote: post #112
feral wrote: post #86

Earlier quoted context omitted.

And, to give an example we've probably all become familiar with, this this is equivalent to how a disease becomes an epidemic as the R value crosses 1.

That seems more like a truism: If on average one case leads to more than one other (R > 1), the number of cases will grow. The R number therefore appears to be nothing more than a measure of growth or decline. What am I missing?

What I mean is that R varies by disease (or for a given disease, according to interventions, etc).

The size of the total epidemic varies sharply as R is changed in this way.

Post reply on HN