4 ms·

> 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 con

by 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.
  - feoren 2y ago
    > Yes, I did indeed mean finite. 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.
    - bubblyworld 2y ago
      Look, I'm not going to argue about this because we're talking about completely different things. Read up on the probabilistic method if you're genuinely interested in what I wrote - Paul Erdos has some famous papers on it.
      - 2y ago
- feoren 2y ago
  You're simply wrong. What I said was correct. > 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.
  - moralestapia 2y ago
    Agree, @zamadatix seems a bit out if his area of expertise. On finite sets, all the stuff they're saying doesn't make sense completely.
    - bubblyworld 2y ago
      I'm an ex-PhD in mathematics. We're talking about two entirely separate things - finite numbers of samples from a probability distribution (what you are talking about) vs the measure of a subset of some finite number of objects (the probabilistic method).
    - zamadatix 2y ago
      Just trying to prevent my "false assumption" confirmation bias from growing - did you come to this thread as a result of https://news.ycombinator.com/item?id=41729586 https://news.ycombinator.com/item?id=41729586 or should I be attributing happenstance? Either is cool, no worries!
    - deleted 2y ago

by feoren 2y ago

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.
- feoren 2y ago
  > Yes, I did indeed mean finite. 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.
  - bubblyworld 2y ago
    Look, I'm not going to argue about this because we're talking about completely different things. Read up on the probabilistic method if you're genuinely interested in what I wrote - Paul Erdos has some famous papers on it.
    - 2y ago
feoren 2y ago
You're simply wrong. What I said was correct. > 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.
- moralestapia 2y ago
  Agree, @zamadatix seems a bit out if his area of expertise. On finite sets, all the stuff they're saying doesn't make sense completely.
  - bubblyworld 2y ago
    I'm an ex-PhD in mathematics. We're talking about two entirely separate things - finite numbers of samples from a probability distribution (what you are talking about) vs the measure of a subset of some finite number of objects (the probabilistic method).
  - zamadatix 2y ago
    Just trying to prevent my "false assumption" confirmation bias from growing - did you come to this thread as a result of https://news.ycombinator.com/item?id=41729586 https://news.ycombinator.com/item?id=41729586 or should I be attributing happenstance? Either is cool, no worries!
  - deleted 2y ago