Dear qarl,
First of all, we should agree that infinity is not a number but a
property. For example, we can say that a set contains an infinity of
members, but it makes no sense to say that any member of this set is
itself infinity. By definition, an infinite set has more members than any
finite set. The set containing all natural numbers is one example of an
infinite set. Its membership is greater than that of any finite set of
natural numbers. In particular, it contains every possible natural number.
If we pick a natural number at random, it will surely not be infinity, for
it is always possible to produce a greater number. If we pick a number n,
there is always the greater value n+1, and countless more besides. This
is true for any n. However, we shall see that the expected value of a
random selection from the set of all natural numbers is infinite in a
different sense. In the remainder of our discussion, we use "random" to
mean that every member of the set has an equal chance of being chosen,
which is to say that we are selecting under a uniform distribution.
You propose the experiment of making a random selection from the set
of all natural numbers, and wish to establish that the result will be
very large. The expected value of such an experiment is not infinity,
as I explained above, but it does have the following interesting property.
Claim
The expected value of a random selection from the set of all
natural numbers is greater than the expected value of a random
selection from any finite set of numbers.
So no matter how many big numbers you collect into a finite set, the
expected value of picking a number from this set is smaller than the
expected value of a selection among all natural numbers. If we restrict
ourselves to a set containing a single number n, then we must pick n. And
no matter how big this n may be, the expected value of a randomly chosen
natural number is greater than n. Thus, our Claim implies the following
Corollary.
Corollary
The expected value of a random selection from the set of all
natural numbers is greater than any given natural number n.
In that precise and highly practical sense, the expected value of
a randomly chosen natural number is infinite. Since the Claim leads
directly to the Corollary, we need only prove the Claim. My proof,
which does not rely on any particular ordering of the natural numbers,
is as follows. It is a proof by contradiction.
---------------------------------------------------------------------
Proof
Suppose the Claim is false. This implies that there is a finite
set S such that the expected value of a random selection from S
is at least as great as the expected value of a random selection
from N, the set of all natural numbers. We express this situation
with the inequality
mean(S) >= mean(N) . [1]
Now, the expected value of a random selection from S is bounded
from above by the greatest value in S, which we shall call m.
mean(S) <= m [2]
This is because no matter what number we pick from S, it will not
be greater than m, the greatest member of S. Since no member of
S is greater than m, it follows that the expected value cannot
be greater than m either.
Now, the set of all natural numbers N includes the subset
T = { 1, 2, 3, ..., 2m-2, 2m-1, 2m } [3]
no matter how it is ordered. Note that T has exactly 2m
members. The expected value of a random selection from T is m+0.5,
because the mean of T is
mean(T) = (1 + 2 + 3 + ... + 2m-2 + 2m-1 + 2m) / 2m [4]
= m * (2m + 1) / 2m [5]
= (2m + 1) / 2 [6]
= m + 1/2 . [7]
But in addition to the numbers appearing in T, the set of all
natural numbers N contains many more numbers, all of which are
greater than 2m. Thus, the expected value of a random selection
from N must be greater than m+0.5 .
mean(T) < mean(N) [8]
m+0.5 < mean(N) [9]
But inequality [2] above tells us that m+0.5 is still greater
than mean(S), the expected value of a random selection from
S. Hence, mean(S) must be even smaller than the expected value
of a random selection from N. Putting together inequalities
[2] and [9], we obtain the following.
mean(S) <= m < m+0.5 < mean(N) [10]
mean(S) < m+0.5 < mean(N) [11]
mean(S) < mean(N) [12]
This contradicts inequality [1], which is the contrary of the
claim. Therefore, the Claim cannot be false. It must be true.
---------------------------------------------------------------------
If you don't see how to compute mean(T) = m+0.5, let me bring to your
attention the following article on summing an arithmetic series.
MathWorld: Arithmetic Series
http://mathworld.wolfram.com/ArithmeticSeries.html
Note in particular equation (10), which in our case yields
sum = 1/2 * 2m * (1 + 2m)
= m * (2m + 1)
and that is exactly the numerator in line [5] above.
Regards,
leapinglizard |
Request for Answer Clarification by
qarl-ga
on
16 Nov 2005 12:51 PST
hey leapinglizard -
i feel like such a party-pooper. everyone brings me a proof - and i
always find some hole in it. i'm beginning to feel very bad about all
this... but i think i've found a hole in yours, too.
but perhaps not, let's talk about it.
my concern is your underlying (unmentioned) assumption that "the
expected value of a randomly selected natural number" has a specific
value - especially given that your proof is by contradiction. you
show that since it doesn't have one value, it must have the other.
but if it has no value at all, then it's not an either-or situation.
consider the infinite sum (-1)^i for all natural numbers i. (which
longhand is (-1 +1 -1 +1 -1 +1....)) the sum doesn't converge, so we
say it has no value. if we began by assuming it had a value, we would
quickly get ourselves into all kinds of trouble, and show it to be
equal to anything we wanted.
or, consider this question: what is the probability of choosing an
even number from the set of natural numbers. as shown in the
comments, this probability has no value. but if we start by assuming
it does, we could then argue (by contradiction) that it can't be less
than 1/2, and it can't be greater than 1/2, so it must be 1/2. but in
fact it can be shown to be not 1/2 either - because it has no value.
...
so what do you think?
K.
|
Clarification of Answer by
leapinglizard-ga
on
16 Nov 2005 13:56 PST
My proof does not mention a specific value for the result of the
random selection. It shows that the expected value of randomly
selecting among the natural numbers is greater than any given natural
number. In this sense, the expected value is infinite. You cannot
produce a natural number that is as great or greater than the expected
value of making a random selection among all natural numbers. This can
be proven, as I have done, by elementary algebraic manipulation.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
16 Nov 2005 16:14 PST
erm - i think you do assume a value. when you say "a < b" leads to a
contradiction, so "a >= b" - the underlying assumption is that "a" and
"b" both have values (and have value in a completely ordered set.)
in this case, as in the case with infinite sums, there's the
possiblilty that "a = NaN" (in IEEE parlance) and so the negation of
"a < b" is not "a >= b", but instead "(a >= b") or (a = NaN) or (b =
NaN)". so to complete your proof, you'll need to show that "a !=
NaN".
|
Clarification of Answer by
leapinglizard-ga
on
16 Nov 2005 20:20 PST
I bring to your attention the Law of the Excluded Middle.
MathWorld: Law of the Excluded Middle
http://mathworld.wolfram.com/LawoftheExcludedMiddle.html
If the Claim is not false, then it must be true. In my proof, I posit
that it is false, and I arrive at a contradiction. Therefore it is
true.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
16 Nov 2005 20:58 PST
yes. and i'm telling you that when you posit that the statement is
false, you incorrectly take its negation.
the original statement is "The expected value of a random selection
from the set of all natural numbers is greater than the expected value
of a random selection from any finite set of numbers."
the correct negation of this statement is "The expected value of a
random selection from the set of all natural number is less than or
equal to the expected value of a random selection from any finite set
of numbers, OR the expected value of a random selection from the set
of natural numbers has no value OR the expected value of a random
selection from any finite set of numbers has no value."
the last term of the statement is easily shown to be false - that
leaves the second term.
perhaps, if you gave a mathematical definition of what you mean by
"the expected value of a random selection from the set of natural
numbers" we could avoid the "no value" situation. but as long as we
leave it undefined, the problem persists.
|
Clarification of Answer by
leapinglizard-ga
on
16 Nov 2005 22:09 PST
Well, the expected value of drawing a number from any set under the
uniform distribution is the same as the arithmetic mean of the numbers
in the set. So the mathematical definition you are looking for is that
of the arithmetic mean, also known as simply the mean or the average.
See equation (1) on the following page for the formula.
MathWorld: Arithmetic Mean
http://mathworld.wolfram.com/ArithmeticMean.html
As N tends toward infinity, so does the mean of the set {x_i}. Or if X
is a random variable with a uniform distribution, we say that the
expected value of X tends toward infinity as the domain of X tends
toward the set of all natural numbers.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 00:29 PST
so, we're agreed that "mean" has no definition for an infinite set?
the 1/N definition i saw in your Wolfram reference gets into trouble
for N=inf.
and by your last comment, it sounds as if you're relying on a limit
argument, which i think suffers from the same trouble as in the
comments.
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 00:58 PST
No, we are not agreed. Every set, whether finite or not, has a mean.
For example, the mean of the infinite set {..., -2, -1, 0, 1, 2, ...}
is 0. The mean of the infinite set {1, 2, 3, ...} is infinitely large.
In other words, it is larger than any given natural number.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 02:08 PST
really? are you sure? can you provide a reference?
(your wolfram reference defined means only for finite sets.)
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 03:08 PST
Yes, I'm sure. Every set has a sum, and every set has a cardinality.
The mean is the sum divided by the cardinality.
leapinglizard
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 03:10 PST
There is one exception: the empty set. Since the empty set has
cardinality zero, its mean is undefined. But every non-empty set has a
mean.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 11:37 PST
aw crap. no, not every set has a sum.
http://mathworld.wolfram.com/RiemannSeriesTheorem.html
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 11:59 PST
Yes, every set has a sum. The summing operation is well-defined for
finite as well as infinite sets. The Riemann Series has nothing to do
with the sum of a set.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 12:10 PST
i'm getting the feeling you don't have a firm grip on these topics.
so what's the sum of {...-1/8, -1/6, -1/4, -1/2, 0, 1/3, 1/5, 1/7....}?
can you provide a reference for the definition of "mean" over an
infinite set (other than your own?)
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 16:01 PST
I hold the degree of Master of Mathematics from an eminent university.
I know what I'm talking about.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 16:34 PST
that's very nice for you - and i have lain waste to more than one phd
thesis from another eminent university. so perhaps with both our big
brains, we can resolve this issue.
you have repeatedly stated that summation is well defined for
countably infinite sets. can you please specify this definition?
and, what value does this definition provide for the sum of the
alternating harmonic series? given than Riemann showed it converges
to any value you'd care to make it - it doesn't seem promising that it
has a "single well defined value".
seriously - if you have a valid point here - please explain it.
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 16:45 PST
or, more simply - what is the sum of the set of integers, I = {...,
-3, -2, -1, 0, 1, 2, 3, ...}.
by one ordering:
0 + 1 - 1 + 2 - 2 +... = 0 + 0 + 0 + 0 +...
i get 0.
by another:
0 + 1 + (2-1) + (3-2) + (4-3) +... = 0 + 1 + 1 + 1 + 1 + ...
i get inf.
|
Clarification of Answer by
leapinglizard-ga
on
17 Nov 2005 17:14 PST
You are correct, there are sums that cannot be evaluated. This does
not mean that we cannot otherwise express them or reason about them.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
17 Nov 2005 19:54 PST
so - let's be clear - we're agreed that not all sums can be evaluated
(i.e. put in a 1-1 "natural" correspondence with the reals.) so we're
not dealing with simple numbers, presumably.
so what set are we talking about here? when you say one sum is "less
than" another sum, what are you talking about? can you please, PLEASE,
provide me with some external reference for this "less than" relation
- and proof that it is a total ordering?
if you don't start answering my specific questions, i'm going to ask
that we end this discussion, and you allow someone else to answer my
question.
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 01:52 PST
Very well.
leapinglizard
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 02:15 PST
I mean to say, I don't know what you mean. A total order is defined
within a set, not between sets.
It occurs to me that I should not have presented the proof as a
reductio ad absurdum, since I don't make use of the contradicted
premise anyway. It works perfectly well as a direct proof. See below.
leapinglizard
Claim
The expected value of a random selection from the set of all
natural numbers is greater than the expected value of a random
selection from any finite set of numbers.
Corollary
The expected value of a random selection from the set of all
natural numbers is greater than any given natural number n.
Proof
The expected value of a random selection from a finite set S is
bounded from above by the greatest value in S, which we shall
call m.
mean(S) <= m [1]
This is because no matter what number we pick from S, it will not
be greater than m, the greatest member of S. Since no member of
S is greater than m, it follows that the expected value cannot
be greater than m either.
Now, the set of all natural numbers N includes the subset
T = { 1, 2, 3, ..., 2m-2, 2m-1, 2m } [2]
no matter how it is ordered. Note that T has exactly 2m
members. The expected value of a random selection from T is m+0.5,
because the mean of T is
mean(T) = (1 + 2 + 3 + ... + 2m-2 + 2m-1 + 2m) / 2m [3]
= m * (2m + 1) / 2m [4]
= (2m + 1) / 2 [5]
= m + 1/2 . [6]
But in addition to the numbers appearing in T, the set of all
natural numbers N contains many more numbers, all of which are
greater than 2m. Thus, the expected value of a random selection
from N must be greater than m+0.5 .
mean(T) < mean(N) [7]
m+0.5 < mean(N) [8]
But inequality [2] above tells us that m+0.5 is still greater
than mean(S), the expected value of a random selection from
S. Hence, mean(S) must be even smaller than the expected value
of a random selection from N. By combining inequalities [1] and
[8], we obtain the following.
mean(S) <= m < m+0.5 < mean(N) [9]
mean(S) < m+0.5 < mean(N) [10]
mean(S) < mean(N) [11]
Therefore, the expected value of a random selection from N is
greater than the expected value of a random selection from S.
|
Request for Answer Clarification by
qarl-ga
on
18 Nov 2005 11:51 PST
> It works perfectly well as a direct proof.
yeah, i had noticed that, too. but it still doesn't get around my
central grouse, which i can pinpoint to the following line:
> But in addition to the numbers appearing in T, the set of all
> natural numbers N contains many more numbers, all of which are
> greater than 2m. Thus, the expected value of a random selection
> from N must be greater than m+0.5 .
if the expected value of a random selection from N has no value (as
the sum of the integers has no value) then you can't say it must be
greater than m+0.5. they may be "unrelated" - as happens with
non-total orderings.
when you say "greater than" i can only assume you're talking about (a)
the "normal" ordering on numbers or (b) some other total ordering.
but we've already seen that these objects don't map nicely to numbers,
so perhaps you mean "greater than" defined on some algebra of sums.
but here i see no nice way to define such a total ordering - so if you
do have one, you'll need to tell me what it is.
or you could argue that the expected value of a random selection from
N does has some well-defined (numeric) value. but as of yet, you have
not provided me with a good definition, other than insisting one
exists. a simple external reference to such a definition would
quickly resolve this matter - but as you repeated refuse to give me
one - i am left to wonder whether you're making it up.
so, to summarize. i believe you have proven the following statement:
The expected value of a random selection from the set of all
natural numbers, if it exists, is greater than the expected value of a random
selection from any finite set of numbers.
but that's not the whole enchilada. in fact, it misses the most important part.
this sort of problem occurs quite frequently when dealing with
infinite series. the fact that you're not familiar with it is what
worries me about your mathematical experience.
|
Request for Answer Clarification by
qarl-ga
on
18 Nov 2005 12:57 PST
gurgle...
it has been brought to my attention that the question i'm asking is
really very deep and not well understood:
http://www.missouri.edu/~klinechair/on-line%20papers/Standard%20Decision%20Theory%20Corrected.doc
as such - it's not a very appropriate question for google answers.
(although, it would have been nice if someone here had sent me that
link.)
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 13:22 PST
You conceived of the experiment of picking a natural number, any
natural number, under the uniform distribution. Of course this is not
possible in any practical sense, but let us consider it in the
abstract. I claim that the expected value n of this experiment is
infinitely large. To prove this, I challenge you to name a value m
that is greater than n. No matter what value you name for n, I point
out that the set of all natural numbers includes the subset {1, 2,
..., 2m}, the mean of which is m+1/2. But if we add 2m+1 to this set,
its mean can only increase. As you go on adding 2m+2, 2m+3, and so
forth, the mean keeps on increasing. Hence, the expected value must be
infinite if we can conceive of the experiment at all. This fully
answers your original question.
leapinglizard
|
Request for Answer Clarification by
qarl-ga
on
18 Nov 2005 13:54 PST
given that you have again ignored my specific questions - i ask that
you disengage from this question and allow someone else to answer it.
thank you.
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 14:20 PST
I am willing to address any concerns you may have about my answer to
your question. I cannot go farther afield. To minimize the scope for
confusion, I succinctly rephrased the proof in my previous
Clarification. I see no flaws in it.
leapinglizard
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 14:24 PST
Actually, I do see a typographical error that does not affect the
argument. Where I wrote "No matter what value you name for n", please
read m for n. I append an amended version for your reference.
leapinglizard
You conceived of the experiment of picking a natural number, any
natural number, under the uniform distribution. Of course this is not
possible in any practical sense, but let us consider it in the
abstract. I claim that the expected value n of this experiment is
infinitely large. To prove this, I challenge you to name a value m
that is greater than n. No matter what value you name for m, I point
out that the set of all natural numbers includes the subset {1, 2,
..., 2m}, the mean of which is m+1/2. But if we add 2m+1 to this set,
its mean can only increase. As you go on adding 2m+2, 2m+3, and so
forth, the mean keeps on increasing. Hence, the expected value must be
infinite if we can conceive of the experiment at all.
|
Request for Answer Clarification by
qarl-ga
on
18 Nov 2005 14:27 PST
no. sorry. please retract your answer or i will begin the refund process.
|
Clarification of Answer by
leapinglizard-ga
on
18 Nov 2005 14:33 PST
I regret that you are not pleased with my efforts. Of course you are
free to request a refund at any time.
leapinglizard
|
