- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by royalchickenThe set of rational numers is countable. We can map any rational on to an integer by the following operation (cribbed from http://www.cut-the-knot.org/do_you_know/countRats.shtml):
What is the probability that a randomly selected rational number (fraction in lowest terms) has an even denominator?
Every positive rational number has a unique representation as a fraction m/n with mutually prime integers m and n. Each of m and n has its own prime number decomposition. Let these be
m = p1^a1 p2^a2 ... pr^ar, and n = q1^b1 q2^b2 ... qs^bs,
Form the number K(m/n) = p1^(2a1) p2^(2a2) ... pr^(2ar) q1^(2b1-1) q2^(2b2-1) ... qs^(2bs-1).
K is a function that maps any rational positive number onto a positive integer. A point of note is that K is a 1-1 correspondence.
Continuing with my own logic:
If we pick a random integer X and generate its corresponding rational number M/N then we have a good method of randomly selecting a rational number. If X is odd then there will be no powers of 2 in the prime number decomposition of X. So if X is odd N cannot be even.
If X is even then its prime number composition will contain some power A (A>0) of 2. However a corresponding power of 2 will only appear in the prime number composition of N if A is ODD (if A is even then the power of two will contribute to the prime number decomposition of M).
So N is odd IF (X is Even) AND (A is Odd)
the probability is 1/2 * 1/2 = 1/4
However I suspect I may have gone wrong somewhere, possibly in the assumption that A is randomly ditributed...
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by iamatigerYes, I was wrong - I think the proportion of Odd A's to even A's is 1/2 + 1/8 + 1/32 + 1/128... = 2/3. So the probability of an even denominator is 1/2 * 2/3 = 1/3
If X is even then its prime number composition will contain some power A (A>0) of 2. However a corresponding power of 2 will only appear in the prime number composition of N if A is ODD (if A is even then the power of two will contribute to the prime number decomposition of M).
So N is odd IF (X is Even) AND (A is Odd)
the probability is 1/2 * 1/2 = 1/ ...[text shortened]... may have gone wrong somewhere, possibly in the assumption that A is randomly ditributed...
I think you got it right the second time....
Pick a rational number. The numerator (N) is odd (NO) or even (NE), and the denominator (D) is odd (DO) or even (DE).
Case 1: NO+DO, Since the denominator is odd, there is no way that simplifying the fraction will result in a even denominator.
Case 2: NE+DO, Since the denominator is odd, there is no way that simplifying the fraction will result in a even denominator.
Case 3: NO+DE, That the denominator is even, it means the it's divisible by 2. The numerator isn't, so no matter how much you simplify the fraction, the 2 in the denominator will remain.
Case 4: NE+DE, Now both the numerator and the denominator are divisible by two, wich means that when you simplify the fraction the 2's will cancel out, wich leaves an odd numerator and denominator.
Of the four cases, only case 3 has an even denominator. So the ratio even : odd is 1 : 3
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by TheMaster37Thanks for agreeing with me, but I have a few issues with your method : 🙂
I think you got it right the second time....
Pick a rational number. The numerator (N) is odd (NO) or even (NE), and the denominator (D) is odd (DO) or even (DE).
Case 1: NO+DO, Since the denominator is odd, there is no way that s ...[text shortened]... y case 3 has an even denominator. So the ratio even : odd is 1 : 3
a) One case out of 4 is a prob of 1/4, not 1/3
b) NE+DE could be something like 2/8 which simplifies to 1/4 (still an even denominator)
c) I think your method of generating a random number was perhaps biased - if you generate a random numerator and then a random denominator you are stacking the odds because disproprtionately many of your generated numbers will simplify to simple fractions like 1/2.
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by FiathahelIts an interesting question - of course there is exactly one even number for every odd number - so I would have thought that the probability of getting an even number would be 1/2. But can anyone come up with any method at all of randomly (and fairly) selecting an integer when there is no upper or lower bound to the set of integers from which you are to select one?
Can someone proof for me that the probability of picking an even number out of all numbers is 1/2?
Cause this is what you all use, and this is what I doubt on.
Originally posted by iamatigercrap
Thanks for agreeing with me, but I have a few issues with your method : 🙂
a) One case out of 4 is a prob of 1/4, not 1/3
b) NE+DE could be something like 2/8 which simplifies to 1/4 (still an even denominator)
c) I think your method of generating a random number was perhaps biased - if you generate a random numerator and then a random denominator ...[text shortened]... use disproprtionately many of your generated numbers will simplify to simple fractions like 1/2.
THe answer is 1/3. Good going iamatiger!
Here's my proof. Let S(d) be the number of rationals in (0,N] with denominator d for some integer N.
Clearly, we are counting pairs (m,d) such that gcd(m,d)=1. If d is prime, then:
S(d) = N(1-1/d)
If d has k distinct prime factors, then:
S(d) = N(1-1/p1 - 1/p2 - ...-1/pk + 1/p1p2+...+1/p1p2p3p4p5...pk)
= N(1-1/p1)(1-1/p2)...(1-1/pk)
Thus if d is odd, then for all a, S(d*2^a) = S(d)/2.
Thus for every even-denominator rational, there are two odd-denominator rationals. Thus the probability we want is 1/3.
This illustrates the fact that being even guarantees the presence of a prime factor, 2, while being odd guarantees nothing.
Originally posted by royalchickenThere are some errors in your proof
THe answer is 1/3. Good going iamatiger!
Here's my proof. Let S(d) be the number of rationals in (0,N] with denominator d for some integer N.
Clearly, we are counting pairs (m,d) such that gcd(m,d)=1. If d is prime, then:
S(d) = N(1-1/d)
If d has k distinct prime factors, then:
S(d) = N(1-1/p1 - 1/p2 - ...-1/pk + 1/p1p2+...+1/p1p2p3p4 ...[text shortened]... t being even guarantees the presence of a prime factor, 2, while being odd guarantees nothing.
First of all you forgot a d in every line : for example S(d) = dN(1-1/d). This gives if S(d)=dN(1-1/p1)(1-1/p2)...(1-1/pk) then S(d*2^a)=(d*2^a)*N(1-1/2)(1-1/p1)(1-1/p2)...(1-1/pk)=S(d)*2^(a-1)
So here you got a problem.
Ok, I made a typo, but not exactly the one Fiathahel meant. If S(d) referred to the number of d-denominator rationals in (0,N] as I said, then indeed
S(d) = dN(1-1/p1)....(1-1/pk) as Fiathehel said. However, I meant to say that S(d) counts rationals with NUMERATORS IN (0,N], ie those rationals in (0,N/d] so that the rest is as I said.
S(d) = N(1-1/p1)(1-1/p2)....(1-1/pk) is p1,p2,...pk are the distinct prime factors of d.
So for any prime r, S(dr^a) = (1-1/r)S(d), so S(d*2^a) = S(d)/2, which shows that the probability of choosing a random even-denom. rational is 1/3.
In this situation, we can count the rationals with a maximum numerator regardless of changes in denominator. In the situation you mention based on my typo, we have the number of possible numerators, dN rather than N, growing as the denominator grows, which makes S(d) pretty meaningless since we can't make comparisons among different denominators.
The proof from which I just exorcised a typo can also be stated more clearly by saying that S(d) = (N/d)*P(d), where P is the Euler totientfunction that counts the number of integers less than and prime to d. Since P is multiplicative, S(2d) = (N/2d)*P(2d) = (N/2d)*P(d)*P(2) = (N/d)*P(d)/2 = S(d)/2.