Expected maximums and fun with Faulhaber’s formula

A recent Futility Closet post inspired this one. There, Greg Ross mentioned a 2020 paper by P Sullivan titled “Is the Last Banana Game Fair?” in Mathematics Teacher. (BTW, it’s behind a paywall and I haven’t seen that paper). I’m not going to define the last banana game, but instead look at a related question.

Let’s define things more generally. Let I_n=\{1,2,...,n\}, let X,Y be two independent, uniform random variables taken from I_n, and let Z=max(X,Y). The last banana game post above concerns the case n=6. Here, I’m interested in investigating the question: What is E(Z)?

Computing this isn’t hard. By definition of independent and max, we have
P(Z\leq z)=P(X\leq z)P(Y\leq z).
Since P(X\leq z)=P(Y\leq z)={\frac{z}{n}}, we have
P(Z\leq z)={\frac{z^2}{n^2}}.
The expected value of Z is defined as \sum kP(Z=k), but there’s a handy-dandy formula we can use instead:
E(Z)=\sum_{k=0}^{n-1} P(Z>k)=\sum_{k=0}^{n-1}[1-P(Z\leq k)].
Now we use the previous computation to get
E(Z)=n-{\frac{1}{n^2}}\sum_{k=1}^{n-1}k^2=n-{\frac{1}{n^2}}{\frac{(n-1)n}{6}}={\frac{2}{3}}n+{\frac{1}{2}}-{\frac{1}{6n}}.
This solves the problem as stated. But this method generalizes in a straightforward way to selecting m independent r.v.s in I_n, so let’s keep going.

First, let’s pause for some background and history. Notice how, in the last step above, we needed to know the formula for the sum of the squares of the first n consecutive positive integers? When we generalize this to selecting m integers, we need to know the formula for the sum of the m-th powers of the first n consecutive positive integers. This leads to the following topic.

Faulhaber polynomials are, for this post (apparently the terminology is not standardized) the sequence of polynomials F_m(n) of degree m+1 in the variable n that gives the value of the sum of the m-th powers of the first n consecutive positive integers:

\sum_{k=1}^{n} k^m=F_m(n).

(It is not immediately obvious that they exist for all integers m\geq 1 but they do and Faulhaber’s results establish this existence.) These polynomials were discovered by (German) mathematician Johann Faulhaber in the early 1600s, over 400 years ago. He computed them for “small” values of m and also discovered a sort of recursive formula relating F_{2\ell +1}(n) to F_{2\ell}(n). It was about 100 years later, in the early 1700s, that (Swiss) mathematician Jacob Bernoulli, who referenced Faulhaber, gave an explicit formula for these polynomials in terms of the now-famous Bernoulli numbers. Incidentally, Bernoulli numbers were discovered independently around the same time by (Japanese) mathematician Seki Takakazu. Concerning the Faulhaber polys, we have
F_1(n)={\frac{n(n+1)}{2}},
F_2(n)={\frac{n(n+1)(2n+1)}{6}},
and in general,
F_m(n)={\frac{n^{m+1}}{m+1}}+{\frac{n^m}{2}}+ lower order terms.

With this background aside, we return to the main topic of this post. Let I_n=\{1,2,...,n\}, let X_1,X_2,...,x_m be m independent, uniform random variables taken from I_n, and let Z=max(X_1,X_2,...,X_m). Again we ask: What is E(Z)? The above computation in the m=2 case generalizes to:

E(Z)=n-{\frac{1}{n^m}}\sum_{k=1}^{n-1}k^m=n-{\frac{1}{n^m}}F_m(n-1).

For m fixed and n “sufficiently large”, we have

E(Z)={\frac{m}{m+1}}n+O(1).

I find this to be an intuitively satisfying result. The max of a bunch of independently chosen integers taken from I_n should get closer and closer to n as (the fixed) m gets larger and larger.

Harmonic morphisms to P_4 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_4.
path4-0123

We only consider the cyclic graph on k vertices, C_k as the domain in this post. There are no non-trivial harmonic morphisms C_5 \to P_4, so we start with C_6. We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_4 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_4 (we let 3 be the numerical notation for the color red), the blue vertices in \Gamma_1 to the blue vertex of \Gamma_2=P_4 (we let 2 be the numerical notation for the color blue), the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_4 (we let 1 be the numerical notation for the color green), and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_4 (we let 0 be the numerical notation for the color white).

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms C_6 \to P_4, plus that induced by f = (1, 2, 3, 2, 1, 0) and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of P_4 induced by the transposition (0,3)(1,2) (so total = 10).cyclic6-123210

Example 2: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0) and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (2, 1, 0, 1, 2, 3, 3) and all 7 of its cyclic permutations (total = 7+11 = 18).
cyclic7-1232100
cyclic7-1233210

