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

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.

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... $$