Reading that and then rereading the post, it all made a whole more sense: why the conjecture is intuitively appealing and why the computational approach doesn't readily result in a proof.
What did I miss?
P[nodes in upper bunk connected] > P[nodes in lower bunk connected] * P[sufficient "bedpost" edges survive connecting upper and lower]
Since
P[nodes in upper bunk connected] = P[nodes in lower bunk connected]
And by definition
P[sufficient "bedpost" edges survive connecting upper and lower]<1
In this example, a1 is connected to both c1 and c2:
a1 b1 -- c1
| | |
a2 -- b2 -- c2
Counter-factuals like this don't apply when talking about average probabilities. If you cross over, it's an identical graph with identical probabilities. idk, to me it seems really counter-intuitive that the opposite bunk's node would be easier to get to than the current bunk's node.
and (7253/15654)**(phi*pi)*100 ~ 2
haha :)
Could someone explain why the conjecture seemed obviously true? I have no background with it, but just reading the description here, I was caught off guard by the sentence. What made it seem obvious?
Because if it wasn't true then that would imply that V on different levels (as reached presumably by a canonical DFS tree // spanning tree) were closer (in terms of paths) than V on the same level, which would mean that those V should have "more likely" been on the same level (as however measured).
TL;DR - 'obviously true' because there's a level between them so (on average) of course!
To me it smells like a trap, though. This feels like exactly the kind of problem where some algorithmically chosen infinite graph would break the conjecture, possibly through some kind of NP-hardness-proof-style transformation of the problem into another form, and who knows, maybe the Axiom of Choice gets involved too (but probably not based on the headline!).
"A random subgraph of the bunkbed graph is then formed by independently deleting each edge based on the assigned probability."
So the (apparently incorrect) intuition is that an (upper<->lower) connection starts with an extra edge in the connection, so an (upper<->lower) connection has a greater risk of disconnect via random edge removal. Therefore, a same-level connection is more likely to remain after the random edge removal.
Ed: reflecting on my first sentence, I guess I tend to think of proofs as being at least as important a product of math as the raw truth of a statement. A fact is a fact, but a proof represents (some level of) understanding, and that's the good stuff. Experiments are potentially good science, but usually not math.
(As an aside, there's important distinction with statements that are believed to be true based on empirical evidence, such as hardness of factoring or the Riemann conjecture. If the bunkbed conjecture was refuted based on Monte Carlo simulations, it'd be possible to reduce the level of uncertainty arbitrarily low by throwing more resources at running more simulations.)
Often there are three useful states: none, some, and all. You describe a rigorous proof-of-some, because a proven probability of not-zero guarantees a counterexample exists. It's still news when or if the counterexample is found, but given the standard of rigorous proof is met, it does exist. Of course another option is to construct a counterexample, as was done here.
The case of probability discussed in the Fine Article was rigorously demonstrating a 99.99% chance that the probability is not zero. That's informative but it isn't proof. Proof that the probability is not zero, absent the counterexample which we now know (rather than expect on good grounds) exists, is also a proof. But that isn't the case being discussed here.
I think you mean an infinite set here. If I have a set containing one single coin, and I flip every coin in my set, both heads and tails have a non-zero probability to exist within my flipped set. But there's certainly not an example of both heads and tails in my single-coin set. Indeed for any finite set of coins, there's some chance that either heads or tails never shows up.
However, if I have an infinite set of coins and I flip them all, certainly both heads and tails must exist (although I wouldn't be surprised if even this depends on the axiom of choice or something.)
What you're saying about the infinite set version of GP's statement depends on what flavor of statistics you're measuring by. E.g. a frequentist approach would give the probability of something that occured 50 times out of \inf as 0 while other approaches may say a small non-0 probability.
Flipping an infinite set of coins is actually an inverse view of what's described above and not necessarily "certainly" even though the probability is 1 ("almost surely" rather than "certainly" is the wording) for the same reasons of a non-empty set not necessarily nudging the probabilities of an infinite sequence. The Wikipedia article explains this better than I could https://en.wikipedia.org/wiki/Almost_surely
Then you're wrong. I gave you a counterexample to your statement, which you have ignored. If you care about being correct on this, you should ruminate on my comments, because what you are currently saying is wrong.
> Probabilistic method
Neither example on that Wikipedia page shows proving the existence of something from a finite set because it's probability is non-zero.
The first example is actually showing that if the probability is zero from a finite set then there can be no examples. It's an example of #4 below. The critical point is "The number of monochromatic r-subgraphs... is a non-negative integer, hence it must be 0 (if strictly less than 1)." It's the inverse of your statement (and the contrapositive of mine, hence it has the same truth value): "if the probability of something existing in a finite set is 0, there must be no examples". That's very different!
The second example is from an infinite set. It's an example of #1 below The key sentence is: "For sufficiently large n, the probability that a graph has both properties is positive". We're given g and k as parameters to the problem, and we show that there exists some n, above which the probability of a random graph having the property we want is greater than 0. It is NOT proven that the graph we're looking for has exactly n vertices! It's only proven that random graphs of at least n nodes have a positive probability to have the property. The reason the proof works is because there are infinite numbers larger than n! It shows that there are infinite graphs that have non-zero probability to have the property we're looking for, and therefore at least one must actually exist.
Here's a list. Your incorrect claim is counter to #3.
1. Infinite set, nonzero probability: we know at least one example must exist.
2. Infinite set, zero probability: not sure! It could be zero, or any subset of smaller cardinality or measure zero.
3. Finite set, nonzero probability: not sure! It could be zero! My coin flip example shows this.
4. Finite set, zero probability: we know no examples can exist.
> if something exists with non-zero probability in a finite set there has to be at least one example
This is a false claim. See my #1 through #4 above. I strongly suspect if you carefully re-read those Erdos papers, you'll discover that he never relies on my #2 or #3 above to prove anything; only #1 and #4.
I think you are confusing this with the notion of taking repeated samples from a probability distribution (which is what your coin example is all about).
Question: do any finite sets ever have positive (nonzero) measure? If not, then your sample space is infinite and you're in #4. Haven't you just restricted our conversation only to infinite sets via this assumption? Remember that this entire discussion started because of your claim about finite sets!
There are also myriad examples of measures over infinite spaces in which there exist finite sets with positive measure - left as an exercise to the reader.
I don't mean this to be rude, but I think you would benefit from reading an undergraduate level textbook on probability theory (or measure theory). Especially before making confident claims about people like Erdos are wielding it.
I obviously don't know the intricate details of every possible measure that could be defined, but I strongly suspect that no matter what measure you pick, the following statement is utterly tautological: "If the set { x ∈ S | P(x) } has measure > 0, then there must exist some y in S s.t. P(y)". You're really just saying: if we can show that the subset of elements in S with property P contains at least one element, then S must also contain that element. Of course! It's a subset of S! It's tautological, and I don't believe Erdős threw in tautological steps in his proofs. You are misunderstanding what the proof step is.
We're talking about the Second example in this link: https://en.wikipedia.org/wiki/Probabilistic_method
It's structured like this: "Let n be very large and consider a random graph G on n vertices ... we show that with positive probability, G satisfies two properties." Let me ask: how are we mathematically certain there exists a graph G that satisfies the two properties? (And we are; the proof is correct.) Which of the 4 situations are we in? Your focus on finite sets makes it sound like we're in #3: finite set, nonzero probability. And indeed the set of random graphs with n vertices is finite! But that is an important mistake. We are not relying on argument #3. Yes, the set of random graphs with n vertices is finite, but we have NOT proven that any specific G has our two properties, and we have NOT proven that any graph with n vertices has those two properties! It's entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties.
You might encounter a similar proof, exactly the same up to this point, and that proof might be wrong! So why does Erdős's proof work? It relies on two things that are both necessary: (1) we're not talking about a finite set at all! We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here. Our smallest example might be of size 10^10^10^n! We don't know! We just know that if we keep going, eventually we must hit one. And, critically, (2) there is a positive lower bound on the probability, above some n (it's 1/2). That is, if the probability of a random subgraph having those two properties was some small nonzero probability that decreased as n increased, e.g. p ~ 1/n^2, then we still might never find an example! The proof could be incorrect! But it's shown that above some n, the probability is at least 1/2. Thus the whole proof works, because 1 - (1/2)^inf = 1. The sum of existence probabilities over all possible examples (infinite) is 1. QED.
So in summary, this statement:
> If a property P holds over a sample space with positive probability (i.e. the measure of the subset of elements satisfying P is positive), this implies that there is at least one element of the sample space satisfying P.
is either false or tautological.
If "positive probability" means proving that some elements in a finite sample space have a positive probability of satisfying P, you have not proven existence. You need to show that the sum of "existence probabilities" of all your examples is 1. Showing a positive probability on an infinite set does this (unless the sum of probabilities over all infinite examples somehow converges to a number < 1, e.g. if p ~ 1/n^2 above).
If "positive measure" means "we've proven such a thing exists", then it's tautological. All you've said is "if you can prove something exists in a subset of S, then it also exists in S." I guarantee you Erdős did not include such unnecessary tautologies in his proofs.
> if there is some finite set and there is a non-zero probability of something existing in it then there must be at least one _possible_ example of how this can occur
That is not what GP claimed nor does it really make sense. Yes, if there is a non-zero probability of something existing, then it must be possible. That is what non-zero probability means. That has nothing to do with sets. You've just added the word "possible" to make the claim vague enough to be not provably incorrect.
If you have a finite set, and you show that members of that set have a non-zero (but less than 1) probability of having some property, you do not know whether a member of the set actually has that property! Period! Why is this a point of contention?
> a frequentist approach would give the probability of something that occured 50 times out of \inf as 0 while other approaches may say a small non-0 probability.
No. Nobody would say that 50/infinity is greater than 0.
You haven't actually responded to the thing I actually said, nor really to GP's claim. The claim was:
>> if something exists with non-zero probability in a finite set there has to be at least one example
That is false. I gave an example of how it's false.
On finite sets, all the stuff they're saying doesn't make sense completely.
I'm not here to assert what GP meant with certainty (and neither should you?). Nor am I going to bother engaging further when you so blatantly end with how your troubles with the vagueness in your understanding of the what the claim meant lie in being unable to call it incorrect.
> No. Nobody would say that 50/infinity is greater than 0.
Nor did I claim that's how the other approaches come to calculate the probability greater than 0... again, what's the point in me engaging on this if your goal is to slap portions of text together until you find something to disagree with instead of actually engaging with me? A complaint about me not including how the alternative approaches come to a different conclusion would be more than a valid criticism (or even friendly probe, were you actually interested) but you're goal to make each response to anyone here start with "no", "incorrect", or "you're wrong" is apparently too driving to allow that kind of discussion.
> You haven't actually responded to the thing I actually said, nor really to GP's claim. The claim was... That is false. I gave an example of how it's false.
This, ironically, has got to be the most perfect way I've seen to skip actually responding to anything someone else has said and return to one's original assertions in one swoop. Especially combined with the response opening "You're simply wrong. What I said was correct"...
All that aside, it'd be a disservice to myself to say I'm not going to engage as a "last word" situation so I promise to come back to read any response (if one is made) and see what takeaways you have for me. My only ask is it be more than just how you're right/GP is so wrong/I'm wrong - at least something else about how my initial interjection/the GP's original statement (as you understand it from the other side thread now) could have been better, a more rigorous definition (i.e. not just words we've all been saying) of what you've been arguing so I can say "yeah, I did really understand what he was trying to say was so" (even if I disagree that was the ultimate point being made), or the like. Or don't, it's ultimately a service for me - you won't necessarily get anything out of it. Thanks
My takeaway for you is this: we're talking about mathematical proof techniques, and what you can conclude from the four different situations below. The soundness of a mathematical proof is independent of whether you're a frequentist or not, which is why I brushed off that comment. The particular measure you choose doesn't really matter either. It might matter whether you accept the axiom of choice or not, but I'm the only one who's brought that up so far. It's important because mathematical proofs are very finicky on exact details, and bubblyworld's statement is exactly the kind of pernicious little detail that can trick you into thinking a proof is correct when it's not. That matters!
The main free variable here is exactly what "probability" means in terms of how you're "picking" possible objects. Yes, there are some cases where showing that an object exists with "positive probability" (and almost certainly a subset having "positive measure") means that one example must actually exist, but if that's the case, the jump from "positive measure" to "must exist" is actually tautological! That is, your proof doesn't need that step; the act of showing "positive measure" has already proven the existence. The very fact that a mathematical pillar like Erdős was relying on such a step means that it was necessary for his proof. His proofs didn't have random tautological steps in them. We are not talking about the proof technique of "if a subset of X has a thing in it, then X must have a thing in it" -- that's literally tautological.
So what does "probability" really mean here? bubblyworld gave a link to examples of what he's talking about (see [1], Example 2), and seemed to misunderstand the proof. It's structured like this: "Let n be very large and consider a random graph G on n vertices ... we show that with positive probability, G satisfies two properties." Let me ask: how are we mathematically certain there exists a graph G that satisfies the two properties? (And we are; the proof is correct.) Which of the 4 situations are we in below? bubblyworld's insistence on finite sets makes it sound like we're in #3: finite set, nonzero probability. And indeed the set of random graphs with n vertices is finite! But that is an important mistake. We are not relying on argument #3 below. Yes, the set of random graphs with n vertices is finite, but we have NOT proven that any specific G has our two properties, and we have NOT proven that any graph with n vertices has those two properties! It's entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties.
You might encounter a similar proof, exactly the same up to this point, and that proof might be wrong! If you believe bubblyworld, you could make this mistake. So why does Erdős's proof work? It relies on two things that are both necessary: (1) we're not talking about a finite set at all! We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here. Our smallest example might be of size 10^10^10^n! We don't know! We just know that if we keep going, eventually we must hit one. And, critically, (2) there is a positive lower bound on the probability, above some n (it's 1/2). That is, if the probability of a random subgraph having those two properties was some small nonzero probability that decreased as n increased, e.g. p ~ 1/n^2, then we still might never find an example! The proof could be incorrect! But it's shown that above some n, the probability is at least 1/2. Thus the whole proof works.
Any discussion about frequentism or Lebesgue measure is missing the point: we're talking about whether proofs are correct or not, and that is a very finicky, tricky discussion. bubblyworld's original statement, and his continued refinements of that statement, are incorrect, and believing such things can lead you to accept incorrect proofs. I think that matters. So I corrected it.
[1] https://en.wikipedia.org/wiki/Probabilistic_method
1. Infinite set, nonzero probability: we know at least one example must exist.
2. Infinite set, zero probability: not sure! It could be zero, or any subset of smaller cardinality or measure zero.
3. Finite set, nonzero probability: not sure! It could be zero! My coin flip example shows this.
4. Finite set, zero probability: we know no examples can exist.
Apologies if my initial wording or response made it difficult to reach this kind of discussion and much appreciation for setting that aside when you wrote this for me.
Sometimes we tend to have this intuition that if a rule applies to all low numbers, than it must apply to all numbers, that there can't be some huge number after which it breaks down (unless of course it explicitly includes that huge number, such as the rule "all numbers are smaller than a billion billion billion").
This is such a powerful intuition, even though it's obviously wrong, that rules that break it are even seen as a problem. For example there is the so-called "hierarchy problem" in physics, which states something like "there is no reason why the weak force is so much stronger than gravity". As if 2 times as strong is somehow fundamentally different than it being 10^24 times as strong from a mathematical perspective. And this has ended up being called a major problem with the standard model, even though it's completely normal from a mathematical perspective.
Dirac naturalness is as you describe: skepticism towards extremely large numbers, end of story. It has the flaw you (and every other person who's ever heard it) point out.
Technical (or t'Hooft) naturalness is different, and specific to quantum field theory.
To cut a long story short, the "effective", observable parameters of the Standard Model, such as the mass of the electron, are really the sums of enormous numbers of contributions from different processes happening in quantum superposition. (Keywords: Feynman diagram, renormalization, effective field theory.) The underlying, "bare" parameters each end up affecting many different observables. You can think of this as a big machine with N knobs and N dials, but where each dial is sensitive to each knob in a complicated way.
Technical naturalness states: the sum of the contributions to e.g. the Higgs boson mass should not be many orders of magnitude smaller than each individual contribution, without good reason.
The Higgs mass that we observe is not technically natural. As far as we can tell, thousands of different effects due to unrelated processes are all cancelling out to dozens of decimal places, for no reason anyone can discern. There's a dial at 0.000000.., and turning any knob by a tiny bit would put it at 3 or -2 or something.
There are still critiques to be made here. Maybe the "underlying" parameters aren't really the only fundamental ones, and somehow the effective ones are also fundamental? Maybe there's some reason things cancel out, which we just haven't done the right math to discover? Maybe there's new physics beyond the SM (as we know there eventually has to be)?
But overall it's a situation that, imo, demands an explanation beyond "eh, sometimes numbers are big". If you want to say that physical calculations "explain" anything -- if, for example, you think electromagnetism and thermodynamics can "explain" the approximate light output of a 100W bulb -- then you should care about this.
For example, in lower dimensions you get accidental isomorphisms [0]. These exist essentially because the defining equations are more constrained in lower dimensions.
A more tongue in cheek intuition is the interesting numbers theorem, which says essentially that every integer is interesting. One of the things that can make a number interesting is that there's a property for which it's the first counterexample.
The counterexample seems to rely on correlations between edge deletions which makes no sense because the deletions should be independent (in the definition I'm seeing on Wikipedia).
I could be wrong here because I haven't read it in detail but on first sight, it looks like there are some serious issues with mathematical rigour here.
(I.e., you can "model" undeletability by adding sufficiently many twin posts.)
Ps., do you mean "in which case the conjecture is obviously false"?
PS Depends on what conjecture we refer to here.