Example 3: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0) and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0) and all of its cyclic permutations (12+8=20). In addition, there is f = (1, 2, 3, 3, 2, 1, 0, 0) and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of (1, 2, 3, 3, 2, 1, 0, 0) is closed under the transposition (0,3)(1,2) (total = 28).
cyclic8-12321000
cyclic8-12333210
cyclic8-12332100

Example 4: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0, 0) and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 2, 1, 0, 0, 0) and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0, 0) and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 3, 2, 1, 0) and all 9 of its cyclic permutations (total = 9+31 = 40). cyclic9-123210000cyclic9-123321000cyclic9-123332100cyclic9-123333210

Harmonic morphisms to P_3 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_3.

The path graph P_3

If \Gamma_1 = (V_1, E_1) and \Gamma_2 = (V_2, E_2) are graphs then a map \phi:\Gamma_1\to \Gamma_2 (that is, \phi: V_1\cup E_1\to V_2\cup E_2) is a morphism provided

  1. if \phi sends an edge to an edge then the edges vertices must also map to each other: e=(v,w)\in E_1 and \phi(e)\in E_2 then \phi(e) is an edge in \Gamma_2 having vertices \phi(v)\in V_2 and \phi(w)\in V_2, where \phi(v)\not= \phi(w), and
  2. if \phi sends an edge to a vertex then the edges vertices must also map to that vertex: if e=(v,w)\in E_1 and \phi(e)\in V_2 then \phi(e) = \phi(v) = \phi(w).

As a non-example, if \Gamma_1 is a planar graph, if \Gamma_2 is its dual graph, and if \phi:\Gamma_1\to\Gamma_2 is the dual map V_1\to E_2 and E_1\to V_2, then \phi is not a morphism.

Given a map \phi_E : E_1 \rightarrow E_2 \cup V_2, an edge e_1 is called horizontal if \phi_E(e_1) \in E_2 and is called vertical if \phi_E(e_1) \in V_2. We say that a graph morphism \phi: \Gamma_1 \rightarrow \Gamma_2 is a graph homomorphism if \phi_E (E_1) \subset E_2. Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that \Gamma_2 has at least one edge. Let Star_{\Gamma_1}(v) denote the star subgraph centered at the vertex v. A graph morphism \phi : \Gamma_1 \to \Gamma_2 is called harmonic if for all vertices v \in V(\Gamma_1), the quantity
\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|
(the number of edges in \Gamma_1 adjacent to v and mapping to the edge f in \Gamma_2) is independent of the choice of edge f in Star_{\Gamma_2}(\phi(v)).

An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_3 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_3, the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_3, and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_3.

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression a^b + c^d + e^f + g^h + i^j to make 2018.

2. (a) Express 2018 = p^q + r^s where p, q, r, s are primes.
(b) Express 2018 = p^q - r^s where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express 2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n) using the fewest number of distinct digits.

Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression a^b + c^d + (e + f + g - h)^i
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. 1 / n_1 + 1 / n_2 + ... + 1 / n_k for integers 0 < n_1 < n_2 < ...  n_k < 202049
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.

Differential equations and SageMath

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

The files are licensed under the Attribution-ShareAlike Creative Commons license.

  1. Partial fractions handout, pdf
  2. Introduction to matrix determinants handout, pdf
  3. Impulse-response handout, pdf
  4. Introduction to ODEs, pdf
  5. Initial value problems, pdf
  6. Existence and uniqueness, pdf
  7. Euler’s method for numerically approximating solutions to DEs, pdf.
    Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
  8. Direction fields and isoclines, pdf
  9. 1st order ODEs, separable and linear cases, pdf
  10. A falling body problem in Newtonian mechanics, pdf
  11. A mixing problem, pdf
  12. Linear ODEs, I, pdf
  13. Linear ODEs, II, pdf
  14. Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
  15. Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
  16. Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
    I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
  17. Springs, I, pdf
  18. Springs, II, pdf
  19. Springs, III, pdf
  20. LRC circuits, pdf
  21. Power series methods, I, pdf
  22. Power series methods, II, pdf
  23. Introduction to Laplace transform methods, I, pdf
  24. Introduction to Laplace transform methods, II, pdf
  25. Lanchester’s equations modeling the battle between two armies, pdf
  26. Row reduction/Gauss elimination method for systems of linear equations, pdf.
  27. Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
  28. Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
  29. Electrical networks using Laplace transforms, pdf
  30. Separation of variables and the Transport PDE, pdf
  31. Fourier series, pdf.
  32. one-dimensional heat equation using Fourier series, pdf.
  33. one-dimensional wave equation using Fourier series, pdf.
  34. one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
  35. All these lectures collected as one pdf (216 pages).
    While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester