Conference rusure::math

> For example, can't one say that there's a 50 percent chance
> that an integer chosen randomly is even ?

You need to define the experiment that produces the integer.
Ultimately, the definition of randomness is tied up with the concept
of 'equally likely outcomes'.  But there is no way to prove that
outcomes are 'physically' equally likely; there are only plausibility
arguments from things like symmetry.  To find out what things are
plausible to assume as equally likely, we perform (physical) experiments.

The mathematics of probability allow you to calculate the likelihood of a
composite event given the probability of the elementary events that make up
the composite event, but math can't get you those elementary probabilities;
they must ultimately be assumed.

If you are selecting an integer from a sample space consisting of the integers,
and you assume that any integer is as likely to show up as any other, then
the probability of the integer being even can be shown (by that assumption
and the math of probability) to be 1/2.

If you'd like to see some interesting examples of how the probability of
an event is sensitive to the terms of the experiment, see
Papoulis' book 'Probability, Statistics, and Random Variables' chapter 1 in
which the author shows how a seeemingly innocent question about points in
circles can produce 3 different answers all (apparently) correct.
The difference turns out to be in what are assumed to be equally likely
outcomes.

> And what about the infinite
> set of reals between any two distinct real numbers--can't one talk
> about a number chosen randomly from this set (even if it would take
> forever to write that number down)?

Sure.  This happens all the time.  I can't write down all the digits of
pi or e, but I work with them all the time.

> Is the problem in the definition of randomness?  Is there really an
> issue? 

Well, I'm not sure what problem your'e referring to.  Could you
explain more ?

    re .1
    
    The modern theory of probability is based on measure theory where
    the basic events are identified with interval whose measure is well
    defined in terms of the boundries.
    
    In these terms, one can say that the probability of selecting a
    rational number from the real interval [0,1] is 0, because the measure
    of the set of rational, (either borel or lesbesque) is 0.
    

>If you are selecting an integer from a sample space consisting of the integers,
>and you assume that any integer is as likely to show up as any other, then
>the probability of the integer being even can be shown (by that assumption
>and the math of probability) to be 1/2.

The trouble is, these things are dependent on some concepts that are not
obvious. Suppose I take the set of positive integers and rearrange them so they
are in the order 
	1,2,3,5,4,7,9,6,11,13,8,15 ...
Both the odd and even integers are each in increasing sequence, but in each
triplet two odd and one even integer occur. Now if you sample from any 
subsequence of this sequence, of ANY size, you will tend to get twice as many
odd numbers as even ones. What's more, if this were the 'natural' order of the
integers that you were taught as a child, you might be very tough to convince
that there are just as many evens as odds. 

    For a random number chosen from a fixed interval, you can define what
    is desired by using the distribution function.  That is, if X is a
    random variable in the range [0..1], you want a uniform distribution,
    and 0 <= Y <= 1, then
		P( X <= Y ) = Y
    means that the probability that X <= Y is equal to Y.

> The trouble is, these things are dependent on some concepts that are not
> obvious. Suppose I take the set of positive integers and rearrange them so they
> are in the order 
>	1,2,3,5,4,7,9,6,11,13,8,15 ...

I'm not well informed on transfinite math or measure theory, but let me try
to respond to .2.

There is an implicit assumption here that the two sets (the 'natural' ordering
and your reordering) are equal.

What is the definition of equality for sets of infinite cardinality ?

Since most of the finite subsequences of the reordering you created
are unequal (have different members) to the corresponding finite subsequence
of the 'natural' sequence of the same cardinality, I might argue that these
are different sets.  The sample spaces of the corresponding experiment
(select a number from this finite set) are different, so it seems we
are talking about different experiments.  Showing a simple one to one
correspondence between two sets at infinity is apparently not enough to show
equality.

I think what may be happening here is that we have reduced the evaluation
of measures of infinite sets to measures on finite sets that are somehow
supposed to have the same 'statistics'.  I suspect that this is suspect :-).

I still maintain that there is some logically consistent way to show that the
probability of choosing an even number from the set of positive integers is
1/2 because I dimly recall reading a proof of something similar to this.
I'll see if I can dredge it up.

Are there any transfinite or probability gurus out there that can help
straighten this out ?

> I still maintain that there is some logically consistent way to show that the
> probability of choosing an even number from the set of positive integers is
> 1/2 because I dimly recall reading a proof of something similar to this.

    See note 697.  Let Z(N) = {positive integers <= N}  Z(4) = {1,2,3,4} etc.
    
    P(even)  =  limit ( <Number_of_even_numbers_in_Z(N)> / N ) = 1/2
  		N->oo

    Although a clever Yarbrough might come up with a similar "proof"
    that the probability is really 1/3...
    
      John

