A probability problem suitable for Problem-Based Learning

Un problema de probabilidad adecuado para el Aprendizaje Basado en Problemas

Fecha de recepción y aceptación: 17 de febrero de 2021 y 30 de abril de 2021

DOI: 10.46583/nereis_2021.13.782

J. L. González-Santander1*

1 Department of Mathematics. University of Oviedo.
* Correspondecia: University of Oviedo. Department of Mathematics. Calle Federico García Lorca, 18. 33007 Oviedo. Asturias. Spain. E-mail: gonzalezmarjuan@uniovi.es. ORCID ID: 0000-0001-5348-4967

abstract

We propose a simple probability problem for undergraduate level. This problem involves different branches of Mathematics, such as graph theory, linear algebra and hypergeometric sums hence it is quite suitable to be used as an example of Problem-Based Learning. In addition, the problem allows several variations so that it may be introduced to different groups of students at the same time.

KEYWORDS: Problem-Based Learning, vertex matrix, Chu-Vandermonde summation formula.

Resumen

Se propone un sencillo problema de probabilidad para nivel de grado universitario. Este problema involucra distintas ramas de las matemáticas, como la teoría de grafos, el álgebra lineal o las sumas hipergeométricas, por lo que resulta muy apto para ser usado como aprendizaje basado en problemas. Además, el problema admite diversas variantes, por lo que puede ser propuesto a diferentes grupos de estudiantes simultáneamente.

PALABRAS CLAVE: Aprendizaje basado en problemas, matriz de incidencia, fórmula de suma de Chu-Vandermonde.

INTRODUCTION

We propose a simple probability problem whose solution involves different mathematical areas. The main aim of this problem is to show to the students that although these areas are taught in separate subjects, in fact, they are quite connected to real problems. Therefore, it is quite suitable for Problem-Based Learning [1]. Next, we present the statement of the problem.

Problem If we choose a sequence of m natural numbers, a1, a2, …, am, at random, such that 1 ≤ ain, what is the probability of obtaining a1a2 ≤ ··· ≤ am?

According to Laplace’s first principle of probability [2], the problem leads straightforwardly to a combinatorial problem to count the number of “favoured events”. This combinatorial problem can be tackled by using the vertex matrix of Graph Theory. Since we have to calculate a certain power of the vertex matrix, we may resort to Linear Algebra diagonalization. However, in this case, diagonalization fails, so that we must perform heuristic reasoning wherein we calculate a hypergeometric sum. Therefore, the solution to this problem entails Probability Theory, Combinatorics, Graph Theory, Linear Algebra, and hypergeometric sums.

Therefore, the problem stated above is quite suitable for Problem-Based Learning at undergraduate level, wherein the solution unfolds in different stages and students are encouraged to go over the properties and relations of different topics. Moreover, the problem admits different variations for which, the students may apply similar strategies.

From probability to linear algebra

According to Laplace’s first principle of probability, the probability p of a certain event to occur is the ratio of the “favoured events” f to the total possible events N, assuming that all events are equally likely. The latter assumption is reasonable since the sequence of natural numbers of the problem are chosen at random.

(1)

The number of total possible events N is straightforwardly calculated by using the variations with repetition formula. Indeed, for each natural number ai we have n possible natural numbers. Since we have a sequence of m numbers, then

N=VRnm=nm

(2)

The number of favoured events is more complicated to calculate because it is subject to some restrictions, i.e. a1a2 ≤ ··· ≤ am. For simplicity, we start considering n = m = 3. In this case, the 10 favoured events are listed below.

1-1-1, 1-1-2, 1-1-3, 1-2-2, 1-2-3,

1-3-3, 2-2-2, 2-2-3, 2-3-3, 3-3-3.

We can visualize these sequences as the allowed paths of length 2 in the directed graph shown in figure 1.

Fig.1. Graph for 3 vertices

The element matrix rij of the vertex matrix R is equal to the number of edges joining vertices i and j [3]. Thereby, the vertex matrix of the graph of figure 1 is

Clearly, the vertex matrix for nN is the following triangular matrix of order n.

(3)

