Café Math : Dual Numbers and Markov Chains (Part 1)
1, 1, 2, 2, 1, 8, 6, 7, 14, 27, 26, 80, 133, 170, 348, 765, 1002, 2176, 4682, ...   (A121350)
Math Blog
Articles
Talks
Teaching
Phd Thesis
Financial Maths
About me
PrevNext

Dual Numbers and Markov Chains (Part 1)

Thu, 09 Sep 2013 19:50:16 GMT


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

Be the first to post a comment !

Comment:

Name:

Email:

Website: