3 ms·
With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be
by wakamoleguy 5y ago
With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence?
In other words, perhaps I'm just asking for the answer to Exercise 2!
- wakamoleguy 5y agoI suppose if you choose edges at random, then it's as likely to fail early as it is to fail late. So if you get to 70% confidence, that does seem reasonable to believe it's probably 3-colorable (but still with a big chance that it is not).
- xiphias2 5y agoIt's about 1-1/e (63%) as there's always 1 edge with problem, and always 1/E probability that it is revealed in on average E rounds. (1-1/E)^E -> 1/e