Probability that a Random Integer...
Date: 7/18/96 at 2:42:49 From: don mcmahon&sheri anderson Subject: Probability that a Random Integer... I started trying to figure out what the probability that an integer chosen randomly would be an integer multiple of a given integer "n" (or perhaps of a prime "p")...and then the probability that it would be a multiple of, say, the integers 2...7, and so on. I think I got stuck on trying to figure out how to formulate the "or" probabilities and add things up properly. I think my idea was to generate a sequence P(n) where P(n) would be the probability a random integer would be a multiple of at least one of the integers from 2 up to n. I think I got tangled up in the lattice of integers and then had to go settle a civil war in the sandbox in the backyard. Can you head me in the right direction? Sheri Anderson
Date: 7/18/96 at 19:58:55 From: Doctor Tom Subject: Re: Probability that Random Integer... Well, to be precise (and that's what we mathematicians have to be!), I have to know exactly what you mean by "an integer chosen randomly". If you're talking about the entire infinite set of integers, there is no way to do this without some sort of a distribution function over the integers, and there is no such function that gives an "equal probability" for all integers. To make things precise, here's what I'll assume you mean: If M is a very large integer, and we randomly (with equal probability) choose an integer between 0 and M, what's the probability that it is divisible by n? For any fixed M, you can work this out, and then if we take the limit of these probabilities as M goes to infinity, I think that will be what you want. So if your question just concerns a single number n, the answer is that the limiting probability is 1/n. For large M, roughly 1/n of the integers less than M are divisible by n, and the error is smaller and smaller as M gets larger and larger. If you ask, "What's the probability that a number is divisible by n and m?", I think you begin to see the problem - for example, if n = 2 and m = 4, it's 1/4, since anything divisible by 4 is automatically divisible by 2. If you ask the general question, "What's the probability that a number is divisible by all of the numbers n1, n2, n3, ..., nx?" the answer is "if z = the least common multiple of n1, n2, ..., nx, then the probability is 1/z". The least common multiple of a set of integers is the smallest integer that all of them divide. For example, the least common multiple of 4 and 6 is 12. Of 7 and 11 is 77. And so on. To find the least common multiple of a set of numbers, factor all of them into prime factors. For each prime that appears anywhere in the list, find the number in which the highest power of that prime appears, and include that power of the prime in a product. The grand product is the LCM (least common multiple). For example, to find the LCM of 24, 125, 32, 100, and 444, where "*" indicates multiplication, and "^" exponentiation: 24 = 2^3*3^1 125 = 5^3 32 = 2^5 100 = 2^2*5^2 444 = 2^2*3^1*37^1 LCM = 2^5*3^1*5^3*37^1 I hope it's obvious why this works, and I won't bother to multiply out the number in my example. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.