4 ms·

Can you elaborate? It's possible to prove probabilistic results about discrete objects rigourously - in fact this is a reasonably common technique (going back t

Can you elaborate? It's possible to prove probabilistic results about discrete objects rigourously - in fact this is a reasonably common technique (going back to work by Paul Erdos, and probably further). It can give you concrete information about the existence or non-existence of these objects (if something exists with non-zero probability in a finite set there has to be at least one example). It's not a "less valid" way to prove things, just a particular choice of approach. Sometimes it makes things easier, sometimes it doesn't.

ilya_m 2y ago
We are talking about different kinds of "probabilistic" proofs. Igor Pak's blog post and the root message in this thread refer to statements that are validated only probabilistically. The probabilistic method, by Erdos and others, is a proof as rigorous as any. "Probabilities" in the this method are just a convenient apparatus for counting objects. (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.)
- bubblyworld 2y ago
  Right - I admit I stopped reading the blog post at the point they linked to the paper and started reading that instead (which contains a rigorous proof). Having read the rest of the blog now I can see where the OP is coming from.
samatman 2y ago
What you're describing is different from the distinction the parent is making, which is between providing a high probability of evidence that a conjecture is true, versus proving the conjecture true through a rigorous formal proof. 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.
- bubblyworld 2y ago
  Yeah, I missed that there was a discussion of empirical evidence in mathematics in the blog post (rather than the probabilistic method).
feoren 2y ago
> if something exists with non-zero probability in a finite set there has to be at least one example 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.)
- zamadatix 2y ago
  I think GP did mean finite, just not perfectly clearly how (and also all in missing what the article was focusing on a bit). I.e. 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 - otherwise the probability could not be non-zero. Not in that a single given instance of the finite set must show that result, just that one possibility of what it could contain must have. 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 https://en.wikipedia.org/wiki/Almost_surely
  - bubblyworld 2y ago
    Yes, I did indeed mean finite. I was referring to the probabilistic method in combinatorics (https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikipedia.org/wiki/Probabilistic_method). It's a non-constructive technique for proving existence theorems. Of course, this kind of thing works for infinite sets too, but there are some subtleties when it comes to sets of measure zero that kind of obscure the point.

ilya_m 2y ago

We are talking about different kinds of "probabilistic" proofs. Igor Pak's blog post and the root message in this thread refer to statements that are validated only probabilistically. The probabilistic method, by Erdos and others, is a proof as rigorous as any. "Probabilities" in the this method are just a convenient apparatus for counting objects. (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.)

bubblyworld 2y ago
Right - I admit I stopped reading the blog post at the point they linked to the paper and started reading that instead (which contains a rigorous proof). Having read the rest of the blog now I can see where the OP is coming from.

samatman 2y ago

What you're describing is different from the distinction the parent is making, which is between providing a high probability of evidence that a conjecture is true, versus proving the conjecture true through a rigorous formal proof. 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.

bubblyworld 2y ago
Yeah, I missed that there was a discussion of empirical evidence in mathematics in the blog post (rather than the probabilistic method).

feoren 2y ago

> if something exists with non-zero probability in a finite set there has to be at least one example 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.)

zamadatix 2y ago
I think GP did mean finite, just not perfectly clearly how (and also all in missing what the article was focusing on a bit). I.e. 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 - otherwise the probability could not be non-zero. Not in that a single given instance of the finite set must show that result, just that one possibility of what it could contain must have. 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 https://en.wikipedia.org/wiki/Almost_surely
- bubblyworld 2y ago
  Yes, I did indeed mean finite. I was referring to the probabilistic method in combinatorics (https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikipedia.org/wiki/Probabilistic_method). It's a non-constructive technique for proving existence theorems. Of course, this kind of thing works for infinite sets too, but there are some subtleties when it comes to sets of measure zero that kind of obscure the point.