4 ms·
> 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 t
by 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 agoLook, 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.
- feoren 2y agoWe're not talking about different things. We're talking about one very specific claim that you made: > 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.
- deleted 2y ago[deleted]
- bubblyworld 2y agoIf 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. This is easy to prove - it follows formally from sigma-additivity of the measure. 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).
- feoren 2y ago> i.e. the measure of the subset of elements satisfying P is positive 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!
- bubblyworld 2y agoThat depends on the measure, obviously. It's trivial to construct examples in which finite sets have positive measure - just take the uniform probability distribution over a finite set. Or for a more thematic example, the probability space of random graphs on n vertices. Or really any finite measure you like! 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.