You are here

Euler's Analysis of the Genoese Lottery - Probabilities in the Genoese Lottery (continued)

Author(s): 
Robert E. Bradley
pk,i k = 1 k = 2 k = 3 k = 4
i=0
n-t

n


(n-t)(n-t-1)

n(n-1)


(n-t)(n-t-1)(n-t-2)

n(n-1)(n-2)


(n-t)(n-t-1)(n-t-2)(n-t-3)

n(n-1)(n-2)(n-3)

i=1
t

n


2t(n-t)

n(n-1)


3t(n-t)(n-t-1)

n(n-1)(n-2)


4t(n-t)(n-t-1)(n-t-2)

n(n-1)(n-2)(n-3)

i=2
t(t-1)

n(n-1)


3t(t-1)(n-t)

n(n-1)(n-2)


6t(t-1)(n-t)(n-t-1)

n(n-1)(n-2)(n-3)

i=3
t(t-1)(t-2)

n(n-1)(n-2)


4t(t-1)(t-2)(n-t)

n(n-1)(n-2)(n-3)

i=4
t(t-1)(t-2)(t-3)

n(n-1)(n-2)(n-3)

Table 2: Summary of Problems 1-4

Euler's reasoning is entirely elementary, and each Problem builds on the results of the previous one. If k=1, the player is choosing just one number from among n. Since t of these will be winning numbers, p1,1 = t/n and p1,0=1- p1,1.

To calculate the probabilities when k=2, we can think of the player as choosing the two numbers one at a time. Therefore, there are n-1 ways to choose the second number, having made the first choice from among n. This accounts for the denominator n(n-1) in all three of the probabilities in the second column of Table 2. The case k=2, i=2 arises from choosing one of the t winning numbers first, and one of the remaining t-1 winning numbers next. Similary, in the calculation of p2,0, the player first chooses one of the n-t losing numbers, and then chooses one of the remaining n-t-1 losing numbers. The interesting case is i=1. There are two ways this can happen, either by choosing a winning number followed by a losing number, or by choosing a losing number followed by a winning number. There are t good choices and n-t bad choices, so the numerator of p2,1 has to be 2t(n-t).

Elements of the pattern in Table 2 gradually come into focus quickly. Particularly noteworthy is the presence of binomial coefficients. The details of Euler's solutions of Problems 1-4 make this identification certain, as the coefficient of every entry in each column, except the first and last, arises a sum of two coefficients in the previous column, thereby obeying precisely the same recursive formula as the entries in Pascal's triangle. For example, one can bet on k=4 numbers, and get i=2 of them correct in two different ways: either by matching 2 of the first 3 numbers bet upon, and then failing to match on the fourth one, or by matching only 1 of the first 3, and then succesfully matching the fourth one. Therefore, the binomial coefficient

æ
ç
ç
è
k
i
ö
÷
÷
ø
will always be a factor of pk,i. Let's introduce one more piece of modern notation, by letting
sk,i = pk,i

æ
ç
ç
è
k
i
ö
÷
÷
ø
,       so that    pk,i = æ
ç
ç
è
k
i
ö
÷
÷
ø
sk,i.

In Problem 5, Euler asks for the general form of pk,i. He introduces r=n-t and writes out the cases k=1, 2, ¼, 6 in this new notation. Observing the pattern, sk,i is seen to be:

t(t-1)¼(t-i+1)r(r-1)¼(r-(k-i)+1)

n(n-1)(n-2)¼(n-k+1)
,
where 0 £ i £ k, 1 £ k £ t £ n, and k £ r=n-t.

Euler does not use this notation, nor does he explicitly give a formula for the general value of sk,i. His notation is as follows:

Ai
=
s1,i
Bi
=
s2,i
Ci
=
s3,i
Di
=
s4,i
etc.

In Corollary 1 to Problem 5, Euler observes that the sk,i can be given recursively. We may give an explicit formulation as follows. Let

s1,0= n-t

n

and
s1,1= t

n

from Problem 1; then for k > 1, and 0 £ i < k:
sk,i = r-(k-i)+1

n-k+1
  sk-1,i.
Also,
sk,k = t-k+1

n-k+1
  sk-1,k-1.
In Euler's notation, these formulas are given as follows:
A1= t

n
,     A0= r

n
;

B2= t-1

n-1
A1,     B1= r

n-1
A1,     B0= r-1

n-1
A0;

C3= t-2

n-2
B2,    C2= r

n-2
B2,     C1= r-1

n-2
B1,     C0= r-2

n-2
B0;

D4= t-3

n-3
C3,     D3= r

n-3
C3,     D2= r-1

n-3
C2,     D1= r-2

n-3
C1,     D0= r-3

n-3
C0;

etc.

Robert E. Bradley, "Euler's Analysis of the Genoese Lottery - Probabilities in the Genoese Lottery (continued)," Convergence (August 2010)