In this post we will discuss Difference Equations.
One could say difference equations are the discrete analogue of differential equations.
Indeed the techniques used to solve them very much resembles the approach one takes for solving ordinary differential equations (ODEs).
An example of a difference equation is the Fibonacci sequence which we will learn how to solve later.
Difference equations are often not as extensively treated in undergraduate education as their continuous counterpart.
They are nevertheless important in all sorts of disciplines.
In probability theory difference equations (or “recurrence relations”) often arise when describing probabilistic transitions between a number of discrete states. In science and economy one is often interested in discretizing a differential equation into a difference equation so one can solve it numerically in a computer. There is a whole research area devoted just to approximating solutions to differential equations in this way so I am not going to delve much deeper into this.
Instead we will look at how to solve certain types of difference equations exactly and apply the theory to some nice puzzles, like Tower of Hanoi or finding out the probability of a mouse surviving in a filthy student corridor with a cat (a metaphor for finding the absorption probability of a discrete Markov Chain).
Let’s start off with some theory for the simplest kind of difference equations:
Let’s move on to an application:
According to the legend the world will end once monks, fulfilling an ancient prophecy, have finished solving the puzzle for .
According to our analysis the minimum number of moves required is .
Even if they carry out one move per second it will take them approximately years to complete, so I think we are safe for a while longer.
In order to look at remaining applications we need to go over some theory of second order difference equations:
A nice direct application of this is that we may compute a closed form expression for the Fibonacci number.
Let’s now turn our attention to a probabilistic application:
Those of you who have studied elementary probability might have recognized already that the problem above was simply a restatement of the Gamblers Ruin Paradox. Instead of a mouse and a cat we have two opponents each holding and dollars respectively. The opponents play a fair game (say they flip a fair coin) and if one opponent loses, he has to give away one dollar to the other opponent. They play the game until one of them holds all dollars. The question is what the probability is of the first opponent losing all his money (i.e the mouse getting eaten by the cat).
The seeming “paradox” here being despite playing a fair game the first player will still lose all his money if he plays a very rich opponent, say a casino. Indeed if we assume for arguments sake that the casino has infinite amount of money, then the probability that the first player loses all his money is i.e the game will (almost surely) not continue forever, despite even chance of winning or losing, no matter what finite amount of chips the first player starts with.
Below are some neat exercises for you to try.
They can all be solved by identifying a difference equation and solving it.