Program Design

A Short Story

It’s not straightforward for ordinary programmers to write codes to automate the moment and covariance derivation in the Theory page.

The recursive equations (3) in the Theory page contain integral operations. The integrals are not that concise. What makes things worse is that the integrals grow recursively. Meanwhile, \(v_{n-1}\) will get buried in the results. It seems Symbolic Computation is needed to tidy the final expression such that we can make use of equation (1) in the Theory page. However, to the best of my knowledge, none of the current programming languages (Mathematica, MATLAB) or packages (SymPy) have offered supports in their Symbolic Computation for manipulating Itô processes, let alone computing their expectations, which are essential in the moment and covariance derivation of AJD models.

Thus, I believed expertise in compiler design is required to solve the problems from the bottom. And I do have tried to learn corresponding courses over several months but finally realized this demands time and lots of practice, so I quitted.

Fortunately, I come up a different solution (may also be simpler) afterwards which will be explained in the following sections.

Insights

I observe some features that allow me to bypass the compiler design approach. One of the features is that all \(E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}|v_{n-1}]\) can be represented as a “Polynomial” of following form

\[\begin{split}&E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}|v_{n-1}]\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{n_3k(n-1)h} e^{ik[t-(n-1)h]} [t-(n-1)h]^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q\end{split}\]

where \(b_{ijlopq}\) is the item coefficient. And \(E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\) can be represented similarly.

To facilitate the representation and corresponding operations, I designed a new class called Poly which is a tailored dictionary data structure, derived from the UserDict class in the Python Standard Library collections.

Essential Integral

The essential computation in recursive equation (3) of the Theory page is that of the following integral

\[\int_{(n-1)h}^t e^{ik[s-(n-1)h]} [s-(n-1)h]^j ds.\]

For the indefinite integral, we have

\[\begin{split}\int e^{nkt} t^m dt = \begin{cases} \sum_{i=0}^m c_{nmi} \frac{1}{k^{i+1}}e^{nkt} t^{m-i} & \text{if } n\neq 0, m \neq 0,\\ \frac{1}{nk}e^{nkt}t^0 & \text{if } n\neq 0, m = 0,\\ \frac{1}{m+1}e^{0kt}t^{m+1} & \text{if } n = 0, m \neq 0,\\ e^{0kt}t^1 & \text{if } n =0 , m=0, \end{cases}\end{split}\]

where \(c_{nm0} \triangleq \frac{1}{n}\) and

(1)\[c_{nmi} \triangleq \frac{(-1)^{i}}{n^{i+1}} \prod_{j=m-i+1}^{m} j, \quad 1\le i \le m.\]

Coefficient \(c_{nmi}\) is implemented as function c_nmi() which returns a Fraction instead of a decimal (float number).

For the definite integral,

\[\int_{(n-1)h}^t e^{ik[s-(n-1)h]}[s-(n-1)h]^jds = F(t-(n-1)h) - F(0)\]

where \(F(t) = \int e^{nkt} t^m dt\). The definite integral is implemented as function int_et().

Polynomial Representation

The result of the integral, returned by int_et(), is represented as a “polynomial” of the following form

