Author |
Topic: Infinite Balls Urn (Read 3466 times) |
|
WombatDeath
Junior Member
Posts: 89
|
 |
Re: Infinite Balls Urn
« Reply #25 on: Jan 9th, 2007, 3:20pm » |
 Quote  Modify
|
on Jan 8th, 2007, 5:16pm, Icarus wrote:
I figured you were being facetious, but I wanted to make sure other readers who are less familiar with probability understood the difference between probability = 1 and certainty. |
|
I hadn't come across that concept, so thank you for giving me something new to think about (and for making my brain bleed). I'm going to take a stab at the meaning of your comment and hope for the best:
The probability of not picking ball 837 from an infinite number of balls is 1 (c.f. the discussion about 1 = 0.999...). Therefore the probability of picking ball 837 is zero. However, you can't be certain that you won't do so anyway through some bizarre quirk of fortune. So the likelihood of not picking ball 837 isn't certain, even though it has a probability of 1.
And I suppose the corollary is that having a probability of zero doesn't necessarily make an event impossible.
Is that vaguely correct?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #26 on: Jan 9th, 2007, 3:34pm » |
Quote Modify
|
on Jan 9th, 2007, 3:20pm, WombatDeath wrote:Yep.
Obviously it's not just the case for 837; it holds (at the same time) for every number in an infinite set that picking it has probability 0 *).
But if you pick a number from that set, you have to end up with one. So you can't avoid getting a number that has zero probability.
*)Although it does depend on the probability distribution, of course.
|
| « Last Edit: Jan 9th, 2007, 3:40pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite Balls Urn
« Reply #27 on: Jan 9th, 2007, 5:43pm » |
Quote Modify
|
The example you gave doesn't quite work, because probability goes wonky when you try to make it uniform on unbounded sets, such as all natural numbers. However bounded infinite sets are better behaved:
Choose a real number at random from the interval [0,1]. This means that probability that the selected number lies between a and b is |b-a|. For any given single number x in [0,1], the probability that x will be the number you selected is 0. But since this holds for all values, every time a number is selected, it happens dispite that 0 probability.
|
| « Last Edit: Jan 9th, 2007, 5:44pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Infinite Balls Urn
« Reply #28 on: Jan 9th, 2007, 5:55pm » |
Quote Modify
|
on Jan 9th, 2007, 3:20pm, WombatDeath wrote:| The probability of not picking ball 837 from an infinite number of balls is 1 |
|
That depends on how you propose to pick one ball from an infinite number of balls. Once you go beyond the physically realizable situation of making finitely many choices from finitely many possibilities, you need to turn to the mathematically realizable situation of a probabilitiy space.
Suppose we have some set S of balls, and we wish to choose a ball X at random. Mathematically, we model this as a probability space (S, F, P), where S is the set of balls, F is a sigma-algebra consisting of certain subsets of S, called events, and P : F-> [0,1] is a probability measure, where for a set E in F, P(E) is the probability that the ball X we chose lies in E.
If S is countable, say S = N = {1,2,3,...}, then we can specify P by picking any sequence of nonnegative numbers p1,p2,... with [sum] pk = 1. We can set P({k}) = pk, and by countable additivity, this uniquely determines P(E) for any subset E of S. So in this case, knowing the probability measure is equivalent to knowing the probability of picking any given ball.
But we can't pick a ball uniformly at random: we need [sum] pk = 1, and this is impossible if the pk are all equal, for then the sum would either be 0 or infinity. In fact this condition forces pk > 0 for at least one k, so ball 837 could very well have positive probability of being picked.
The situation is drastically different when S is uncountable. For example, let S = [0,1], and suppose we want to pick a ball at random, i.e., we want to pick a random real number X between 0 and 1. The standard thing to do is to "pick" X uniformly at random. However, we are not actually picking X through any physical process, we are only defining a probability measure P : F -> [0,1]. That is, we know, for certain subsets E of S, the probability that X lies in the set E.
There are two ways in which this differs from the countable case: P is not uniquely determined by P({x}) for each element x of S, and P does not determine P(E) for every subset E of S.
First, if we pick X uniformly at random from the unit interval, then the probability that X is any given number is equal to the probability that X is any other given number. But this probability cannot be positive, because then by countable additivity, the probability that X lies in any countably infinite subset of S would be infinite, a contradiction. So the probability that X is equal to any given number is 0, but it makes perfectly good sense to say, for example, that the probability that X lies in (.1, .6) is 1/2.
More generally, if E is an interval (a,b) contained in [0,1], then P(E) = b-a. Since F is a sigma-algebra, we also know P(E) for any E which is a countable union of such intervals, and this includes every open set. We also know the probability of the complements of these sets, which are the closed sets. And we also know the probability of any countable union of closed sets, as well as their complements, which are countable intersections of open sets. And we know countable unions of these, etc. The collection of all sets we obtain in this way -- the smallest sigma-algebra containing the open sets -- is known as the Borel sigma-algebra.
So by specifying that X is chosen uniformly from the interval [0,1], we know the probability that X lies in any given Borel set. However, it can be shown that there are only countably many Borel sets, while S has uncountably many subsets. Is it possible to extend the measure P beyond the Borel sets? The answer is yes. P has an extension, called the Lebesgue measure, defined on the sigma-algebra F known as the Lebesgue subsets (one can show there are uncountably many Lebesgue subsets, hence most are not Borel).
But, assuming the axiom of choice, there are subsets, such as the Vitali set V, which are not Lebesgue-measurable. That is, if we pick a number X uniformly at random between 0 and 1, it does not make sense to ask what the probability is that X lies in V.
There's another way to think of the uniform distribution on [0,1] that may shed some light. To determine X, flip a coin for each binary digit in the expansion of X. Of course, you won't actually know X at any finite time. But suppose some number A is given, via some infinite binary expansion. Then it is possible to know, after a finite number of flips, whether X<A or X>A. The only exception would be if the the digits match A for every single flip, or possibly if from some point on you get all 0s or all 1s, but none of these events will ever "happen". So this is a physical procedure that may actually be carried out (if you know arbitrarily many digits of A, and have an arbitrarily large amount of time on your hands), and so P(X<A) makes sense, and similarly it makes sense to ask what the probability is that X lies in any given open subset of [0,1]. Sort of.
Now, clearly it's "possible" to pick X=0, but only if your coin never comes up tails after infinitely many flips. One way to put it is that if something has probability 0 of occuring, it doesn't mean it can't happen, just that it won't. The problem with this way of thinking, though, is that you're trying to attach a physical model to a mathematical model, when the whole point of introducing the mathematical model was to model something non-physical. Or, that probability doesn't exist to tell you what can or will happen in any physical sense; it just assigns numbers to certain sets in a certain way.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Infinite Balls Urn
« Reply #29 on: Jan 9th, 2007, 6:41pm » |
Quote Modify
|
Suppose at stage k, we add ck balls, and then remove one at random, and let dk = c1+...+ck, and then the probability that ball n is never removed is
pn = prod{d_k >= n} (1 - 1/[dk-k+1]).
Thus if ck is constant or logarithmic, for example, then the urn will be empty with probability 1, and the expected number of balls left is 0.
But if ck grows large enough so that some ball n has positive probability of remaining, then note that every ball m > n is at least as likely to be left over, so the expected number of balls remaining is infinite. Moreover, since pn > 0, the infinite product converges and so the tails pm -> 1 as m goes to infinity.
Now let A be the set of remaining balls. For any fixed k, the event [A is contained in {1,...,k}] is contained in the event [m is not in A] for all m>k. Since the latter event has probability 1-pm -> 0, it follows that P[A is contained in {1,...,k}] = 0. Taking the union over all k, it follows P[A is finite] = 0. That is, with probability 1, there are infinitely many balls remaining. (In particular, it is empty with probabilty 0.)
|
|
IP Logged |
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: Infinite Balls Urn
« Reply #30 on: Jan 9th, 2007, 6:50pm » |
Quote Modify
|
This discussion reminds me of the problematic thinking behind "Bertrand's paradox."
Given a circle C of radius R, and a concentric circle c of radius r=1/2R, what is the chance that a chord through C, drawn at random, intersects c.
Argument 1: a chord is wholly determined by it's midpoint (except if the midpoint is the center, but that has probability zero), and a chord will intersect c exactly when the midpoint is in c. c has 1/4 the area of C, so there is a 1/4 chance that a chord will hit c.
Argument 2: Let the chord go through some point p on the outside of C. The chord will be uniquely determined by the angle it makes relative to the diameter. We can draw a right triangle with right angle at the center and hypotenuse as the line through p tangent to c. Then the angle at p has sin = r/R or 1/2, so 30 degrees out of 90 (on each side of the diameter) hit c, so we get 1/3 probabability.
Argument 3: use rotational symetry to assume that the chord is vertical. Then it is uniquely determined by the point it intersects the diameter. 1/2 of the diameter lies inside c, so the probability must be 1/2.
|
| « Last Edit: Jan 9th, 2007, 6:56pm by kiochi » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite Balls Urn
« Reply #31 on: Jan 9th, 2007, 7:10pm » |
Quote Modify
|
Of course, the whole secret to the "paradox" is the fact that the condition "drawn at random" is meaningless without further explanation. The three arguments choose three different probability distributions as their definitions of "at random". The result is three different probabilities.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: Infinite Balls Urn
« Reply #32 on: Jan 9th, 2007, 7:17pm » |
Quote Modify
|
Right. I think this sort of problem helped motivate the formalization of probability to include probability spaces so that thes ambiguities don't arise.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print