Café Math : Dual Numbers and Markov Chains (Part 1)

# Dual Numbers and Markov Chains (Part 1)

### This article was written in collaboration with my friend Alfredo de la Fuente.

Hi, today Alfredo and I want to talk about dual numbers and how to apply them to markov chain problems. A dual number is an expression of the form, $$a + b\varepsilon,$$ where $a$ and $b$ are elements of a given ring (real, complex, matrices or anything) and where $\varepsilon^2 = 0$. The numbers $a$ and $b$ are its real part and dual part, respectively. This is analogous to complex numbers $a + i b$ where $i^2 = -1$ but contrary to the complex numbers, dual numbers do not constitute a field. The rules of computation are as follows.

Addition and substraction are made term by term, \begin{align*} (a + b \varepsilon) + (c + d \varepsilon) &= (a + c) + (b + d) \varepsilon , \\ (a + b \varepsilon) - (c + d \varepsilon) &= (a - c) + (b - d) \varepsilon . \end{align*} Multilication is done by expanding and using the fact that $\varepsilon^2 = 0$, \begin{align*} (a + b \varepsilon)(c + d \varepsilon) &= ac + (ad + bc)\varepsilon + bd \varepsilon^2 \\ &= ac + (ad + bc)\varepsilon . \end{align*} Division is done using the conjugate of the denominator, since $(c + d \varepsilon)(c - d \varepsilon) = c^2$, \begin{align*} \frac{a + b \varepsilon}{c + d \varepsilon} &= \frac{(a + b \varepsilon)(c - d \varepsilon)}{(c + d \varepsilon)(c - d \varepsilon)} \\ &= \frac{ac + (bc - ad)\varepsilon}{c^2}\\ &= \frac{a}{c} + \frac{bc - ad}{c^2}\varepsilon . \end{align*} In particular, we see that a dual number is invertible, if and only if, its real part is. Both addition and multiplication are associative and commutaive. Multiplication is distributive with respect to addition and has a unit element. In short, the structure of dual numbers over a given field $k$ is that of a unitary $k$-algebra.

Remark. When real parts are equal to one, the multiplication rule takes a particularly simple form, \begin{align*} (1 + a \varepsilon)(1 + b \varepsilon) &= 1 + (a + b)\varepsilon . \end{align*} Similarly for inversion and division, \begin{align*} \frac{1}{1 + a \varepsilon} &= 1 - a \varepsilon, \\ \\ \frac{1 + a \varepsilon}{1 + b \varepsilon} &= 1 + (a - b) \varepsilon . \end{align*}

Remark. A key observation is that, order one Taylor developpements of differentiable funtions at a given point, actually behave like dual numbers. Say $f$ and $g$ are two real valued functions that are differentiable at $x$, we have, \begin{align*} f(x + \varepsilon) &= f(x) + f'(x) \varepsilon + O(\varepsilon^2) \\ g(x + \varepsilon) &= g(x) + g'(x) \varepsilon + O(\varepsilon^2) \end{align*} and that correspondance is an isomorphism of algebra. Indeed, \begin{align*} f(x + \varepsilon)+ g(x + \varepsilon) & = \left[f(x) + g(x)\right] + \left[f'(x)+ g'(x)\right]\varepsilon + O(\varepsilon^2). \\ f(x + \varepsilon)\times g(x + \varepsilon) & = f(x)\cdot g(x) + \left[f'(x) \cdot g(x) + g'(x)\cdot f(x)\right]\varepsilon + O(\varepsilon^2). \end{align*} which mimics the rules for dual numbers.

# 1. The Iterated Random Number Generator Problem

Problem. Suppose that $(R(n))_{n \ge 1}$ is a sequence of random variable such that, $$P(R(n) = k) = \begin{cases} \displaystyle \frac{1}{n} & \text{if 0 \le k < n,} \\ \\ 0 &\text{othewise.} \end{cases}$$ We start from a positive integer $n_0 = N$ and iterate the process $n_{k+1} = R(n_k)$ until $n_k = 0$. What is the average length of this sequence if $N$ is a googol ($N = 10^{100}$).

Ok this is a Markov chain problem where the set of state $\{s_n\}_{n \ge 0}$ is indexed by the set of natural numbers. To each state $s_n$ we associate a generating series, $$G_n(t) = \sum_{k \ge 0} p_{n,k} t^k ,$$ where $p_{n,k}$ is the probabity of reaching the state $s_0$ from the state $s_n$ in $k$ transitions. Of course, $$G_n(1) = \sum_{k \ge 0} p_{n,k} = 1,$$ and, \begin{align*} G_0(t) &= 1, \\ G_1(t) &= t, \\ G_2(t) &= \tfrac{1}{2} t +\tfrac{1}{2} t^2, \text{etc...} \end{align*} We can deduce the expected number of transitions $E_n$ to reach the state $s_0$ from the state $s_n$ by taking the derivative of $G_n(t)$ and evaluating it at $t = 1$, $$E_n = G'_n(1) = \sum_{k \ge 0} k p_{n,k} .$$ The problem has the following recursive structure, $$G_n(t) = \frac{t}{n} \sum_{k = 0}^{n-1} G_k(t) .$$ If we consider the same relation at $n+1$ we get, \begin{align*} G_{n+1}(t) &= \frac{t}{n+1} \sum_{k = 0}^n G_k(t) \\ &= \frac{n}{n+1} G_n(t) + \frac{t}{n+1} G_n(t) \\ &= \frac{1}{n+1} (n+t) G_n(t) . \end{align*} From that we probably can compute the probabilities $p_{n,k}$ but it would be tiersome and error prone. A good idea is to approximate this relation by its first order Taylor expansion at $t=1$, \begin{align*} G_n(t) &= G_n(1) + (t-1) G'_n(1) + o(t-1), & \text{as $t \rightarrow 1$.} \end{align*} if we rewrite it using $t = 1 + \varepsilon$ and we neglect terms in $\varepsilon^2$, this Talor expansion becomes a dual number. \begin{align*} G_n(1+\varepsilon) &= G_n(1) + G'_n(1) \varepsilon \\ &= 1 + E_n \varepsilon . \end{align*} The recurrence relation above becomes, \begin{align*} G_{n+1}(1+\varepsilon) &= \frac{1}{n+1} (n+1+\varepsilon) G_n(1+\varepsilon) \\ &= \left( 1 + \frac{1}{n+1} \varepsilon \right) \left(1 + E_n \varepsilon \right) \\ &= 1 + \left( E_n + \frac{1}{n+1} \right) \varepsilon . \end{align*} This means that, $$E_{n+1} = E_n + \frac{1}{n+1} ,$$ and since $E_0 = 0$, we can solve this recurrence by, $$E_n = \sum_{k = 1}^n \frac{1}{n} .$$ This number is called the $n$-th harmonic number and is denoted $H_n$ in the litterature. Approximating the sum by an integral one get, $$E_n = \log(n) + \gamma + O\left(\frac{1}{n}\right) ,$$ where $\gamma = 0.5772156649...$ is the Euler-Mascheroni constant. Using that, the solution to the problem is very well approximated by, $$E_{10^{100}} = 230.835724964...$$