There are lots of examples of this phenomenon connected with "the probabilistic method". There the problem is to prove a certain type of object exists (there is at least one piece of hay in the stack). But it's hard to build one. So what you do is construct one randomly, then prove that on average or with high probability, your construction satisfies the requirements. This proves that at least one thing in the stack is hay, or actually that on average or most of the stack is hay.
I'm thinking of graphs, for example expander graphs; error-correcting codes; and probably lots more I'm forgetting. In these cases it then becomes a research program to construct such objects explicitly (which has a lot of history with expanders and codes).
>Irrational numbers occupy the vast, vast majority of space on a number line—so vast, in fact, that if you were to pick a number on the number line at random, there is literally a 100 percent chance that it will be irrational.*
The asterisk at the end doesn't seem to lead to an actual footnote. What is meant by this? That irrational numbers are more than 99.5% of all numbers and so it rounds to 100%?
Slogan: "rational numbers exist but do not take up space."
This is in a measure-theoretic sense, so literally 100% (not just 99.5%). On the number line, the measure of an interval is the (absolute) difference between its endpoints (the "length" of the interval). For any measurable set, you can approximate its size from above by covering its points with intervals and shrinking them as much as possible.
But because there are only countably many rational numbers, you can cover all of the rationals with a set of intervals with a finite total sum of lengths.
To be a bit more specific, if your rationals are r_1, r_2, r_3, ..., then for any small number e > 0, you can form the set of intervals
which have a total sum of lengths e/2 + e/4 + e/8 + ... = e and contain all of the rational numbers.
So for any positive number e > 0, the measure of the rational numbers is less than e, meaning that the measure of the rational numbers is 0.
To turn this into actual probabilities requires a little bit more work, since the measure of the number line, and hence that of the irrational numbers, is infinite, not "100%". But you could look at the probability of selecting a rational number in the interval [0, 1] and use the same reasoning as above to get a probability of 100% for an irrational number and 0% for a rational number.
(Edited to try to answer the objection more clearly.)
The intervals overlap heavily. Each of the intervals R_i contains infinitely many rational numbers, and all but finitely many of those will have corresponding intervals which are completely contained within the interval R_i. As a result, the estimate obtained by the construction described is always strictly smaller than the chosen e.
I appreciate your careful and patient explanation, and assay a superficial and snarky one of my own: it is impossible for the measure of the rationals, if it is to exist at all, to be exactly `e` for every small positive real number `e`. Even if we didn't know anything about the overlap of the intervals, we'd know at best that we had a (possibly non-strict) upper bound of `e`; but the only non-negative real number that can satisfy such a bound for every positive `e` is `0`.
The reason it’s 100 percent and not 99.9999 percent has to do with the strange things that happen once you start thinking about the probabilities when infinity is involved. Around the turn of the 20th century, the mathematician Henri Lebesque helped to develop “measure theory,” which provided a mathematically rigorous way for calculating the probabilities when infinite outcomes are possible.
Suppose that were to select one number at random from the set of integers in the range from [-1..8]. There is a 1 in 10 chance of selecting -1.
Now suppose you select from the range [-1..98]. There is a 1 in 100 chance of getting the single negative value. In the range [-1..99,998] there is a 1 in 10,000 chance. And so forth.
In the range [-1..x], as we raise x higher the chance of getting the negative value is smaller, and the higher x gets, the closer the chance gets to zero. That is what we mean when we say "the chance of selecting -1 out of [-1..infinity] is zero".
And that is precisely the sense in which the mathematical structures this article refers to (like irrational numbers, or non algebraic solids) have 100% chance of being selected when choosing a (number/solid/whatever) at random.
Another way to think of it, other than the other fine posts: Imagine you are selecting your random number by using a ten-sided die and writing down the number of each (fair) roll. Suppose you assume you are going to write down a rational number. What does that imply? It means that your fair die is going to roll some prefix, and then roll some infinitely repeating segment over and over again. As you roll the dice an infinite number of times, what is the probability that your die will ever deviate from the necessary strict repetition of the repeating segment? It is literally 100%, because no matter how many times it happens to conform to the repeating sequence, there remain an infinite number of rolls remaining in which to deviate.
If it absolutely never deviated, over the course of infinite rolls, that would itself be proof that the die is itself not a fair die. e.g., if your putatively "fair ten-sided die" rolls up precisely 1/3, by virtue of rolling an infinite series of 3s, then that would be proof that it is not in fact fair and random.
I think this helps the 100% intuition. It is simply impossible for a truly random selection process to produce a rational number.
> As you roll the dice an infinite number of times, what is the probability that your die will ever deviate from the necessary strict repetition of the repeating segment? It is literally 100%, because no matter how many times it happens to conform to the repeating sequence, there remain an infinite number of rolls remaining in which to deviate.
While I think that accumulating as much intuition as possible is a good idea, I'm afraid that this intuition may be misleading. The problem is that there's no roll at which we can give up and say "oh well, we deviated from the pattern and aren't rolling a rational number", because we have no idea in advance when we've entered the repeating portion of the decimal expansion. That is, if we roll 0.000123456789, and then roll a 6 rather than a 1, we can't conclude that we're rolling an irrational number; all we can conclude is that, if we roll a rational number, then the repeating portion of its decimal expansion either isn't 123456789, or else hasn't begun yet.
For any given rational number, my argument holds. I meant to type "suppose we're going to roll a particular rational number", but I see that I neglected to edit that in.
For any given roll up to a certain point, there are a finite number of rational numbers that you could be rolling. For any given one of those numbers, my argument holds. There is never a point at which any rational number you could be rolling has a probability greater than zero.
You will pick an irrational number "almost surely" or "with probability 1". It's a somewhat counterintuitive* concept, but very well defined mathematically.
[*] (For example, any individual number has probability 0 of being picked (exactly, not approximately), yet one is being picked. Or: there are infinitely many rational numbers between 0 and 1, but the probability that any one of them is picked is 0. Thus, the probability that one of the remaining ones is being picked (an irrational number), is 1.)
I would guess it means "in some sense". In a measure-theoretic sense, for example. You need to give it meaning somehow, as you cannot really pick a "random" real number with any algorithm (most real numbers are actually not even computable!).
It could also be a remark that in infinite sets 100% (in a measure-theoretic sense) does not mean all of the elements.
In statistics there's a slight difference between something that happens 100% of the time and something that always happens.
Or rather just because something has a probability of 0 doesn't mean it can't happen, events with probability 0 happen all the time.
They may also have been referring to the fact that picking a random number over the whole number line is not that as simple as it sounds since the uniform distribution doesn't exist.
> Or rather just because something has a probability of 0 doesn't mean it can't happen, events with probability 0 happen all the time.
There is definitely a mathematical sense in which events with probability 0 can happen, but I don't know of any 'real-world' setting, e.g., in statistics, in which we correctly assign an event a probability of 0 (rather than just "too small to distinguish from 0") and yet find it happening. Could you give an example?
> In statistics there's a slight difference between something that happens 100% of the time and something that always happens.
> Or rather just because something has a probability of 0 doesn't mean it can't happen, events with probability 0 happen all the time.
I took this to be a claim that there was a 'real-world' sense (or as real-world as statistics is), not just a strictly mathematical sense, in which events with probability 0 happen "all the time", and I was wondering what this sense (not the mathematical sense) was.
It's just the converse: the probability of not picking the given number was (and still is) 100%, but you did pick it, so what "had to" happen with 100% probability, didn't.
(Maybe that's the meaning of the perceived difference between the real world and statistics. Playing a lottery doesn't make sense, but people do win!)
An idealized 'dot' has zero 'volume', as does a countable number of such dots. The bulk of the real number line is made from irrational numbers, with a countable number of rational dots mixed in.
If you define the 'probability' of hitting a rational dot in terms of ratios of volumina, it will be mathematically zero.
the same result holds if you restrict to some subset of the real line, say the closed unit interval `[0, 1]`.
although there are infinitely many rationals and infinitely many irrationals in the unit interval [0, 1], from the perspective of cardinality, there are a lot more irrationals. there are countably many rationals in [0, 1], meaning you can put those rationals into correspondence with the natural numbers 1, 2, 3, ... , but there are uncountably many irrationals in that same interval.
the quote about "100 percent chance" is probably alluding to measure theory. measure theory is used to define integration. in this 1 dimensional case of the real line, or a subset of the real line, you can think of the measure of a set being something like defining its length. the measure of the whole set [0, 1] is 1. the subset of all rationals in [0, 1] has measure zero, i.e. it has the same measure as a single point. there's no measurable length to it. not all subsets can be assigned a sensible notion of a length.
if you think of random sampling a point from the set [0, 1] according to a uniform distribution, then you have a probability of 0 < delta <= 1 of randomly sampling a point that belongs to any pre-defined subset [-0.5 * delta + x, x + 0.5 * delta] of [0, 1] . Informally, if we make delta smaller and smaller, the chance of randomly sampling a point that is arbitrarily close to x is probability delta that becomes arbitrarily close to zero. when you randomly sample from uniform distribution on [0, 1] the chance of sampling any particular pre-specified real number is probability zero. probability zero isn't the same as impossible! see https://en.wikipedia.org/wiki/Almost_surely
on another hand, despite this, the rationals are dense in [0, 1]. this means that for any real number x in [0, 1], for any (small) radius r > 0 we can find some rational y in [0, 1] that is within a ball of radius r from x, i.e. there is some rational y such that |x-y|<r. this means we can pick some sequence y_1, y_2, y_3, ... of rational numbers that become better and better approximations to the target x (which in the interesting case, x is irrational). think a sequence of decimal approximations to the target number x. despite this ability to approximate any irrational with a rational arbitrarily well, there are still a lot more irrationals, in both the cardinality and a crude measure-theoretic sense (if we delete them all it doesnt change the amount of length we started with).
> The asterisk at the end doesn't seem to lead to an actual footnote. What is meant by this?
perhaps it is meant to provoke all people who like to see everything clearly defined
The article points out how rational numbers are the needles amongst the hay of irrational numbers.
In a more discrete setting, we have compressible files being the needles among the hay of incompressible files. Technically; all but a fraction of 2^-k of binary strings of length n need at least n-k bits to describe, but we cannot come up with a single explicit example.
Indeed; we can't come up with explicit examples for the uncomputable compression to the shortest possible description (corresponding to the Kolmogorov complexity).
Which is why in computational, science, and engineering mathematics there is the concept of maximum precision. All measurements have an amount of precision and as long as the precision of how you record and calculate numbers is greater than that, the solution will be correct.
Unfortunately, this was not what I was taught in math class (science classes had to teach this separately.) This lead me (and most everyone else I communicate with) to erroneously believe that "good" math requires infinite precision. This leads to things like junior programmers losing their minds when 0.1 + 0.2 doesn't equal 0.3
> as long as the precision of how you record and calculate numbers is greater than that, the solution will be correct.
Well .. not quite, you have to be very aware of the kinds of operations that may result in loss of precision or error accumulation. Whether you're using floating point or longhand decimal.
Conversely algebra operates as infinite precision, allowing the safe manipulation of numbers with no finite representation.
I'd rather do my math with a machine even though it requires finite precision. How operations affect precision is well known and not difficult to keep track of. You will only have "error accumulation," as you call it, if your desired precision is at the maximum that your computational machine can tolerate. So don't do that, and everything will work out fine.
> You will only have "error accumulation," as you call it, if your desired precision is at the maximum that your computational machine can tolerate.
This is not true. The tiniest of errors can accumulate arbitrarily—this is what it means to say the real numbers form an Archimedean number system; and so it is perfectly possible to get, say, the wrong integer part (a far coarser measure than the maximum precision that any modern machine can tolerate) by performing many successive operations on, say, a float.
i think a dark side to "finding hay in a haystack" is the risk of building up an elegant theory for e.g. a novel calculus of hay, only to realise after some time that the set of hay is in fact empty, or is isomorphic to some other well understood and hence uninteresting structure.
So much for "mainstream math". There is an alternative take called constructive algebra, which I believe to be more useful to a computer programmer. Briefly:
"There are only finitely many numbers."
That's trivially true, because numbers are man-made objects, and man has only had enough time to make finitely many of them. Integral and rational numbers can be made by writing them down, algebraic irrational numbers can be made by writing down an expression for them. (What language? Lambda calculus, obviously, because according to the Church-Turing thesis, nothing more powerful exists.)
Only countably infinitely many numbers can potentially be made this way, only finitely many will ever be made. Those non-algebraic transcendental numbers? Don't exist, because they can never be made. They may "exist" in a philosophical way, but they no impact whatsoever on the real world in which my programs operate.
So you can't imagine a world in which our understanding of pi or e might impact or be useful to the real world?
More broadly, you can surely imagine how the study of transcendent numbers might inform results in other fields? I don't usually try to justify math by pointing at its applications, but for example, the transcendence of pi leads to a proof that squaring the circle is impossible. Even if things aren't constructable, they can still be valuable to think about.
Brilliant, just like the dimwitted TA at university who claimed full of conviction "NO amount of memory can represent pi!" Which is funny, because he represented it with a single character.
Pi and e are both algebraic numbers, there are expressions (algorithms) for both. And guys like you are funny: Faced with proof that almost all real numbers do not have a name, you immediately try to name an example.
You contradict yourself: any given real number is, in fact, given by its "name", which, as you said, is either a symbol or an algorithm (which, incidentally, are the same thing - a symbol can be seen as the name of an algorithm, or a function; the TA was probably referring to the fact that the algorithm would have to stop at some point so as to avoid overrunning the memory limit).
Err... I didn't say that. For good reason, as you point out. I know that you cannot "give" almost all real numbers. I'm merely pointing out that there are mathematicians who go the extra mile and decide that those don't even exist.
Symbol, name, algorithm; all of those are the same thing. And almost all real numbers (in ZFC aka "standard math") don't have one.
> the TA was probably referring to the fact that the algorithm would have to stop at some point
Nope, he wasn't. He specifically insisted that no amount of memory can represent pi, while any integer can be represented. He was technically correct, but I have an easier time working with pi (to any desired, even dynamically determined precision) than with Ackermann(4,4).
The dimwitted TA missed the point, and he did so, because standard (not constructive) math creates lots (continuously infinitely many) of infinities, which serve no use but to make irrelevant points about things that cannot occur in actual programs.
I'm thinking of graphs, for example expander graphs; error-correcting codes; and probably lots more I'm forgetting. In these cases it then becomes a research program to construct such objects explicitly (which has a lot of history with expanders and codes).