Comment by ineptech | Hacker News Reader

Comment by ineptech | Hacker News Reader

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?

The effect you're seeing on the coin flip is best understood by seeing that each coin flip is independent, and in no way connected to the past. So, the odds are based on a fair 50/50 per flip, which leaves you with a simple 2^n sample space of one of each binary combination for n flips. The math for that works out easily, and can be plotted.

The emergence of random structure in graphs, however, is different. The chance of a specific structure, such as a cycle of some length or a spanning tree of certain dimension, can go from not particularly likely (<20%) to significantly likely (95%+) in just a single additional node. Those transition thresholds at which the percentage changes in an intuitively surprising way are the subject matter of interest here.

Eh, the coins weren't important, that's just an easy thing for me to visualize. If one graphs that emergence -if one graphs the number of nodes in a graph against the chance of finding some structure in a graph of that size - I had imagined one would see a smooth curve like one half of a binomial distribution curve. It sounds like you're saying the graph would look discontinuous?

It's as continuous a want discrete function can be, but yes it has a region of explosive growth, sort of like a sigmoid.

Think of all the Jenga games. What is the probability of the tower collapsing on turn T (or T/H, for a tower of size H), graphed as a function of T (or T/H)?

Coins example would work here if he asked what are the odds of getting n of a/b in a row or how many n-length rows for few different ns in a number of flips.

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 (365364...*(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 graph sizes.

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

I don't think it's Bernoulli, binomial rather?

Reply on news.ycombinator.com