We all know that, given two events A and B, the probability of the union A U B is given by the formula P(A U B) = P(A) + P(B) - P( AB) where AB represents the intersection of A and B. Most of us even know that

P(A U B U C) = P(A) + P(B) + P(C) - { P(AB) + P(AC) + P(BC) } + P(ABC)

In particular, if the events are independent, it becomes:

1 - P(A U B U C) = 1 - { P(A) + P(B) + P(C) } + { P(A)P(B) + P(A)P(C) + P(B)P(C) } - P(A)P(B)P(C)

This is equivalent to 

1 - P(A U B U C) = { 1 - P(A) } { 1 - P(B) } { 1 - P(C) }

It generalizes to n independent events, and this formula is known as the inclusion-exclusion principle. Let us consider n events A(1), A(2), ... , A(n) where A(k) is for a positive integer number, the property to be divisible by the square of the k-th prime number. We assume here that the first prime number is 2. These events are independent because we are dealing with prime numbers.  As n tends to infinity, 1 - P( A(1) U A(2) U ... U A(n) ) tends to the probability, for a positive integer number, to be square-free. Thus we have:

Beautiful Probability Theorem

The probability, for a positive integer number to be square-free (that is, not divisible by any square integer other than 1), is given by the formula below, where the product is over all prime numbers p > 1. 

If you are interested in this kind of topic, read my article on number densities, especially the exercise at the bottom of section 1, and the section on probabilistic number theory at the bottom of section 4. You might also be interested in my article entitled the fundamental statistics theorem revisited

Also, interestingly, the probability computed here is identical to the probability that two numbers are relatively prime.

Top DSC Resources

Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge

Views: 14081


You need to be a member of Data Science Central to add comments!

Join Data Science Central

Comment by Vincent Granville on December 22, 2016 at 12:38am

@Michael: The zeta function is useful to generalize the result. For instance, if you consider numbers not divisible by a cube, the formula is the inverse of zeta of 3. Same if you consider numbers not divisible by a cube nor a square, or numbers not divisible by a fifth power, the zeta function becomes handy.

© 2021   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service