A Selection of Problems from A.A. Markov’s Calculus of Probabilities: Problem 3 – Solution to Parts 1 and 2

Review statement of Problem 3.

Solution:   For brevity, let \[\left\lbrace \frac{p(p-1) \cdots (p-m+1)}{1\cdot2\cdot\cdots\cdot m}\right\rbrace^k = Z_p ,\] for any number \(p\).

On each draw, the number of selected tickets can represent any set of \(m\) numbers from all \(n\) numbers \(1, 2, \dots, n\).

Corresponding to this, on one draw we distinguish \(\frac{n(n-1)\cdots(n-m+1)}{1\cdot2\cdot\cdots\cdot m}\) equally likely cases, and on \(k\) draws, we distinguish  \(\left\lbrace \frac{n(n-1)\cdots(n-m+1)}{1\cdot2\cdot\cdots\cdot m}\right \rbrace^k = Z_n\) equally likely cases.⁹

Each of the preceding exhaustive and disjoint cases consists of the appearance of \(k\) specific sets of \(m\) numbers on the \(k\) draws considered.

Establishing in this way those cases that we will consider, and showing the total number of them, we proceed to determine the probabilities of the events referred to in the problem by calculating the number of cases favorable to them.

If \(i\) specific numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\) do not appear, then for one draw, instead of  \(\frac{n(n-1)\cdots(n-m+1)}{1\cdot2\cdot\cdots\cdot m}\), there remain \(\frac{(n-i)(n-i-1)\cdots(n-i-m+1)}{1\cdot2\cdot\cdots\cdot m}\) cases, and for \(k\) draws, we have  \(\left\lbrace\frac{(n-i)(n-i-1)\cdots(n-i-m+1)}{1\cdot2\cdot\cdots\cdot m}\right\rbrace^k = Z_{n-i}\) cases, instead of \(\left\lbrace \frac{n(n-1)\cdots(n-m+1)}{1\cdot2\cdot\cdots\cdot m}\right \rbrace^k = Z_n\).

Thus, the probability that, for the \(k\) draws considered, \(i\) specific numbers do not appear is given by the fraction \[\frac{Z_{n-i}}{Z_n} = \left\lbrace\frac{(n-i)(n-i-1)\cdots(n-i-m+1)}{n(n-1)\cdots(n-m+1)}\right\rbrace^k.\]

Then the number of cases for which the \(i\) specific numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\) do not appear and one specific number \(\beta_1\) does appear can be expressed by the difference \(\Delta Z_{n-i-1} = Z_{n-i} - Z_{n-i-1}\), where according to what we just said, \(Z_{n-i}\) represents the number of cases in which the numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\) do not appear, and \(Z_{n-i-1}\) the number of those cases in which, besides the numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\), the number \(\beta_1\) also does not appear.

In a similar manner, the number of cases in which the numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\) do not appear and two specific numbers do appear can be expressed by the second difference \(\Delta^2 Z_{n-i-2} = \Delta Z_{n-i-1} - \Delta Z_{n-i-2}\), where \(\Delta Z_{n-i-1}\) represents the number of all cases in which the number \(\beta_1\) does appear and the numbers \(\alpha_1, \alpha_2, \dots, \alpha_i\) do not appear, and \(\Delta Z_{n-i-2}\) the number of those cases in which, besides \(\alpha_1, \alpha_2, \dots, \alpha_i\), the number \(\beta_2\) also does not appear.

In view of the possibility of continuing similar reasoning, it is not difficult to conclude that, in general, the number of cases in which \(i\) specific numbers do not appear and another \(l\) specific numbers do appear can be represented by the \(l\)^th order difference \(\Delta^l Z_{n-i-l}\), which is equal to: \[Z_{n-i} - \frac{l}{1}Z_{n-i-1} + \frac{l(l-1)}{1\cdot2} Z_{n-i-2} - \cdots \pm Z_{n-i-l}.\]

Then the probability that, in the \(k\) draws considered, \(i\) specific numbers do not appear and another \(l\) specific numbers do appear is equal to¹⁰ \[\frac{\Delta^l Z_{n-i-l}}{Z_n}.\]

Continue to Markov's solution of Problem 3, Parts 3, 4, and 5.

Skip to statement of Problem 4.

[9] In other words, \(Z_p = \binom{p}{m}^k\) for any \(p\), so that \(Z_n = \binom{n}{m}^k\).

[10] For example, suppose \(n = 10, m = 3,\) and \(k = 5\). The total number of outcomes is \(Z_{10}=\binom{10}{3}^5=120^5\). For question (1), let \(i = 2\), so that we consider the number of selections without two numbers \(\alpha_1\) and \(\alpha_2\) in any of the 5 draws. There are \(Z_8=\binom{8}{3}^5=56^5\) such selections. Hence, the probability that \(\alpha_1\) and \(\alpha_2\) do not appear is \(\frac{Z_8}{Z_{10}}=\frac{56^5}{120^5} \approx 0.02213\). For question (2), the number of selections without \(\alpha_1\) and \(\alpha_2\) and containing another number \(\beta_1\) is: \[\Delta Z_7 = Z_8 - Z_7 = \binom{8}{3}^5-\binom{7}{3}^5 = 498~209~901.\] Of these, \[\Delta Z_6 = Z_7 - Z_6 = \binom{7}{3}^5 - \binom{6}{3}^5 = 49~321~875\] do not contain some other number \(\beta_2\). So, the number of selections without \(\alpha_1\) and \(\alpha_2\) and containing \(\beta_1\) and \(\beta_2\) is: \[\Delta^2 Z_6 = \Delta Z_7 - \Delta Z_6 = Z_8 - 2 Z_7 + Z_6 = 448~888~026,\] and the probability of this event is \(\frac{\Delta^2 Z_6}{Z_{10}} = \frac{448~888~026}{120^5} \approx 0.01804\). Similarly, \(\frac{\Delta^3 Z_5}{Z_{10}} = \frac{Z_8 - 3Z_7 + 3Z_6 - Z_5}{120^5} \approx 0.01618\).