3 ms·

I don't know. To me it sounds like it's obvious the conjecture doesn't hold. if you have a path in the upper bunk that gets broken you are screwed but if that p

by yread 2y ago

I don't know. To me it sounds like it's obvious the conjecture doesn't hold. if you have a path in the upper bunk that gets broken you are screwed but if that path is broken you have the option to switch to path in the lower bunk at ANY moment. So you have n+1/n higher chance of a break but n-1 ways how to avoid it

supernewton 2y ago
The conjecture is true for all small graphs that they tried, so if it's "obviously" false to you then something went wrong with your intuition somewhere.
- zmgsabst 2y ago
  Or everyone else’s, since his intuition arrived at the right asymptotic answer.
tech_ken 2y ago
I'm pretty sure you're sampling the "bedposts" as well, the upper and lower subgraphs aren't just connected at every node; I understood the rough (and incorrect) intuition to be like: 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
winwang 2y ago
Intuitively (subjectively) why this argument doesn't work: if you switch to the path in the lower bunk, you can switch to the upper bunk "at any moment", regardless of if there is a path which exists on the lower bunk. In this example, a1 is connected to both c1 and c2: a1 b1 -- c1 | | | a2 -- b2 -- c2 If, instead of deleting edges, we assigned a distance d = 1/p, then you'd expect (and probably easily prove) that the distance to the target vertex is at most the distance to its partner in the other bunk. The fact that this intuitive "problem translation" doesn't actually translate to probabilities is quite surprising (to me)!
scottmsul 2y ago
> if you have a path in the upper bunk that gets broken you are screwed 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.

by yread 2y ago

supernewton 2y ago

The conjecture is true for all small graphs that they tried, so if it's "obviously" false to you then something went wrong with your intuition somewhere.

zmgsabst 2y ago
Or everyone else’s, since his intuition arrived at the right asymptotic answer.

tech_ken 2y ago

I'm pretty sure you're sampling the "bedposts" as well, the upper and lower subgraphs aren't just connected at every node; I understood the rough (and incorrect) intuition to be like: 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

winwang 2y ago

Intuitively (subjectively) why this argument doesn't work: if you switch to the path in the lower bunk, you can switch to the upper bunk "at any moment", regardless of if there is a path which exists on the lower bunk. In this example, a1 is connected to both c1 and c2: a1 b1 -- c1 | | | a2 -- b2 -- c2 If, instead of deleting edges, we assigned a distance d = 1/p, then you'd expect (and probably easily prove) that the distance to the target vertex is at most the distance to its partner in the other bunk. The fact that this intuitive "problem translation" doesn't actually translate to probabilities is quite surprising (to me)!

scottmsul 2y ago

> if you have a path in the upper bunk that gets broken you are screwed 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.