Skip to main content

Poisson Games and Sudden-Death Overtime

Another Nice Application of Difference Equations

Here's a nice problem I encountered in a course on applied stochastic processes.


Show that the set of all pairs of positive integers can be placed into one-one correspondence with the positive integers by giving an explicit one-one mapping between the two sets.


This can be done expediently using the theory of partial difference equations. A standard diagonalization can be characterized by the following relations:
  1. \( f(1,1)=1 \)
  2. \( f(x,y) = f(x-1,y)+x+y \)
  3. \( f(x,y) = f(x,y-1)+x+y-1 \)
These can be written in difference notation as:
  1. \( f(1,1)=1 \)
  2. \( \frac{\Delta f}{\Delta x} = x+y \)
  3. \( \frac{\Delta f}{\Delta y} = x+y-1 \)
Equation 2 gives \( \frac{{\Delta}^2 f}{{\Delta x}{\Delta y}} = 1 \) and equation 3 gives \( \frac{{\Delta}^2 f}{{\Delta y}{\Delta x}} = 1, \) so this is an exact partial difference equation. Summing using equation 2, \[ f(x,y) = x(x+1)/2 + xy + g(y). \] Differencing and setting this equal to equation 3, \[ x+\frac{\Delta g}{\Delta y} = x+y-1 \] and so \( g(y) = y(y+1)/2 - y + C \) . Finally \( f(1,1)=1 \) implies that \( C=-1 \) , and so \[ f(x,y) = x(x+1)/2 + xy + y(y+1)/2 - y - 1. \]


Popular posts from this blog

A Bayes' Solution to Monty Hall

For any problem involving conditional probabilities one of your greatest allies is Bayes' Theorem. Bayes' Theorem says that for two events A and B, the probability of A given B is related to the probability of B given A in a specific way.

Standard notation:

probability of A given B is written \( \Pr(A \mid B) \)
probability of B is written \( \Pr(B) \)

Bayes' Theorem:

Using the notation above, Bayes' Theorem can be written: \[ \Pr(A \mid B) = \frac{\Pr(B \mid A)\times \Pr(A)}{\Pr(B)} \]Let's apply Bayes' Theorem to the Monty Hall problem. If you recall, we're told that behind three doors there are two goats and one car, all randomly placed. We initially choose a door, and then Monty, who knows what's behind the doors, always shows us a goat behind one of the remaining doors. He can always do this as there are two goats; if we chose the car initially, Monty picks one of the two doors with a goat behind it at random.

Assume we pick Door 1 and then Monty sho…

What's the Value of a Win?

In a previous entry I demonstrated one simple way to estimate an exponent for the Pythagorean win expectation. Another nice consequence of a Pythagorean win expectation formula is that it also makes it simple to estimate the run value of a win in baseball, the point value of a win in basketball, the goal value of a win in hockey etc.

Let our Pythagorean win expectation formula be \[ w=\frac{P^e}{P^e+1},\] where \(w\) is the win fraction expectation, \(P\) is runs/allowed (or similar) and \(e\) is the Pythagorean exponent. How do we get an estimate for the run value of a win? The expected number of games won in a season with \(g\) games is \[W = g\cdot w = g\cdot \frac{P^e}{P^e+1},\] so for one estimate we only need to compute the value of the partial derivative \(\frac{\partial W}{\partial P}\) at \(P=1\). Note that \[ W = g\left( 1-\frac{1}{P^e+1}\right), \] and so \[ \frac{\partial W}{\partial P} = g\frac{eP^{e-1}}{(P^e+1)^2}\] and it follows \[ \frac{\partial W}{\partial P}(P=1) = …

Solving a Math Puzzle using Physics

The following math problem, which appeared on a Scottish maths paper, has been making the internet rounds.

The first two parts require students to interpret the meaning of the components of the formula \(T(x) = 5 \sqrt{36+x^2} + 4(20-x) \), and the final "challenge" component involves finding the minimum of \( T(x) \) over \( 0 \leq x \leq 20 \). Usually this would require a differentiation, but if you know Snell's law you can write down the solution almost immediately. People normally think of Snell's law in the context of light and optics, but it's really a statement about least time across media permitting different velocities.

One way to phrase Snell's law is that least travel time is achieved when \[ \frac{\sin{\theta_1}}{\sin{\theta_2}} = \frac{v_1}{v_2},\] where \( \theta_1, \theta_2\) are the angles to the normal and \(v_1, v_2\) are the travel velocities in the two media.

In our puzzle the crocodile has an implied travel velocity of 1/5 in the water …