>>	1,2,3,5,4,7,9,6,11,13,8,15 ...
>...
>There is an implicit assumption here that the two sets (the 'natural' ordering
>and your reordering) are equal.
>
>What is the definition of equality for sets of infinite cardinality ?

That they can be put into 1-to-1 correspondence with each other; i.e. that it is
not possible to find an element in one set for which there is no corresponding
element in the other. Thus there are as many odd integers as integers
(by the correspondence
	1 2 3 4 5  6  7 ...
	1 3 5 7 9 11 13 ...)
and also as many rationals as integers (again, a complex 1-1 mapping can be
constructed), but there are more reals than rationals (since given any listing
of the rationals, a real number can be constructed which cannot appear in the
list). 

    re .7
    
    The bijection defines equality of cardinality.  There may be other
    properties of interest such as measure, which a simple bijection
    does not preserve. For example set up a bijective correspondence
    between the Cantor Set (gotten by extracting middle thirds from
    intervals) and the set of irrational numbers.  One set has measure
    0 and the other measure 1.  
    
    In addition to count and measure properties one can preserve structure
    as in the case of homomorphs and isomorphs.  The only way for two
    sets to be equal in the sense of identitical, is that they have
    the same members, or equivalently each one is a subset of the other.
    
    

correction to .1:

Got the title wrong.

The Papoulis reference is:

page 9,
'Probability, Random Variables, and Stochastic Processes', 2nd edition,
McGraw-Hill

>There may be other
>properties of interest such as measure, which a simple bijection
>does not preserve.

For the benefit of those of us not familiar with the definition of
measure (myself included), could you briefly define it ?
    
>The only way for two
>sets to be equal in the sense of identical, is that they have
>the same members, or equivalently each one is a subset of the other.

So this holds for infinite sets as well as finite sets.
Let me go take a look at 697 and I'll come back later.

Re .0:

>I understand that one would need an infinite amount of time just to
>enumerate an average random positive integer, for example.

Can you explain why you believe this?

I believe that all integers are of finite magnitude.  (Eric's statement in
718.7 would seem to claim otherwise, however).  I assume I can find a
definition of "integer" which agrees with this belief, if I had to look.
But I would hope that the issue is too obvious to require that.

Given this belief, it should take a finite time to express such a number
in any specific radix (should take a finite time to write the number down).

Or do you mean something different by "enumerate"?
				/AHM/THX

    RE: .12
    
    Well, Alan, I'll do my best to explain my belief:
    
    Since there is no upper limit on the set of positive integers, then the
    "average random positive integer" would be of infinite length. I used
    the term "average" where, perhaps, the term "typical" would have been
    more appropriate (and I'm not even sure that "typical" is much better).
    Even though there are positive integers which can be enumerated in a
    finite amount of time, they make up only an infinitesimal subset of all
    positive integers.
    
    Does this make sense?  Can anyone else express it more clearly?
    

    Re .12:
    
    >> I understand that one would need an infinite amount of time just to
    >> enumerate an average random positive integer, for example.
    
    > Can you explain why you believe this?
    
    Suppose you have a computer that can get and store a trillion digits a
    second.  What is the average time this computer will take to finish
    getting and storing a random integer?
    
    
    				-- edp

   The following algorithm produces a random non-negative integer.
   It generates such a number starting with the least significant bit.

   R1.	(Initialize)  I <- 0.

   R2.  (Generate and output the bit having coefficient 2**I).  Let
	rand() be a function that effectively returns random numbers
	uniformly distributed in the half-open range [0..1).
	If rand() >= 0.5 then Output "1" else Output "0".

   R3.	(Iterate).  I <- I + 1; Go to step R2.

Most users of this algorithm needn't worry about the performance.  :^)

    Or, to put it yet another way:  The average value of a random positive
    integer is unbounded (which is the same as "approaching infinity",
    or "oo").
    
    Or, to put it still another way: (vague pseudo-proof)
    
    	If R(x) = some random integer uniformly distributed over the
    		range [1,x]
    	Then Average ( R(x) ) = (x+1)/2
    
    Therefore
    
    	If a "random positive integer" may be defined (questionable) as
    	    the value of R(x) as ( x -> oo )
    	Then
    	    an "Average random positive integer" =  Lim   (x+1)/2
    						   x -> oo
    	    Which is
    						 =  (oo + 1)/2
    						 =  oo

    
    --  Barry

>> 722.13    
>>    Since there is no upper limit on the set of positive integers, then the
>>    "average random positive integer" would be of infinite length. I used
>>    the term "average" where, perhaps, the term "typical" would have been
>>    more appropriate (and I'm not even sure that "typical" is much better).
>>    Even though there are positive integers which can be enumerated in a
>>    finite amount of time, they make up only an infinitesimal subset of all
>>    positive integers.
>>    
>>    Does this make sense?  Can anyone else express it more clearly?

     If by the "length" of a positive integer you mean the number
     of digits that it takes to write it in base ten, then
     *every* positive integer has finite length.  If by
     "enumerating" you mean churning out those digits, say, by a
     Turing machine, then *every* positive integer can be
     enumerated in finite time.

     If you estimate that there are, say, 10 ** 80 (or 1.0E+80)
     electrons in the universe and that only positive integers
     less than that can be "physically enumerated" then, with the
     exception of some small ones at the beginning :-), "most"
     positive integers are too large to be physically enumerated.

                (Number of integers <= n that can be)
          lim   (physically enumerated              )
        n -> oo ------------------------------------- = 0
                                n

     Remember that any individual positive integer is "finite"
     and can be represented by a finite sequence of digits.
     Counts or sums or averages taken over the first n positive
     integers [in the usual ordering] may become arbitrarily
     large as n increases; but don't confuse such an "infinite
     limit" with a "typical positive integer."

    re .15
    
    When do you stop? *Do* you stop?  What use is this procedure?
    How long will it take someone (you know who you are) to write
    a DCL procedure to do this :-)?

The length of the randomly generated integers will be infinite.  This
is because the size (in decimal digits) of a number is proportional to
the log of the number, and the log of infinitity is infinity.

Another way of looking at this nonscientifically is figuring the chance of the
random integer being less than 1Ex where x is any integer.  However, there are
10 times as many numbers that are less than 1E(x+1) so it is 9 times as likely
the number is between 1Ex and 1E(x+1). 

Similarly, it is 99 times as likely a number between 1Ex and 1E(x+2) will
appear.

Taking this to its logical conclusion, it is infinitely more likely that a
number larger than any number you come up with will be generated, no matter how
big your number is. 

-Mike

Gilbert's algorithm looks like it *always* produces an infinitely long
string of bits.

My idea of random integers is that they can be all sorts of lengths,
but must INCLUDE short ones too.  Gilbert's algorithm looks like it would
never emit a short number.

For that matte, his algorithm never stops, so it never announces exactly
what number it has emitted.

My idea for a random number generator would be something like:

	Pick a random angle from 0 through pi/4 radians, take the tangent,
	and take the integer part.

This algorithm definitely emits specific numbers.  On the other hand,
it isn't quite evenly distributed.  Perhaps the tangent should be sent through
another function before we take the integer part ?

/Eric

In .15, I tried for a uniform distribution.  If a different distribution
is acceptable, we can take .20 as a starting point, ...

	Pick a random angle X from 0 through pi/2 radians, with uniform
	distribution (so that P(X<=Y) = Y*2/pi), and let Z be tan(X).

Now Z has the range 0..infinity, and the distribution of Z is given by:

	P( Z <= Y ) = arctan(Y) * 2/pi.

    The problem is hard if you're looking for a uniform distribution.
    If a non-uniform distribution is OK, it's easy.  A simpler way to
    generate a random number than the tangent method is to toss a coin
    until you get a tail.  If, on the nth throw, you get a tail, your
    number is n.  If you're willing to throw coins for a while, you
    will eventually generate every integer you can name.
    				Jeff
    

    Isn't this all a bit circular?  How do you pick a random real --
    it's the same argument with the same problems and contradictions
    as selecting a "random integer".  You can't do it.  You have to
    go thru some kind of limit process.
    
      John

For what you call a "non-uniform" distribution, you can simply pick an
integer from a finite subset (e.g., pick always "7").

The sentence "pick a random integer" is not mathematically defined, so
therefore there is no point of evaluating the probablility of this
integer being odd, even, prime, etc.

The coin method (for example) does define a true experiment, and then we
can argue about the probability of even, half, etc. About the tangent
method and such - I think, again, the sentence "pick a random real number
in the range X to Y" is not mathematically defined, because it is equivalent
to the previous statement.

/Nitsan