\[\int_{(n-1)h}^t e^{ik[s-(n-1)h]} [s-(n-1)h]^j ds = \sum_{i,j^{'},l}c_{ij^{'}l}e^{ik[t-(n-1)h]}[t-(n-1)h]^{j^{'}}k^{-l}\]

which is encoded in a Poly with keyfor = ('e^{k[t-(n-1)h]}','[t-(n-1)h]','k^{-}') which is a derived UserDict with key = \((i,j^{'},l)\) and value = \(c_{ij^{'}l}\).

Code Design

Itô process moment

With \(E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\) represented as a “polynomial” of the following form

\[\begin{split}&E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{n_3k(n-1)h} e^{ik[t-(n-1)h]} [t-(n-1)h]^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q,\end{split}\]

consequently, we have

\[\begin{split}&e^{-kt}E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{(n_3-1)k(n-1)h} e^{(i-1)k[t-(n-1)h]}[t-(n-1)h]^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q,\\ &e^{kt}E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{(n_3+1)k(n-1)h} e^{(i+1)k[t-(n-1)h]}[t-(n-1)h]^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q,\\ &e^{2kt}E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{(n_3+2)k(n-1)h} e^{(i+2)k[t-(n-1)h]}[t-(n-1)h]^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q.\end{split}\]

Therefore, it’s profitable to consider the following generic integral

(2)\[\begin{split}&\int_{(n-1)h}^t e^{mks}E[I\!E_{n-1,s}^{n_3}I_{n-1,s}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]ds\\ &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{(n_3+m)k(n-1)h} \cdot int\_et(i+m,j)\cdot v_{n-1}^l k^{-o}\theta^p\sigma_v^q\\ &= \sum_{n_3+m,i+m,j^{'},l,o^{'},p,q} b_{(n_3+m)(i+m)j^{'}l o^{'}pq} e^{(n_3+m)k(n-1)h} e^{(i+m)k[t-(n-1)h]} [t-(n-1)h]^{j^{'}}\\ &\qquad \cdot v_{n-1}^{l} k^{-o^{'}}\theta^{p}\sigma_v^{q}\end{split}\]

where

\[int\_et(i+m,j) =\sum_{i+m,j^{'},l^{'}} c_{(i+m)j^{'}l^{'}}e^{(i+m)k[t-(n-1)h]}[t-(n-1)h]^{j^{'}} k^{-l^{'}}.\]

Implementation:

1. Function int_e_poly() in module ito_mom is defined to accomplish the computation in equation (2).

2. Function recursive_IEII() in module ito_mom is defined to realize the recursive step in equation (3) of the Theory page.

3. Function moment_IEII() in module ito_mom is implemented to calculate \(E[I\!E_n^{n_3}I_n^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\).

To demonstration, I re-write the following initial three moments in Itô process Moments - I in the Theory page according to the “polynomial” representation

\[\begin{split}E[I\!E_{n-1,t}^2|v_{n-1}] &=& \frac{1}{2}&e^{2k(n-1)h} e^{2k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0\\ && + &e^{2k(n-1)h}e^{k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^1 k^{-1}\theta^0\sigma_v^0\\ && - &e^{2k(n-1)h}e^{k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0\\ && - &e^{2k(n-1)h}e^{0k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^1 k^{-1}\theta^0\sigma_v^0\\ && + \frac{1}{2} &e^{2k(n-1)h}e^{0k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0,\\ % E[I\!E_{n-1,t}I_{n-1,t}|v_{n-1}] &=& &e^{k(n-1)h} e^{k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0\\ && +&e^{k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^1v_{n-1}^1 k^{-0}\theta^0\sigma_v^0\\ && -&e^{k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^1v_{n-1}^0 k^{-0}\theta^1\sigma_v^0\\ && -&e^{k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0,\\ % E[I_{n-1,t}^2|v_{n-1}] &=&-&e^{0k(n-1)h} e^{-k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^1 k^{-1}\theta^0\sigma_v^0\\ && +&e^{0k(n-1)h} e^{-k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0\\ && +&e^{0k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^1v_{n-1}^0 k^{-0}\theta^1\sigma_v^0\\ && +&e^{0k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^1 k^{-1}\theta^0\sigma_v^0\\ && -&e^{0k(n-1)h} e^{0k[t-(n-1)h]}[t-(n-1)h]^0v_{n-1}^0 k^{-1}\theta^1\sigma_v^0.\end{split}\]

Moments

Central Moments

(3)\[\begin{split} E[\overline{y}_{n}^l] &= \sum_{\boldsymbol{n}} c(\boldsymbol{n})b(\boldsymbol{n})E\left[v_{n-1}^{n_2}(e^{-knh}I\!E_{n})^{n_3}I_{n}^{n_4}I_{n}^{*n_5}\right]\\ &=\sum_{\boldsymbol{n}} c(\boldsymbol{n})b(\boldsymbol{n})E\left[v_{n-1}^{n_2}e^{-n_3knh}E[I\!E_{n}^{n_3}I_{n}^{n_4}I_{n}^{*n_5}|v_{n-1}]\right]\end{split}\]

where \(\boldsymbol{n} = (n_1,n_2,n_3,n_4,n_5)\) and \(\sum_{i=1}^5n_i=l\),

(4)\[ c(\boldsymbol{n}) = C_{l}^{n_1}C_{l-n_1}^{n_2}C_{l-n_1-n_2}^{n_3}C_{l-n_1-n_2-n_3}^{n_4}\]

(5)\[ b(\boldsymbol{n}) = \theta^{n_1}\cdot(-1)^{n_2}\cdot\left(\frac{1-e^{-kh}}{2k}\right)^{n_1+n_2}\cdot \left(\frac{\sigma_v}{2k}\right)^{n_3} \cdot \left(\rho - \frac{\sigma_v}{2k} \right)^{n_4} \cdot \left(\sqrt{1-\rho^2}\right)^{n_5}\]

Equation (5) is further represented as a Poly with

• attribute keyfor = ('e^{-kh}', 'k^{-}', 'theta', 'sigma_v', 'rho', 'sqrt(1-rho^2)'),

• key = \((i,n_1+n_2+n_3+j,n_1,n_3+j,n_4-j,n_5)\) and

• value = \(C_{n_1+n_2}^i C_{n_4}^j (-1)^{n_2+i+j} \frac{1}{2^{n_1+n_2+n_3+j}}\),

i.e.,

\[\begin{split}b(\boldsymbol{n}) &= \sum_{i=0}^{n_1+n_2} \sum_{j=0}^{n_4} C_{n_1+n_2}^i C_{n_4}^j (-1)^{n_2+i+j} \frac{1}{2^{n_1+n_2+n_3+j}} \\ &\quad e^{-ikh} k^{-(n_1+n_2+n_3+j)}\theta^{n_1}\sigma_v^{n_3+j}\rho^{n_4-j} \left(\sqrt{1-\rho^2}\right)^{n_5}.\end{split}\]

And we have

\[e^{-n_3knh}E[I\!E_{n}^{n_3}I_{n}^{n_4}I_{n}^{*n_5}|v_{n-1}] = \left(e^{-n_3kt}E[I\!E_{n-1,t}^{n_3}I_{n-1,t}^{n_4}I_{n-1,t}^{*n_5}|v_{n-1}]\right)_{t=nh}.\]

Implementation:

1. Define c_n() and b_n() in ajdmom.mdl_1fsv.cmom to implement equation (4) and (5), respectively.

2. Define moment_comb() for computing the moment under an exact combination of \((n_1,n_2,n_3,n_4,n_5)\).

3. Define sub_v() and cmoment_y() for computing the central moment \(E[\overline{y}_{n}^l]\).

Moments

(6)\[\begin{split} E[y_{n}^l] &= \sum_{\boldsymbol{n}} c(\boldsymbol{n})b_2(\boldsymbol{n})E\left[v_{n-1}^{n_2}(e^{-knh}I\!E_{n})^{n_3}I_{n}^{n_4}I_{n}^{*n_5}\right]\\ &=\sum_{\boldsymbol{n}} c(\boldsymbol{n})b_2(\boldsymbol{n})E\left[v_{n-1}^{n_2}e^{-n_3knh}E[I\!E_{n}^{n_3}I_{n}^{n_4}I_{n}^{*n_5}|v_{n-1}]\right]\end{split}\]

where \(\boldsymbol{n}\) and \(c(\boldsymbol{n})\) are the same as these in (3) while

(7)\[\begin{split} b_2(\boldsymbol{n}) &= \left[(\mu-\theta/2)h + \frac{1-e^{-kh}}{2k}\theta\right]^{n_1}\cdot(-1)^{n_2}\cdot\left(\frac{1-e^{-kh}}{2k}\right)^{n_2}\\ &\quad \cdot \left(\frac{\sigma_v}{2k}\right)^{n_3} \cdot \left(\rho - \frac{\sigma_v}{2k} \right)^{n_4} \cdot \left(\sqrt{1-\rho^2}\right)^{n_5}.\end{split}\]

Implementation:

1. Define b_n() in module ajdmom.mdl_1fsv.mom to implement equation (7).

2. Define moment_comb() in module ajdmom.mdl_1fsv.mom as a counterpart of moment_comb() in ajdmom.mdl_1fsv.cmom.

3. Define moment_y() for computing the moment \(E[y_n^l]\).

Covariances

(8)\[cov(y_n^{l_1},y_{n+1}^{l_2}) = E[y_n^{l_1}y_{n+1}^{l_2}] - E[y_n^{l_1}]E[y_{n+1}^{l_2}],\]

in which \(E[y_n^{l_1}]\) and \(E[y_{n+1}^{l_2}]\) can be computed through moment_y() in module ajdmom.mdl_1fsv.mom. Thus, I only need to present the computation of \(E[y_n^{l_1}y_{n+1}^{l_2}].\)

Co-Moments

(9)\[\begin{split} &E[y_n^{l_1}y_{n+1}^{l_2}]\\ &= \sum_{\boldsymbol{n}}c(\boldsymbol{n})b_2(\boldsymbol{n})E[y_n^{l_1} v_n^{n_2}e^{-n_3k(n+1)h}I\!E_{n+1}^{n_3} I_{n+1}^{n_4} I_{n+1}^{*n_5}]\\ &= \sum_{\boldsymbol{n}}c(\boldsymbol{n})b_2(\boldsymbol{n})E[y_n^{l_1}\color{teal} v_n^{n_2}e^{-n_3k(n+1)h}E[I\!E_{n+1}^{n_3} I_{n+1}^{n_4} I_{n+1}^{*n_5}|v_n]]\\ &= \sum_{\boldsymbol{n}}c(\boldsymbol{n})b_2(\boldsymbol{n})E[y_n^{l_1}\color{teal} \text{ve_IEII_vn}(n_2, n_3, n_4, n_5)]\\ &= \sum_{\boldsymbol{n}}c(\boldsymbol{n})b_2(\boldsymbol{n})\color{magenta}\sum_{\boldsymbol{m}}c(\boldsymbol{m})b_2(\boldsymbol{m})E[v_{n-1}^{m_2}e^{-m_3knh}I\!E_n^{m_3}I_n^{m_4}I_n^{*m_5} \color{teal}\text{ve_IEII_vn}(n_2, n_3, n_4, n_5)]\end{split}\]

where I used

\[\begin{split}y_n^{l_1} &= \sum_{\boldsymbol{m}}c(\boldsymbol{m})b_2(\boldsymbol{m})v_{n-1}^{m_2}e^{-m_3knh}I\!E_n^{m_3}I_n^{m_4}I_n^{*m_5},\\ y_{n+1}^{l_2} &= \sum_{\boldsymbol{n}}c(\boldsymbol{n})b_2(\boldsymbol{n})v_{n}^{n_2}e^{-n_3k(n+1)h}I\!E_{n+1}^{n_3}I_{n+1}^{n_4}I_{n+1}^{*n_5}.\end{split}\]

Note that

\[\begin{split}E[I\!E_{n+1}^{n_3} I_{n+1}^{n_4} I_{n+1}^{*n_5}|v_n] &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{n_3knh} e^{ikh} h^jv_{n}^l k^{-o}\theta^p\sigma_v^q,\\ v_n^{n_2}e^{-n_3k(n+1)h}E[I\!E_{n+1}^{n_3} I_{n+1}^{n_4} I_{n+1}^{*n_5}|v_n] &= \sum_{n_3,i,j,l,o,p,q} b_{n_3ijlopq} e^{-n_3kh} e^{ikh} h^jv_{n}^{l+n_2} k^{-o}\theta^p\sigma_v^q.\end{split}\]

Function ve_IEII_vn() is defined to accomplish above computation and expand \(v_n\) which returns a poly with keyfor = (‘e^{-knh}IE_n’,‘e^{-kh}’,‘h’,‘v_{n-1}’,‘k^{-}’,‘theta’,‘sigma_v’), i.e.,

\[\text{ve_IEII_vn}(n_2, n_3, n_4, n_5) =\sum_{m,i,j,l,o,p,q}b_{mijlopq}e^{-mknh}I\!E_n^m e^{-ikh} h^jv_{n-1}^l k^{-o}\theta^p\sigma_v^q.\]

The expansion of \(v_n\) is done through,

(10)\[\begin{split}v_n &= e^{-kh}v_{n-1} + (1 - e^{-kh})\theta + \sigma_v e^{-knh}I\!E_{n},\\ v_n^m &= \sum_{\boldsymbol{m}} c_v(\boldsymbol{m}) b_v(\boldsymbol{m}) \cdot v_{n-1}^{m_1}(e^{-knh}I\!E_n)^{m_3},\end{split}\]

(taking \(v_n^m\) as an example), where \(\boldsymbol{m} = (m_1,m_2,m_3)\), \(m_1+m_2+m_3 = m\), and

\[c_v(\boldsymbol{m}) \triangleq C_m^{m_1}C_{m-m_1}^{m_2}, \quad b_v(\boldsymbol{m}) \triangleq e^{-m_1 kh} \cdot [(1-e^{-kh})\theta]^{m_2} \cdot \sigma_v^{m_3}.\]

Implementation:

1. Define ve_IEII_vn() in module ajdmom.mdl_1fsv.cov.

2. Define moment_inner_comb() (in module ajdmom.mdl_1fsv.cov) to compute the moment when the inner combination \(\boldsymbol{m}=(m_1,m_2,m_3,m_4,m_5)\) is fixed under an exact outer combination \(\boldsymbol{n}=(n_1,n_2,n_3,n_4,n_5)\).

3. Define moment_outer_comb() (in module ajdmom.mdl_1fsv.cov) to compute the moment when only the combination of the \(\boldsymbol{n}=(n_1,n_2,n_3,n_4,n_5)\), \(\sum_{i=1}^5n_i=l_2\) is given.

4. Define moment_yy() (in module ajdmom.mdl_1fsv.cov) for equation (9).

5. Define cov_yy() (in module ajdmom.mdl_1fsv.cov) for equation (8).