Tag Archives: Probability

The Prime Bet

Let's say you sit in a pub, minding your own business, when all of a sudden a stranger walks up to you and offers you a bet:

We'll choose two positive integers at random. If they have any divisor in common (other than 1) I'll pay you a dollar, else you'll pay me a dollar. Are you in?

Apart from the question what kind of establishments you frequent, you should be wondering: is this a good bet for you?

When two integers have no divisors in common except the trivial divisor 1 we say they are coprime or relatively prime. 6 and 9 have the common divisor 3, so they are not coprime, whilst 8 and 9 only have the trivial common divisor 1, so they are coprime.

This makes you start thinking: "As numbers grow bigger, aren't there a lot of divisors out there? After all, half the numbers are even, so if we hit two even numbers, they'll have the factor 2 in common and I'll win. And then there's 3, 5, 7, ... Seems like a good deal!" Continue reading The Prime Bet

Are Primes Independent?

The question may sound silly, but I hope it will become apparent that it's very reasonable to ask. What we will examine here is the probabilistic interpretation of the prime distribution. So, essentially we ask: "What's the probability that a randomly chosen number is prime?" Those familiar with some basic probability theory know the notion of independency in this context, so the question I'm basically interested in here is if the probability to find a prime is independent of the preceding or following numbers. This post is a little out of the regular narrative, but it's something I have been thinking about recently, and I think it makes a cute article.

But one step back. First consider the following problem: We pick a number X not exceeding some (large) n at random. What are the odds this number is prime? Well, this is a classic example of a discrete probability, so the answer is positive cases over all cases, i.e.,

P(X\in\mathbb{P})=\frac{\pi(n)}{n},

where \mathbb{P} denotes the set of all primes, and \pi(n) is the prime counting function, i.e., the number of primes not exceeding n. Now, the famous Prime Number Theorem states that we can approximate \pi(n) with the elementary function

\pi(n)\sim\frac{n}{\log n}.

Don't worry too much about the exact meaning of the tilde, we will have plenty of opportunity to examine it further. For now just read it as "the left-hand side behaves similarly to the right-hand side". Now we can substitute this approximation in the calculation of the probability above, and obtain

P(X\in\mathbb{P})\sim\frac{n/\log n}{n}=\frac{1}{\log n}.

Continue reading Are Primes Independent?