Probability on Discrete Infinite Sets

Introduction

What does one need to know to answer the question below?

What is the probability of a random integer being divisible by 5?

The answer is practically obvious: every fifth number is divisible by $5$ and, therefore, the probability in question is $1/5.$ The numeric answer is immanently plausible and in fact is correct, however, the basic idea of selecting a random integer needs clarification. There are five equivalence classes $\{0,1,2,3,4\}$ modulo $5.$ (This are the remainders of division by $5.)$ A priori all events of selecting one of them are equiprobable such that each has the probability of $1/5.$ But the problem of selecting one equivalence class out of five is not the same as the one at hand which requires selecting a member of an infinite set. If all integers are equiprobable, then selecting one of them should be assigned the probability of zero. But this neither useful nor jibes with the reasonable expectation that the answer to the above question just ought to be $1/5.$

So we sidestep the question of selection and find another reasonable way to define the probabilities.

Definition

Uniformly random selection is only possible from a finite set; so this is what we do: we always select from a finite set but do this repeatedly, each time selecting from a bigger set. Here's a more accurate definition:

Let $q$ be a Boolean function (i.e., a function that takes values $true$ and $false)$ defined on the set $\mathbb{N}$ of integers and $q(n)$ the number of integers $k\in\mathbb{N}_{n}=\{a:\space 1\le a\le n\}$ for which $q(k)=true.$ We think of $\space\displaystyle\frac{q(n)}{n}$ as the probability of an integer from $\mathbb{N}_{n}$ to have the property $q.$

Now, the probability that a random integer has property $q$ is defined as $\space\displaystyle\lim_{n\to\infty}\frac{q(n)}{n}.$

Let's see how this definition works for the problem of divisibility by 5.

Let $n=5m + r,$ where $0\le r\le 4\}.$ The number $q(n)$ of integers not exceeding $n$ and divisible by $5$ equals $\displaystyle q(n)=\bigg\lfloor\frac{q(n)}{5}\bigg\rfloor =m,$ where $\lfloor a\rfloor$ is the floor function. Further,

$\displaystyle \frac{q(n)}{n}=\frac{m}{n}=\frac{(n-r)/5}{n}=\frac{1}{5}-\frac{r}{5n},$

implying that indeed, $\displaystyle \lim_{n\to\infty}\frac{q(n)}{n}=\frac{1}{5}.$

Reinforcement

Following are several simple questions that could be unswered within the above framework.

What is the probability that a random integer will be coprime with $6?$

In the six element set $\{0,1,2,3,4,5\}$ of the remainders modulo $6,$ only $1$ and $5$ can be said not to have common factors with $6.$ More acurately, no integer in one of the forms $6k\pm 1$ has common factors with $6,$ whereas $\mbox{gcd}(6k\pm 2,6)=2$ and $\mbox{gcd}(6k+3,6)=3,$ not to mention that $6k$ is outright divisible by $6.$ Thus the probability in question is $\displaystyle\frac{2}{6}=\frac{1}{3}.$

What is the probability that at least one of two random integers will be coprime with $6?$

The probability that a random integer is not coprime with $6$ is $\displaystyle 1-\frac{1}{3}=\frac{2}{3}.$ Assuming that divisibility of an integer by $6$ is a provate matter, independent of te divisibiity of another random integer, the probability that both random integers are divisible by $6$ is $\displaystyle \frac{2}{3}\cdot \frac{2}{3}=\frac{4}{9},$ making probability in question $\displaystyle 1-\frac{4}{9}=\frac{5}{9}.$

What is the probability that the square of a random integer will end with $1?$

A square of a number ends in $1$ if the number ends in either $1$ or $9$ out of all possible digits, so the answer is $\displaystyle \frac{2}{10}=\frac{1}{5}.$ The same are the probability that the square ends with $4$ (for the endings of $2$ and $8,)$ $9$ (for the endings of $3$ and $7,)$ $6$ (for the endings of $4$ and $6)$ and $\displaystyle \frac{1}{10},$ for each of the endings $0$ and $5,$ respectively.

What is the probability that the square of a random integer will end with $11?$

No square ends with $11;$ the probability is $0.$

What is the probability that the cube of a random integer will end with $11?$

Cubes do end with $11:$ $71^{3}=357911.$ You can check that this is the only such cube. Since only the last two digits of an integer affect the last two digits of its cube, the probability in question is $\displaystyle \frac{1}{100}.$

What is the probability that, for a random integer $n,$ $2^n$ will end with $12?$

Here is a list of successive endings of the powewrs of $2:$

$\begin{align} 2,4,8,16,32,64,&28,56,12,24,48,96,\\ &92,84,68,36,72,44,88,76,52,04,08,\ldots \end{align}$

From this moment on, the sequence of the last two digits will repeat itself, making it periodic with period $20.$ Even though the periodicity only starts with the second term ($4)$ of the sequence, we still can say that every twentieth power of two ends with $12$ because at the limit an extra term loses all significance. The probability in question is, therefore, $\displaystyle \frac{1}{20}.$

What is the probability for two random integers to be coprime?

This is an interesting question that deserves a page of its own.

References

  1. A. M. Yaglom, I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol I, Dover, 1987

|Contact| |Front page| |Contents| |Algebra| |Probability|

Copyright © 1996-2018 Alexander Bogomolny

71471176