The number of different paths going from vertex i to vertex j of length q is the matrix element sij, where S=Rnq, [4]. In our case, q = m – 1. Therefore, the number of favourable events f is given by the sum of all the matrix elements of Rnm-1,

(4)

In order to calculate the matrix Rnm-1, we may attempt to get Rn in diagonal form, thus

Rn=PDP-1Rnm-1= PDm-1P-1,

where P is a square matrix with the eigenvectors set in columns and D is a diagonal matrix with the eigenvalues set in the main diagonal [4]. However, Rn cannot be obtained in diagonal form since Rn has got one eigenvalue, λ = 1, and one eigenvector, =(1,0,…,0) . Therefore, let us make another attempt with the following definition.

Definition. Consider the following set of sequences an(0),an(1),…an(m) such that

(5)

Theorem. The m + 1 power of the Rn matrix is given by

(6)

Proof. Let us prove (6) by induction. For m = 0, equation (6) follows straightforwardly

Assume that (6) is true for m. Let us prove that is also true for m + 1 we have

as we wanted to prove. ■

Therefore, according to (4) and (6), we can sum up all the diagonals of the Rnm-1 matrix, to obtain

(7)

In summary, our problem would be solved, if we could calculate the set of sequences an(0),an(1),…an(m) satisfying (5). The latter leads us to calculate a hypergeometric sum.

A useful hypergeometric sum

Let us define first a hypergeometric series [5].

Definition. A hypergeometric series is a series ∑ck such that

(8)

so that

(9)

where (α)k=Γ(α+k)/ Γ(α) denotes the Pochhammer symbol and Γ(z) is the gamma function.

Lemma. The following summation formula holds true:

(10)

Proof. Perform variable substitution in (8) to obtain

(11)

where the upper limit of the sum can be extended to infinity because l/n!=0 for n ∉ Z-.

According to (8-9), rewrite (11) as a hypergeometric series. Indeed,

Thereby,

(12)

Now, apply Chu-Vandermonde summation formula [5],

and the following property of the Pochhammer symbol, [6] in combination with the factorial property of the gamma function, Γ(n+1)=n!, nN, [6],

thus, after some simplification, (12) becomes

as we wanted to prove. ■

Corollary. The following summation formula holds true:

(13)

Proof. Divide both sides of (10) by s! and rewrite the result in terms of binomial coefficients, shifting the sum index to start at k = 1. ■

Notice that (13) fits in the set of sequences (5) we were looking for. Indeed, take

(14)

thus

Once we have obtained (14), we calculate the number of favourable events from (7), thereby,

Applying (10), we have

(15)

Curiously, note that, according to (14), f=an(m). As a consistency test, we recover the number of favoured events for n = m = 3, i.e. f=a3(3)= =10 , as aforementioned in the Introduction.

Finally, substitute (2) and (15) in (1), to obtain the probability,

conclusions

We have proposed a simple probability problem whose solution involves Graph Theory, Linear Algebra and hypergeometric sums, hence it is quite suitable for Problem-Based Learning. This problem admits several variations. For instance, we can modify the restrictions of the favoured events, i.e. a1 < a2 < ··· < am, so that these variations may be proposed to different groups of students at the same time.

Also, it connects different branches of Mathematics in a very natural way. This is important in an undergraduate level of education since these topics are usually studied separately, but many times they appear intertwined in real problems.

Literature cited

  1. Boud D, Feletti G. The Challenge of Problem-Based Learning. London: Psychology Press; 1997.
  2. Laplace PS. Essai philosophique sur les probabilités. 5th ed. Cambridge: Cambridge University Press; 2009.
  3. Brualdi RA. Introductory to Combinatorics. 5th. ed. Pearson Educational; 2009.
  4. Anton H, Rorres C. Elementary Linear Algebra. 9th ed. John Wiley & Sons; 2005.
  5. Andrews GE, Askey R, Roy R. Special Functions. Encyclopedia of Mathematics 71. Cambridge: Cambridge University Press; 1999.
  6. Oldham K, Myland J, Spanier J. An Atlas of Functions. 2nd ed. New York: Springer; 2009.