text:
In This appendix we discuss Markovian dynamics of classical systems. We begin in \ref{app:markoviandynamics} by discussing classical finite-dimensional states, the differential equations that govern the generation of events, and their associated delay functions. We demonstrate the properties of the dynamical generators that we will require later in the proof. In \ref{app:eventsequences} we discuss sequences of events generated by Markovian dynamics, and some of their properties, continuing in \ref{app:indisequences} to differentiate between general sequences of events and \emph{independent} sequences, those in which each event is independent of the dynamics of the prior event. Finally in \ref{app:resetresult}, we prove that the accuracy of general sequences is upper bound by that of independent sequences, a result that will translate directly to the case of clocks, in which case reset clocks will upper bound the accuracy of general clocks.

\subsection{Events generated by classical (stochastic) dynamics}\label{app:markoviandynamics}

\subsubsection{Classical states are population vectors}

Here we define the state space for classical Markovian dynamics, of which clocks are a special case. In the main text (Section \ref{sec:classicalspecialcase}), we argued that classical clocks, which are a special case of quantum clocks restricted to a fixed orthonormal basis, may be described by stochastic dynamics on the vector of diagonal elements of the quantum state w.r.t. the restricted basis. In light of this description, we define classical states accordingly.

\begin{definition}\label{def:canonicalbasis}

The \textbf{canonical} basis is a preferred orthonormal basis $\{\mathbf{e}_i\}_{i=0}^d$ for a real vector space of finite dimension $d$. Each $\mathbf{e}_i$ is referred to as a \textbf{canonical state}.

\end{definition}

\begin{definition}\label{def:popvector}

A \textbf{classical state}, or \textbf{population vector}, is a vector $v \in \mathbb{R}^d$ all of whose elements w.r.t. the canonical basis (Def. \ref{def:canonicalbasis}) are greater or equal to zero, and whose sum of the elements in the canonical basis is less or equal to one. Thus $v = \sum_{i=1}^d v_i \mathbf{e}_i$ is a population vector if and only if
\begin{align}
	v_i &\geq 0 \quad \forall i, \\
	\text{and} \quad \sum_i v_i &\leq 1.
\end{align}

\end{definition}

\begin{remark}

In this appendix, we only deal with classical states, and so will omit the prefix classical for simplicity.

\end{remark}

\begin{definition}\label{def:norm}

For this appendix, we define the \textbf{e-sum} (that stands for ``element-sum") of a real vector $v \in \mathbb{R}^d$ as the sum of its elements w.r.t. the canonical basis (Def. \ref{def:canonicalbasis}). Thus if $v = \sum_{i=1}^d v_i \mathbf{e}_i$, then
\begin{align}
	\onenorm{v} &= \sum_{i=1}^d v_i.
\end{align}

\end{definition}

\begin{remark}

Note that for population vectors, the e-sum coincides with the 1-norm, as all of the elements in said basis are non-negative. We use the simple sum because we will deal with negative vectors as well, and the e-sum has the advantage of commuting with other finite sums and finite integrals.

\end{remark}

\subsubsection{Generators of stochastic (Markovian) dynamics}

From standard probability theory, the differential equation for Markovian dynamics is given by
\begin{align}
	\frac{d}{dt} V(t) &= \hat{M} V(t),
\end{align}
where $V(t)$ is the state at time $t$ and $\hat{M}$ is a time-independent linear operator, referred to as the Kolmogorov generator of forward dynamics. If the dynamics are also responsible for the generation of events, then the generator $\hat{M}$ is split into
\begin{align}
	\hat{M} &= \notickmatrix + \tickmatrix,
\end{align}
where $\tickmatrix$ is associated with the generation of events, and the probability density (probability per unit time) that the event occurs at a time $t$ is given by
\begin{align}\label{eq:probdensityevent}
	P(t) &= \onenorm{\tickmatrix V(t)}.
\end{align}

We proceed to discuss the precise properties of these generators that we require in the proof.

\begin{definition}\label{def:stochasticgenerators}

By a \textbf{pair of stochastic generators}, we mean a pair of linear operators $\{ \notickmatrix, \tickmatrix \}$on a finite dimensional real-valued vector space $\mathbb{R}^d$, that we refer to as the \textbf{non-event generator and event generator} respectively, such that the following conditions are satisfied:
\begin{itemize}
	\item $\notickmatrix$ is an endomorphism, i.e. it takes vectors from $\mathbb{R}^d$ to $\mathbb{R}^d$, and when expressed as a matrix w.r.t. the canonical basis,
	\begin{align}\label{eq:nontickcondition}
		\notickmatrix_{ij} & \begin{cases}
				\leq 0 & \text{for $i=j$}, \\
				\geq 0 & \text{for $i\neq j$}.
			\end{cases}
	\end{align}
	\item $\tickmatrix$ takes vectors from $\mathbb{R}^d$ to a real vector space of possibly different dimension $\mathbb{R}^{d^\prime}$. Expressed as a matrix w.r.t. the canonical bases of both (input and output) spaces, $\tickmatrix$ has $d^\prime$ rows and $d$ columns, and must be element-wise non-negative, i.e.
	\begin{align}\label{eq:tickcondition}
		\tickmatrix_{ij} &\geq 0 \quad \forall i,j.
	\end{align}
	\item The pair of generators must satisfy
	\begin{align}\label{eq:stochasticcondition}
		\sum_{i=1}^{d^\prime} \tickmatrix_{ij} + \sum_{i=1}^d \notickmatrix_{ij} &\leq 0 \quad \forall j.
	\end{align}
\end{itemize}

\end{definition}

\begin{remark}

The non-negative nature of $\tickmatrix$ follows from the requirement that the probability density of the event (Eq. \ref{eq:probdensityevent}) must be non-negative, and the state following the event must also be a population vector. The off-diagonal elements of both $\notickmatrix$ and $\tickmatrix$ represent transition probabilities between different canonical states, and are therefore also non-negative. Finally, the condition on the column sums (Eq. \ref{eq:stochasticcondition}) is necessary for the e-sum norm of the state to be non-increasing, from which the condition on the diagonal elements of $\notickmatrix$ follows.

\end{remark}

\begin{remark}

We use the more general norm non-increasing rather than norm-preserving generators in the appendix because 1) the results apply to the more general case anyway, and 2) we will require results on norm non-increasing dynamics later in the proof.

\end{remark}

\begin{corollary}\label{cor:zerotickmatrix}

If $\{\notickmatrix,\tickmatrix\}$ are a pair of stochastic generators, then so is $\{\notickmatrix,\hat{\mathbf{0}}\}$, where $\hat{\mathbf{0}}$ is the zero operator with the same input and output spaces as $\tickmatrix$.

\end{corollary}

\begin{proof}

The zero operator clearly satisfies Eq. \ref{eq:tickcondition}. Furthermore, we verify that Eq. \ref{eq:stochasticcondition} is satisfied for the new pair,
\begin{align}
	\sum_{i=1}^d \notickmatrix_{ij} &\leq - \left( \sum_{i=1}^{d^\prime} \tickmatrix_{ij} \right) < 0 \quad \forall j,
\end{align}
as all of the elements of $\tickmatrix$ are non-negative.

\end{proof}

\begin{remark}

Given an linear endomorphism $\notickmatrix$, we consider it to be a non-event generator if it forms a pair of stochastic generators with the zero operator, which is equivalent to requiring it to for a pair of stochastic generators with at least one element wise generator $\tickmatrix$. On the other hand, every linear operator $\tickmatrix$ that is element-wise non-negative w.r.t. the canonical bases for the input and output space is an event generator, as one can always find a non-event generator with diagonal elements that are negative enough so that the two taken together form a pair of stochastic generators.

\end{remark}

\begin{corollary}\label{cor:zerogenerators}

If $\{\notickmatrix,\tickmatrix\}$ are a pair of stochastic generators (Def. \ref{def:stochasticgenerators}) and $\tickmatrix$ is an endomorphism, i.e. it takes vectors from $\mathbb{R}^d$ to $\mathbb{R}^d$, then the pair $\{\notickmatrix + \tickmatrix, \hat{\mathbf{0}} \}$ is also a pair of stochastic generators. Equivalently, $\notickmatrix + \tickmatrix$ is a non-event generator.

\end{corollary}

\begin{proof}

Eq. \ref{eq:stochasticcondition} is trivially satisfied, while the zero operator by definition satisfies Eq. \ref{eq:tickcondition}. The off-diagonal elements of $\notickmatrix$ and $\tickmatrix$ are individually non-negative, and thus the same holds for the sum, satisfying the second condition in Eq. \ref{eq:nontickcondition}.

Finally, to verify the condition on the diagonal elements (first line of Eq. \ref{eq:nontickcondition}),
\begin{align}
	\notickmatrix_{jj} + \tickmatrix_{jj} &= \sum_{i=1}^d \left( \notickmatrix_{ij} + \tickmatrix_{ij} \right) - \sum_{i\neq j}^d \left( \notickmatrix_{ij} + \tickmatrix_{ij} \right) < 0 \quad \forall j,
\end{align}
as the first sum on the right is non-positive by Eq. \ref{eq:stochasticcondition}, and the second (subtracted) sum comprises solely non-negative numbers, by Eqs. \ref{eq:nontickcondition} and \ref{eq:tickcondition}.

\end{proof}

\begin{corollary}\label{cor:rowgenerators}

If $\{\notickmatrix,\tickmatrix\}$ are a pair of stochastic generators, then so are all of the pairs $\{\notickmatrix,\tickmatrix_j\}$, where $\tickmatrix_j$ is constructed by setting all of the rows in $\tickmatrix$ to zero, save the $j^{th}$ one.

\end{corollary}

\begin{proof}

Eq. \ref{eq:nontickcondition} is satisfied trivially as the non-event generator $\notickmatrix$ is left unchanged. Setting rows to zero in $\tickmatrix$ also maintains Eq. \ref{eq:tickcondition}. Finally, for Eq. \ref{eq:stochasticcondition}, for the $j^{th}$ column, the modified LHS of the expression is missing some non-zero elements from the original event generator $\tickmatrix$, and is therefore less or equal than the original expression, still satisfying the inequality.

\end{proof}

\begin{corollary}\label{cor:scaledgenerators}

If $\{\notickmatrix,\tickmatrix\}$ are a pair of stochastic generators, then so is $\{a\notickmatrix,a\tickmatrix\}$, where $a>0$.

\end{corollary}

\begin{proof}

By direct substitution into Def. \ref{def:stochasticgenerators}, one verifies that all of the inequalities are maintained as the scaling factor $a$ is positive.

\end{proof}

\begin{lemma}[From infinitesimal generators to finite-time transition matrices]\label{lemma:stochasticgenerators}

Given any stochastic non-event generator $\notickmatrix$, and a population vector $V$,
\begin{itemize}
	\item $e^{\notickmatrix t}$ is a transition matrix \cite{probability} for all $t\geq 0$, i.e. If $\mathcal{M} = e^{\notickmatrix t}$, then
	\begin{subequations}
		\begin{align}
			\mathcal{M}_{ij} &\geq 0 \quad \forall i,j, \\
			\sum_i \mathcal{M}_{ij} &\leq 1 \quad \forall j.
		\end{align}
	\end{subequations}
	\item $e^{\notickmatrix t} V$ is a population vector (Def. \ref{def:popvector}) for all $t\geq 0$, and its norm (e-sum) is non-increasing in time.
\end{itemize}

\end{lemma}

\begin{proof}

One of the definitions of the exponential function is via
\begin{align}
	e^{\notickmatrix t} &= \lim_{m\rightarrow\infty} \left( \mathds{1} + \frac{\notickmatrix t}{m} \right)^m
\end{align}

The matrix within the parentheses has non-negative off-diagonal entries since $\notickmatrix_{ij} > 0$ for $i\neq j$. Furthermore, for the diagonal entries, one can always pick $m$ large enough so that $\mathds{1} + t \notickmatrix_{ii}/m > 0$, and thus for large enough $m$, the above expression is a positive power of a matrix with non-negative entries, which must thus be non-negative element-wise. Thus $e^{\notickmatrix t}$ is element wise non-negative.

To prove that the column sums of $\mathcal{M}$ are less or equal to $1$, we first prove the properties of $e^{\notickmatrix t} V$. As $V$ is a population vector, all of its elements are non-negative, and thus the elements of $e^{\notickmatrix t} V$ are also non-negative. Labelling this vector as $V(t) = \sum_i V_i(t) \mathbf{e}_i$ where each $V_i(t) \geq 0$, we may calculate the rate of change of its e-sum (Def. \ref{def:norm}),
\begin{align}
	\frac{d}{dt} \onenorm{V(t)} &= \onenorm{ \frac{d}{dt} e^{\notickmatrix t} V } \\
	&= \onenorm{ \notickmatrix V(t) } \\
	&= \sum_{ij} \notickmatrix_{ij} V_j(t) \\
	&= \sum_j \left( \sum_i \notickmatrix_{ij} \right) V_j \leq 0
\end{align}
as each of the column sums of $\notickmatrix$ is non-positive (Eq. \ref{eq:nontickcondition}). Thus $V(t)$ is also a population vector for all $t \geq 0$, with non-increasing norm. Finally take $V = \mathbf{e}_j$. As the norm of $V(t)$ is less or equal to $1$ for all $t \geq 0$, one has for the transition matrix $\mathcal{M} = e^{\notickmatrix t}$ that
\begin{align}
	\onenorm{V(t)} &= \onenorm{\mathcal{M} \mathbf{e}_j} \\
	&= \sum_i \mathcal{M}_{ij} \leq 1.
\end{align}

\end{proof}

\subsection{Sequences of events}\label{app:eventsequences}

\begin{definition}\label{def:markoviansequence}

By a \textbf{Markovian sequence of events}, we mean a sequence, finite or infinite, of time-dependent population vectors $\{ V^{(n)}(t) : \mathbb{R}^+ \rightarrow \mathbb{R}^{d^{(n)}} \}$ together with a corresponding sequence of pairs of stochastic generators $\{ \notickmatrix^{(n)} : \mathbb{R}^{d^{(n)}} \rightarrow \mathbb{R}^{d^{(n)}}, \tickmatrix^{(n)} : \mathbb{R}^{d^{(n)}} \rightarrow \mathbb{R}^{d^{(n+1)}} \}$, the dynamics of which are given by
\begin{align}\label{eq:markovdynamics}
	\frac{d}{dt} V^{(n)}(t) &= \begin{cases}
		\notickmatrix^{(0)} V^{(0)}(t) & \text{for $n=0$}, \\
		\notickmatrix^{(n)} V^{(n)}(t) + \tickmatrix^{(n-1)} V^{(n-1)}(t) & \text{for $ n \geq 1 $},
	\end{cases}
\end{align}
and that satisfy the initial conditions
\begin{itemize}
	\item $V^{(0)}(0)$ is a normalised population vector,
	\item $V^{(n)}(0) = \mathbf{0}$ for all $n \geq 1$.
\end{itemize}

Furthermore, we define the \textbf{delay function of the $n^{th}$ event} as
\begin{align}\label{eq:sequencedelay}
	\tau^{(n)}(t) &= \onenorm{ \tickmatrix^{(n-1)} V^{(n-1)}(t) },
\end{align}
for $n \geq 1$. For $n=0$, the delay function is $\tau^{(0)}(t) = \delta (t)$, the Dirac-delta distribution.

\end{definition}

\begin{remark}

Note that the fact that the $V^{(n)}$ are population vectors and that the $\tau^{(n)}$ are delay functions is not immediate from the above definition, but is nevertheless implied, as the following lemmas will establish.

\end{remark}

\begin{lemma}[Events in a Markovian sequence are recursive convolutions]\label{lemma:sequenceconvolution}

For a Markovian sequence of events (Def. \ref{def:markoviansequence}), each vector in the sequence can be expressed as a convolution w.r.t. the previous one, i.e. for $n \geq 1$,
\begin{align}\label{eq:sequenceconvolution}
	V^{(n)}(t) &= \int_0^t e^{\notickmatrix^{(n)} \left( t - t^\prime \right)} \tickmatrix^{(n-1)} V^{(n-1)} \left( t^\prime \right) dt^\prime,
\end{align}
and for $n=0$,
\begin{align}
	V^{(0)}(t) &= e^{\notickmatrix^{(0)} t} V^{(0)}(0).
\end{align}
\end{lemma}

\begin{proof}

Proof by induction. Consider we define the sequence $f^{(n)}(t)$ by
\begin{align}\label{eq:prooftempsequence}
	f^{(n)}(t) &= \begin{cases}
		e^{\notickmatrix^{(0)} t} V^{(0)}(0) & \text{for $n=0$}, \\
		\int_0^t e^{\notickmatrix^{(n)} \left( t - t^\prime \right)} \tickmatrix^{(n-1)} f^{(n-1)} \left( t^\prime \right) dt^\prime & \text{for $n \geq 1$.}
	\end{cases}
\end{align}

For $n=0$, by construction, $f^{(0)}(t)$ has the same initial conditions and obeys the same differential equation as $V^{(0)}(t)$, and is thus equal to $V^{(0)}(t)$.

Proceeding, let $f^{(n-1)}(t) = V^{(n-1)}(t)$ for some $n \geq 1$. Then differentiating $f^{(n)}(t)$ from Eq. \ref{eq:prooftempsequence} using Leibniz's rule, we find that
\begin{align}
	\frac{d}{dt} f^{(n)}(t) &= \frac{d}{dt} \int_0^t e^{\notickmatrix^{(n)} \left( t - t^\prime \right)} \tickmatrix^{(n-1)} f^{(n-1)} \left( t^\prime \right) dt^\prime \\
	&= \notickmatrix^{(n)} \int_0^t e^{\notickmatrix^{(n)} \left( t - t^\prime \right)} \tickmatrix^{(n-1)} f^{(n-1)} \left( t^\prime \right) dt^\prime + \tickmatrix^{(n-1)} f^{(n-1)} \left( t \right) \\
	&= \notickmatrix^{(n)} f^{(n)}(t) + \tickmatrix^{(n-1)} V^{(n-1)}(t),
\end{align}
and thus $f^{(n)}(t)$ obeys the same differential equation as $V^{(n)}(t)$. Their initial conditions are also the same as $f^{(n)}(0) = \mathbf{0} = V^{(n)}(0)$ for $n \geq 1$. Thus $f^{(n)}(t) = V^{(n)}(t)$, and the rest follows by induction.

\end{proof}

\begin{lemma}[States and delay functions of a Markovian sequence of events]\label{lemma:markovstatedelay}

For a Markovian sequence of events (Def. \ref{def:markoviansequence}),
\begin{itemize}
	\item Every vector $V^{(n)}(t)$ in the sequence is a population vector (Def. \ref{def:popvector}).
	\item Every $\tau^{(n)}(t)$ is a delay function (Def. \ref{def:delayfunction}).
\end{itemize}

\end{lemma}

\begin{proof}

We first prove by induction that the elements of every $V^{(n)}(t)$ w.r.t. the canonical basis are non-negative. At $t=0$, this is true by definition. Furthermore, by Lemma \ref{lemma:sequenceconvolution}, $V^{(0)}(t)$ evolves via the transition operator $e^{\notickmatrix^{(0)} t}$, and is thus always non-negative, by Lemma \ref{lemma:stochasticgenerators}. Proceeding to $V^{(n)}(t)$ from Eq. \ref{eq:sequenceconvolution},
\begin{align}
	V^{(n)}(t) &= \int_0^t e^{\notickmatrix^{(n)} \left( t - t^\prime \right)} \tickmatrix^{(n-1)} V^{(n-1)} \left( t^\prime \right) dt^\prime,
\end{align}
note that if $V^{(n-1)}(t)$ is non-negative for all $t$, then so is $\tickmatrix^{(n-1)} V^{(n-1)}(t)$ as the elements of $\tickmatrix^{(n-1)}$ are all non-negative (Def. \ref{def:stochasticgenerators}), and since this is multiplied by another transition matrix (Lemma \ref{lemma:stochasticgenerators}), whose elements are all non-negative, the integrand is non-negative, and thus $V^{(n)}(t)$ is also non-negative w.r.t. the canonical basis for $t \geq 0$.

To prove that each vector is a population vector, i.e. has an e-sum (Def. \ref{def:norm}) less or equal to $1$, we prove the statement for the sum of e-sums $\sum_{n=0}^m \onenorm{V^{(n)}(t)}$, $m \geq 0$, from which the weaker statement follows.
\begin{align}
	\frac{d}{dt} \sum_{n=0}^m \onenorm{ V^{(n)}(t) } &=  \sum_{n=0}^m  \onenorm{ \frac{d}{dt} V^{(n)}(t) } \\
	&= \onenorm{ \notickmatrix^{(0)} V^{(0)}(t) } + \sum_{n=1}^m \left( \onenorm{ \notickmatrix^{(n)} V^{(n)}(t) } + \onenorm{ \tickmatrix^{(n-1)} V^{(n-1)}(t) } \right) \\
	&= \sum_{n=0}^{m-1} \left( \onenorm{ \notickmatrix^{(n)} V^{(n)}(t)} + \onenorm{ \tickmatrix^{(n)} V^{(n)}(t) } \right) + \onenorm{ \notickmatrix^{(m)} V^{(m)}(t) } \\
	&= \sum_{n=0}^{m-1} \sum_{j=1}^{d^{(n)}} \left( \sum_{i=1}^{d^{(n)}} \mat{\notickmatrix^{(n)}}_{ij} + \sum_{i=1}^{d^{(n+1)}} \mat{\tickmatrix^{(n)}}_{ij} \right) \mat{V^{(n)}(t)}_j + \sum_{j=1}^{d^{(m)}} \left( \sum_{i=1}^{d^{(m)}} \mat{\notickmatrix^{(m)}}_{ij} \right) \mat{V^{(m)}(t)}_j \label{eq:proofseqsum},
\end{align}
where we have used the definition of the e-sum, Def. \ref{def:norm}. The RHS of the above equation is non-positive, as the two column sums in parentheses above are non-positive (see Def. \ref{def:stochasticgenerators} and Corollary \ref{cor:zerotickmatrix}). Thus
\begin{align}
	\frac{d}{dt} \onenorm{ \sum_{n=0}^m V^{(n)}(t) } &\leq 0,
\end{align}
and thus the sum of the norms is non-increasing. At $t=0$ the sum is $1$ by definition (Def. \ref{def:markoviansequence}), and thus the sum is less or equal to unity for $t \geq 0$, from which it follows that each term in the sum, which is also non-negative, must also be between $0$ and $1$. Thus every $V^{(n)}$ is a population vector for all $t \geq 0$.

\bigskip

To prove that every $\tau^{(m)}$ is a delay function, note in Eq. \ref{eq:sequencedelay} that as $\tickmatrix^{(m-1)}$ and $V^{(m-1)}$ are element-wise non-negative and bounded, it follows that $\tau^{(m)}$ is non-negative and bounded as well. To prove integrability, we add up Eq. \ref{eq:sequencedelay} (with $n=m+1$) and Eq. \ref{eq:proofseqsum} to get
\begin{align}
	\tau^{(m+1)}(t) + \frac{d}{dt} \sum_{n=0}^m \onenorm{ V^{(n)}(t) } &= \sum_{n=0}^{m} \sum_{j=1}^{d^{(n)}} \left( \sum_{i=1}^{d^{(n)}} \mat{\notickmatrix^{(n)}}_{ij} + \sum_{i=1}^{d^{(n+1)}} \mat{\tickmatrix^{(n)}}_{ij} \right) \mat{V^{(n)}(t)}_j,
\end{align}
where $m \geq 0$. The RHS is non-positive from the properties of the column sums of the generators, (Eq. \ref{eq:stochasticcondition}), and we label it as the function $g(t)$. Thus $g(t) \leq 0$.

Integrating from $t=0$ to $t=T$, one obtains
\begin{align}
	\int_0^T \tau^{(m+1)}(t) dt &= - \int_0^T \frac{d}{dt} \sum_{n=0}^m \onenorm{ V^{(n)}(t) } dt + \int_0^T g(t) dt \\
	&= \sum_{n=0}^m \onenorm{ V^{(n)}(0) } - \onenorm{ \sum_{n=0}^m V^{(n)}(T) } + \int_0^T g(t) dt \\
	&= 1 - \sum_{n=0}^m \onenorm{ V^{(n)}(T) } + \int_0^T g(t) dt,
\end{align}
using the initial conditions for the sequence of states (Def. \ref{def:markoviansequence}). As $g(t) \leq 0$ for all $t \geq 0$, the RHS of the above expression is less or equal to $1$ for all $T$. However, the integrand on the LHS is non-negative, and thus the integral is non-decreasing w.r.t. $T$. It follows from the monotone convergence theorem\cite{rudin1976principles} that the limit $\lim_{T\rightarrow\infty} \int_0^T \tau^{(m+1)}(t) dt$ exists and is less or equal to $1$.

Thus every $\tau^{(m+1)}$ for $m \geq 0$, or equivalently, every $\tau^{(m)}$ for $m \geq 1$, is a delay function.

\end{proof}

\begin{corollary}\label{cor:validdelayfunction}

Given a single pair of stochastic generators $\{\notickmatrix,\tickmatrix\}$ acting on $\mathbb{R}^d$, together with an arbitrary population vector $V \in \mathbb{R}^d$, the following is a delay function,
\begin{align}
	\tau(t) &= \onenorm{ \tickmatrix e^{\notickmatrix t} V }.
\end{align}

\end{corollary}

\begin{proof}

Take an arbitrary Markovian sequence (Def. \ref{def:markoviansequence}) with the choice of $V^{(0)}(0) = V$,  $\tickmatrix^{(0)} = \tickmatrix$, and $\notickmatrix^{(0)} = \notickmatrix$. Apply Lemma \ref{lemma:markovstatedelay} to deduce that $\tau^{(1)}$ is a delay function, and substitute the solution for the time-evolved state $V^{(0)}(t)$ from Lemma \ref{lemma:sequenceconvolution} to the expression of $\tau^{(1)}(t)$ from Def. \ref{def:markoviansequence}.

\end{proof}

\begin{lemma}[Invariance of the dynamics of an event w.r.t. the following event.]\label{lemma:resetinvariance}

For any Markovian sequence of events, the state and delay function of the $n^{th}$ event in the sequence (as well as those of every previous event) is invariant w.r.t. a change in the $n^{th}$ event generator $\tickmatrix^{(n)}$ that leaves its column sums unchanged, i.e. if $\tickmatrix^{(n)^\prime}$ is chosen such that its matrix elements satisfy
\begin{align}
	\sum_i \mat{\tickmatrix^{(n)\prime}}_{ij} &= \sum_i \mat{\tickmatrix^{(n)}}_{ij} \quad \forall j.
\end{align}

\end{lemma}

\begin{proof}

From Lemma \ref{lemma:sequenceconvolution}, it is clear that the state $V^{(n)}(t)$ corresponding to the $n^{th}$ event is independent of $\tickmatrix^{(n)}$, and does not affect the states and delay functions of any of the events prior to the $n^{th}$. The independence of the $V^{(i)}(t)$ and $\tau^{(i)}(t)$, where $i<n$ follows from the fact that the initial conditions and differential equations for all of the $i<n$ are independent of $i \geq n$.

As for the delay function of the $n^{th}$ event, from Eq. \ref{eq:sequencedelay},
\begin{align}
	\tau^{(n)}(t) &= \onenorm{ \tickmatrix^{(n-1)} V^{(n-1)}(t) } \\
	&= \sum_{ij} \mat{\tickmatrix^{(n-1)}}_{ij} \mat{V^{(n-1)}(t)}_j = \sum_j \left( \sum_i \mat{\tickmatrix^{(n-1)}}_{ij} \right) \mat{V^{(n-1)}(t)}_j,
\end{align}
and is thus invariant under any operation that leaves the column sums of $\tickmatrix^{(n-1)}$ unchanged.

\end{proof}

\begin{remark}

Lemma \ref{lemma:resetinvariance} reflects the fact that the tick generator $\tickmatrix^{(n)}$ encodes both the amount of probability of the event being generated from each canonical state (as reflected by each of the column sums) as well as the state following the generation of an event (encoded in the individual elements of $\tickmatrix^{(n)}$), the first of which affects the dynamics of the $n^{th}$ event, while the second only affects subsequent events.

\end{remark}

\subsection{Independent sequences of events}\label{app:indisequences}

Here we discuss a special class of Markovian sequences, those in which the state of the system immediately following an event is a fixed state, invariant w.r.t. the state of the system prior to the event. Such sequences have useful properties that we use later in the proof.

\begin{definition}\label{def:independentsequence}

A Markovian sequence of events (Def. \ref{def:markoviansequence}) is called an \textbf{independent Markovian sequence of events} if every one of its event generators $\tickmatrix^{(n)}$ is a rank-1 linear operator.

\end{definition}

\begin{remark}[\it Properties of an independent sequence]

If $\tickmatrix$ is a rank-1 linear operator, then all of its columns are proportional to one non-zero column, and therefore, given any vector $V$ in the domain of $\tickmatrix$, the product $\tickmatrix V$ is also proportional to the same fixed column. For a Markovian sequence of events, the term in the dynamical equation $\tickmatrix^{(n-1)} V^{(n-1)}(t)$ (see Eqs. \ref{eq:markovdynamics} and \ref{eq:sequencedelay}) represents the state following the occurrence of the $n^{th}$ event, and thus an independent sequence is one in which this product is proportional to some fixed state for all $t\geq 0$.
\end{remark}

\begin{definition}\label{def:eventresetstate}

For an independent Markovian sequence of events (Def. \ref{def:markoviansequence}), we define the sequence of \textbf{event reset states} $\{V_R^{(n)}\}$ as follows: for each $n$, $V_R^{(n)}$ is the unique normalised vector that every column of $\tickmatrix^{(n)}$ is proportional to.

\end{definition}

\begin{remark}

Note that as every element of $\tickmatrix^{(n)}$ is non-negative, it follows that every event reset state is a normalised population vector (Def. \ref{def:popvector}).

\end{remark}

\begin{lemma}\label{lemma:eventresetstate}

For an independent Markovian sequence,
\begin{align}
	\tickmatrix^{(n-1)} V^{(n-1)}(t) &= \tau^{(n)}(t) V_R^{(n)}.
\end{align}

\end{lemma}

\begin{proof}
	The proof follows from the definition of the event reset state, Def. \ref{def:eventresetstate} and the event delay function, Def. \ref{def:markoviansequence}, Eq. \ref{eq:sequencedelay}.
\end{proof}

\begin{definition}\label{def:canonicalsequence}

A \textbf{canonical independent Markovian sequence of events} is an independent sequence (Def. \ref{def:independentsequence}) in which the initial state and every reset state (Def. \ref{def:eventresetstate}) in the sequence is a canonical state (Def. \ref{def:canonicalbasis}). Alternatively, it is a sequence in which the initial state is a canonical state, and every event generator $\tickmatrix^{(n)}$ has a single non-zero row.

\end{definition}

\begin{definition}\label{def:resetsubeventdelay}

For an independent sequence of Markovian events (Def. \ref{def:independentsequence}), one defines the \textbf{sub-event delay function} as
\begin{align}
	\nu^{(n)}(t) &= \onenorm{ \tickmatrix^{(n-1)} e^{\notickmatrix^{(n-1)} t} V_R^{(n-1)} }.
\end{align}

\begin{remark}

The $n^{th}$ sub-event delay function refers to the delay function of the $n^{th}$ event \textit{from the time of occurrence of event $n-1$}, as opposed to the $n^{th}$ delay function, which is constructed w.r.t. the initial time $t=0$.

\end{remark}

\begin{remark}

That $\nu^{(n)}$ is indeed a delay function follows from Corollary \ref{cor:validdelayfunction}. Note that $\nu^{(n)}(t)$ is independent of all other quantities in the sequence other than those that determine the occurrence of the $n^{th}$ event, namely the stochastic generators $\{\notickmatrix^{(n-1)},\tickmatrix^{(n-1)}\}$ and the event reset state $V_R^{(n-1)}$.

\end{remark}

\end{definition}

\begin{lemma}[The states and delay functions of an independent Markovian sequence]\label{lemma:resetsequenceconvolution}

For an independent Markovian sequence of events (Def. \ref{def:independentsequence}), every vector and delay function in the sequence can be expressed recursively for $n \geq 1$ as
\begin{align}
	V^{(n)}(t) &= \int_0^t e^{\notickmatrix^{(n)} (t-t^\prime)} V_R^{(n)} \tau^{(n)}(t^\prime) dt^\prime \label{eq:resetsequencestate} \\
	\tau^{(n)}(t) &= \left( \tau^{(n-1)} \conv \nu^{(n)} \right) (t), \label{eq:resetsequencedelay}
\end{align}
where $\nu^{(n)}(t)$ is the $n^{th}$ sub-event delay function, Def. \ref{def:resetsubeventdelay}. Note that $\tau^{(0)}(t) = \delta(t)$ by definition (Def. \ref{def:markoviansequence}), and we equate the reset state for the zeroth event $V_R^{(0)}$ to the initial state $V^{(0)}(0)$.

It follows that the delay function of the $n^{th}$ event is the sequential convolution of the delay function of all previous events,
\begin{align}\label{eq:resetsequencedelayconvolution}
	\tau^{(n)}(t) &= \left( \nu^{(1)} \conv \nu^{(2)} \conv ... \conv \nu^{(n)} \right) (t),
\end{align}
and the state of the $n^{th}$ event is similarly given by the sequential convolution
\begin{align}\label{eq:resetsequencestateconvolution}
	V^{(n)}(t) &= \int_0^t e^{\notickmatrix^{(n)} (t-t^\prime)} V_R^{(n)} \left( \nu^{(1)} \conv \nu^{(2)} \conv ... \conv \nu^{(n)} \right) (t^\prime) dt^\prime.
\end{align}

\end{lemma}

\begin{proof}

The first statement of the Lemma, Eq. \ref{eq:resetsequencestate}, follows from Lemmas \ref{lemma:sequenceconvolution} and \ref{lemma:eventresetstate}. For the second statement (Eq. \ref{eq:resetsequencedelay}), we take the definition of the delay function (Eq. \ref{eq:sequencedelay}). For $n \geq 1$,
\begin{align}
	\tau^{(n)}(t) &= \onenorm{ \tickmatrix^{(n-1)} \int_0^t e^{\notickmatrix^{(n-1)} (t-t^\prime)} V_R^{(n-1)} \tau^{(n-1)}(t^\prime) dt^\prime } \\
	&= \int_0^t \onenorm{ \tickmatrix^{(n-1)} e^{\notickmatrix^{(n-1)} (t-t^\prime)} V_R^{(n-1)} } \tau^{(n-1)}(t^\prime) dt^\prime \\
	&= \int_0^t \nu^{(n)}(t-t^\prime) \; \tau^{(n-1)}(t^\prime) dt^\prime \\
	&= \left( \tau^{(n-1)} \conv \nu^{(n)} \right) (t),
\end{align}
where $\nu^{(n)}$ is the sub-event delay function, Def. \ref{def:resetsubeventdelay}. Proceeding by induction, one recovers Eqs. \ref{eq:resetsequencedelayconvolution} and \ref{eq:resetsequencestateconvolution}.

\end{proof}

\begin{lemma}\label{lemma:resetsequencescale}

In an independent Markovian sequence of events (Def. \ref{def:independentsequence}), if a pair of stochastic generators is scaled as
\begin{align}
	\{\notickmatrix^{(n)},\tickmatrix^{(n)}\} \rightarrow  	\{a\notickmatrix^{(n)},a\tickmatrix^{(n)}\},
\end{align}
where $a>0$, the delay function of the $m^{th}$ event in the sequence, where $m>n$, is modified to be
\begin{align}
	\tau^{(m)}(t) &= \left( \nu^{(1)} \conv \nu^{(2)} \conv ... \conv \tilde{\nu}^{(n+1)} \conv ... \conv \nu^{(m)} \right) (t), \\
	\text{where} \quad \tilde{\nu}^{(n+1)}(t) &= a \cdot \nu^{(n+1)}(at).
\end{align}

For $m \leq n$, the delay function is left unchanged.

\end{lemma}

\begin{proof}

The sequence is still independent, as scaling up the event generator $\tickmatrix^{(n)}$ by a positive constant does not change its rank. Thus Lemma \ref{lemma:resetsequenceconvolution} still applies, and by Eq. \ref{eq:resetsequencedelayconvolution}, one only has to consider the modification to the $(n+1)^{th}$ sub-event delay function, (see Def. \ref{def:resetsubeventdelay}),
\begin{align}
	\tilde{\nu}^{(n+1)} &= \onenorm{ a \cdot \tickmatrix^{(n-1)} e^{a \cdot \notickmatrix^{(n-1)} t} V_R^{(n-1)} } \\
	 &= a \onenorm{ \tickmatrix^{(n-1)} e^{\notickmatrix^{(n-1)} (at)} V_R^{(n-1)} } \\
	 &= a \cdot \nu^{(n+1)}(at).
\end{align}

\end{proof}

\begin{lemma}[The delay function of a sequence in terms of canonical independent sequences]\label{lemma:generalindependent}

Given a Markovian sequence (Def. \ref{def:markoviansequence}), the $n^{th}$ delay function and state (for $n \geq 1$ in the sequence may be expressed in terms of convolutions of sub-event delay functions (Def. \ref{def:resetsubeventdelay}) as follows:
\begin{align}
	\tau^{(n)}(t) &= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_n=1}^{d^{(n)}} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(1)}_{i_{n-1}i_n} \right)(t), \\
	V^{(n)}(t) &= \int_0^t e^{\notickmatrix^{(n)} (t-t^\prime)}  \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_n=1}^{d^{(n)}} \mathbf{e}^{(n)}_{i_n} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(1)}_{i_{n-1}i_n} \right)(t^\prime) dt^\prime,
\end{align}
where $v_{i_0}$ are the coefficients of the initial state in its canonical basis,
\begin{align}\label{eq:initialstatecanonical}
	V^{(0)}(0) &= \sum_{i_0}^{d^{(0)}} v_{i_0} \mathbf{e}^{(0)}_{i_0},
\end{align}
the \textbf{canonical sub-event delay functions} $\nu_{i_{j-1}i_j}$ are defined as
\begin{align}\label{eq:canonicalsub-eventdelay}
	\nu^{j}_{i_{j-1}i_j} (t) &= \onenorm{ \tickmatrix^{(j-1)}_{i_j} e^{\notickmatrix^{(j-1)} t} \mathbf{e}^{(j-1)}_{i_{j-1}} }, \quad i_{j-1} \in \{1,2,...,d^{(j-1)}\}, \; i_j \in \{1,2,...,d^{(j)}\},
\end{align}
and in turn the \textbf{canonical event generators} $\tickmatrix^{(j-1)}_{i_j}$ are defined to be the original generator $\tickmatrix^{(j-1)}$ with all the rows except row $i_j$ set to zero. Thus
\begin{subequations}\label{eq:canonicalgenerators}
\begin{align}
	\tickmatrix^{(j-1)} &= \sum_{i_j=1}^{d^{(j)}} \tickmatrix^{(j-1)}_{i_j}, \\
	\text{where} \mat{\tickmatrix^{(j-1)}_{i_j}}_{kl} &= \delta_{i_j,k} \mat{\tickmatrix^{(j-1)}}_{kl}.
\end{align}
\end{subequations}

\end{lemma}

\begin{remark} \textbf{Explanation of Lemma \ref{lemma:generalindependent}.}

The difference between a canonical independent Markovian sequence (Def. \ref{def:canonicalsequence}) and a general Markovian sequence (Def. \ref{def:markoviansequence}) is as follows. In the first case, the initial state and the states following the occurrence of every event in the sequence are canonical states, which is equivalent to every event generator in the sequence having a single non-zero row. For a general sequence, this is not the case.

However, even in the case of a general sequence, one can split each event generator into the sum of matrices with single non-zero rows, each corresponding to a single canonical state (hence the term \textbf{canonical generators}). Note from Lemma \ref{lemma:sequenceconvolution} that the states and delay functions of every event are linear w.r.t. the event generators, and thus by splitting the event generators of a general sequence into canonical generators, we find that states and delay functions may be expressed as a linear combination of each of the terms in the split. Thus the general sequence turns into a tree-like graph, where each event corresponds to branching out w.r.t. all the possible canonical states after the event has occurred.

In other words, we decompose a Markovian sequence into the sum of all the possible canonical independent Markovian sequences that occur within it, and the above lemma expresses the states and delay functions of the original sequence as the same sum over the canonical sequences.

\end{remark}

\begin{proof}

Proof by induction. Consider the case of $n=1$. For the delay function $\tau^{(1)}$, from Eq. \ref{eq:sequencedelay},
\begin{align}\label{eq:firstdelayfunction}
	\tau^{(1)} &= \onenorm{ \tickmatrix^{(0)} V^{(0)}(t) }.
\end{align}

We may use the solution for $V^{(0)}(t)$ from Lemma \ref{lemma:sequenceconvolution}, and the decomposition of the initial state in the canonical basis (Eq. \ref{eq:initialstatecanonical},
\begin{align}
	V^{(0)}(t) &= e^{\notickmatrix^{(0)} t} V^{(0)}(0) = \sum_{i_0=1}^{d^{(0)}} e^{\notickmatrix^{(0)} t} v_{i_0} \mathbf{e}^{(0)}_{i_0}.
\end{align}

We also split the event generator $\tickmatrix^{(0)}$ into the sum of canonical generators (Eq. \ref{eq:canonicalgenerators}),
\begin{align}
	\tickmatrix^{(0)} &= \sum_{i_1=1}^{d^{(1)}} \tickmatrix^{(0)}_{i_1}.
\end{align}

Substituting these back into the delay function of the first event (Eq. \ref{eq:firstdelayfunction}), one obtains
\begin{align}
	\tau^{(1)} &= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} v_{i_0} \onenorm{ \tickmatrix^{(0)}_{i_1} e^{\notickmatrix^{(0)} t} \mathbf{e}^{(0)}_{i_0} } \\
	&= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} v_{i_0} \nu^{(1)}_{i_0i_1},
\end{align}
using the definition of the canonical sub-event delay function (Eq. \ref{eq:canonicalsub-eventdelay}). Thus $\tau^{(1)}$ satisfies the statement of the lemma.

For the state $V^{(1)}$, we apply Lemma \ref{lemma:sequenceconvolution},
\begin{align}
	V^{(1)}(t) &= \int_0^t e^{\notickmatrix^{(1)} \left( t - t^\prime \right)} \tickmatrix^{(0)} V^{(0)} \left( t^\prime \right) dt^\prime,
\end{align}
and follow the same procedure of decomposing the state and event generator, resulting in
\begin{align}\label{eq:tempfirststate}
		V^{(1)}(t) &= \int_0^t e^{\notickmatrix^{(1)} \left( t - t^\prime \right)} \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}}  v_{i_0} \left( \tickmatrix^{(0)}_{i_1} e^{\notickmatrix^{(0)} t^\prime} \mathbf{e}^{(0)}_{i_0} \right) dt^\prime.
\end{align}

The term in parentheses above is proportional to $\mathbf{e}^{(1)}_{i_1}$, as the generator $\tickmatrix^{(0)}_{i_1}$ has only a single non-zero row, which is row $i_1$, corresponding to the canonical state $\mathbf{e}^{(1)}_{i_1}$. Furthermore, the e-sum of the term has already been defined as the canonical sub-event delay function (Eq. \ref{eq:canonicalsub-eventdelay}), and thus we can express it as
\begin{align}\label{eq:associatesub-event}
	\tickmatrix^{(0)}_{i_1} e^{\notickmatrix^{(0)} t^\prime} \mathbf{e}^{(0)}_{i_0} = \mathbf{e}^{(1)}_{i_1} \nu^{(1)}_{i_0i_1}(t^\prime).
\end{align}

Substituting this back into Eq. \ref{eq:tempfirststate},
\begin{align}
	V^{(1)}(t) &= \int_0^t e^{\notickmatrix^{(1)} \left( t - t^\prime \right)} \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} v_{i_0} \mathbf{e}^{(1)}_{i_1} \nu^{(1)}_{i_0i_1}(t^\prime)  dt^\prime,
\end{align}
which satisfies the statement of the lemma.

Proceeding, assume that the lemma is satisfied up to and including $n=k$. For the next delay function $\tau^{(k+1)}$, from Eq. \ref{eq:sequencedelay},
\begin{align}
	\tau^{(k+1)} &= \onenorm{ \tickmatrix^{(k)} V^{(k)}(t) } \\
	&= \onenorm{ \sum_{i_{k+1}=1}^{d^{(k+1)}} \tickmatrix^{(k)}_{i_{k+1}} \int_0^t e^{\notickmatrix^{(k)} (t-t^\prime)}  \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_k=1}^{d^{(k)}} \mathbf{e}^{(k)}_{i_k} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \right)(t^\prime) dt^\prime } \\
	&= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} v_{i_0} \int_0^t \onenorm{ \tickmatrix^{(k)}_{i_{k+1}} e^{\notickmatrix^{(k)} (t-t^\prime)} \mathbf{e}^{(k)}_{i_k} } \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \right)(t^\prime) dt^\prime,
\end{align}
where we have applied the lemma for the state $V^{(k)}(t)$, and then simply rearranged terms (all of the states, sums are finite, and so is the integral).

Identifying the term in the e-sum as another canonical sub-event delay function (Eq. \ref{eq:canonicalsub-eventdelay}), we get
\begin{align}
	\tau^{(k+1)} &= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} v_{i_0} \int_0^t \nu^{(k+1)}_{i_ki_{k+1}}(t-t^\prime) \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \right)(t^\prime) dt^\prime \\
	&= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_n} \conv \nu^{(k+1)}_{i_ki_{k+1}} \right)(t).
\end{align}
Thus $\tau^{(k+1)}$ also satisfies the lemma.

Finally, we express $V^{(k+1)}$ using Lemma \ref{lemma:sequenceconvolution},
\begin{align}
	V^{(k+1)}(t) &= \int_0^t e^{\notickmatrix^{(k+1)} \left( t - t^\prime \right)} \tickmatrix^{(k)} V^{(k)} \left( t^\prime \right) dt^\prime \\
	&= \int_0^t e^{\notickmatrix^{(k+1)} \left( t - t^\prime \right)} \tickmatrix^{(k)} \int_0^{t^\prime} e^{\notickmatrix^{(k)} (t^\prime-t^{\prime\prime})}  \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_k=1}^{d^{(k)}} \mathbf{e}^{(k)}_{i_k} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \right)(t^{\prime\prime}) dt^{\prime\prime} dt^\prime,
\end{align}
where we have applied the lemma to $V^{(k)}$. Once again, we can split the generator $\tickmatrix^{(k)}$ into canonical generators (Eq. \ref{eq:canonicalgenerators}), and rearrange the integral and sums appropriately,
\begin{align}
	V^{(k+1)}(t) &= \int_0^t e^{\notickmatrix^{(k+1)} \left( t - t^\prime \right)} \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} \int_0^{t^\prime} \tickmatrix^{(k)}_{i_{k+1}} e^{\notickmatrix^{(k)} (t^\prime-t^{\prime\prime})}   \mathbf{e}^{(k)}_{i_k} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \right)(t^{\prime\prime}) dt^{\prime\prime} dt^\prime.
\end{align}

Once again, we can associate one of the terms above to a canonical sub-event delay function (Eq. \ref{eq:canonicalsub-eventdelay}), as we did in Eq. \ref{eq:associatesub-event},
\begin{align}
	\tickmatrix^{(k)}_{i_{k+1}} e^{\notickmatrix^{(k)} (t^\prime-t^{\prime\prime})}   \mathbf{e}^{(k)}_{i_k} &= \mathbf{e}^{(k+1)}_{i_{k+1}} \nu^{(k+1)}_{i_ki_{k+1}} (t^\prime - t^{\prime\prime}),
\end{align}
which results in
\begin{align}
	V^{(k+1)}(t) &= \int_0^t e^{\notickmatrix^{(k+1)} \left( t - t^\prime \right)} \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} \int_0^{t^\prime} \mathbf{e}^{(k+1)}_{i_{k+1}} \nu^{(k+1)}_{i_ki_{k+1}} (t^\prime - t^{\prime\prime}) v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(1)}_{i_{k-1}i_k} \right)(t^{\prime\prime}) dt^{\prime\prime} dt^\prime \\
	&= \int_0^t e^{\notickmatrix^{(k+1)} \left( t - t^\prime \right)} \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_{k+1}=1}^{d^{(k+1)}} \mathbf{e}^{(k+1)}_{i_{k+1}} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(k)}_{i_{k-1}i_k} \conv \nu^{(k+1)}_{i_ki_{k+1}} \right) (t^\prime) dt^\prime,
\end{align}
which also satisfies the lemma. By induction, the lemma applies for all $n \geq 1$.

\end{proof}

\subsection{Result on the accuracy of Markovian sequences}\label{app:resetresult}

\begin{theorem}\label{theorem:markovianaccuracy}

Given a Markovian sequence (Def. \ref{def:markoviansequence}), there exists a canonical independent Markovian sequence (Def. \ref{def:canonicalsequence}) such that
\begin{itemize}
	\item the vectors and generators of the canonical sequence are of the same dimension as the original sequence, i.e. $d^{(n)}$ remain the same for all $n$, and
	\item the accuracies (Def. \ref{def:accuracydelayfunction}) of every event in the canonical sequence, i.e. the accuracies of each of the event delay functions (Eq. \ref{eq:sequencedelay}) upper bounds those of the original sequence.
\end{itemize}

Furthermore, one such canonical independent Markovian sequence can be explicitly constructed from the original sequence by
\begin{itemize}
	\item changing the initial state to a well chosen canonical state,
	\item making all of the event generators $\tickmatrix^{(n)}$ into rank-1 matrices by keeping only a single non-zero row, possibly shifted to a different row, and
	\item scaling each pair of event generators $\{\notickmatrix^{(n)},\tickmatrix^{(n)}\}$ by well chosen positive constants.
\end{itemize}

\end{theorem}

\begin{remark}

The major implication of this theorem is that if one's interest is in upper bounding the accuracy of Markovian sequences, then it suffices to optimize over the much smaller subset of canonical independent Markovian sequences, which are far more tractable.

Our main use for this theorem is to straightforwardly apply it to imply that ``reset" clocks, i.e. those that go to a fixed state every time they tick, are the most accurate. However, the content of this theorem is more general than its application to clocks.

\end{remark}

\begin{proof}

We begin by taking restating the first part of Lemma \ref{lemma:generalindependent}, which states that each of the delay functions of a Markovian sequence of events may be expressed as
\begin{align}\label{eq:prooftempdelayconvolution}
	\tau^{(n)}(t) &= \sum_{i_0=1}^{d^{(0)}} \sum_{i_1=1}^{d^{(1)}} ... \sum_{i_n=1}^{d^{(n)}} v_{i_0} \left( \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(1)}_{i_{n-1}i_n} \right)(t),
\end{align}
where the canonical sub-event delay functions $v_{i_{j-1}i_j}$ are defined in Eq. \ref{eq:canonicalsub-eventdelay}, with the associated canonical event generators subsequently in Eq. \ref{eq:canonicalgenerators}.

Applying Lemma \ref{lemma:delaymixture} regarding the accuracy of mixtures of delay functions to Eq. \ref{eq:prooftempdelayconvolution},
\begin{align}
	R \left[ \tau^{(n)} \right] \leq \max_{i_0,i_1,...,i_n} R \left[ \nu^{(1)}_{i_0i_1} \conv \nu^{(2)}_{i_1i_2} \conv ... \conv \nu^{(1)}_{i_{n-1}i_n} \right],
\end{align}
where the range of each $i_j$ above (and in what follows) is $\{1,2,...,d^{(j)}\}$ . We follow by applying Lemma \ref{lemma:delaysequence} regarding the accuracy of convolutions of delay functions, and find that
\begin{align}
	R \left[ \tau^{(n)} \right] \leq \max_{i_0,i_1,...,i_n} \left( R \left[ \nu^{(1)}_{i_0i_1} \right] + R \left[ \nu^{(2)}_{i_1i_2} \right] + ... + R \left[ \nu^{(n)}_{i_{n-1}i_n} \right] \right).
\end{align}

In the maximization above, each $i_j$ for $1 \leq j \leq n-1$ appears twice, in $\nu^{(j)}_{i_{j-1}i_j}$ and $\nu^{(j+1)}_{i_ji_{j+1}}$. Relaxing the maximization to allow for independent maximization of each accuracy, we end up with
\begin{align}
	R \left[ \tau^{(n)} \right] \leq \max_{i_0,i_1^\prime,i_1,i_2^\prime,i_2,...,i_{n-1}^\prime,i_{n-1},i_n} \left( R \left[ \nu^{(1)}_{i_0i_1^\prime} \right] + R \left[ \nu^{(2)}_{i_1i_2^\prime} \right] + ... + R \left[ \nu^{(n-1)}_{i_{n-2}i_{n-1}^\prime} \right] + R \left[ \nu^{(n)}_{i_{n-1}i_n} \right] \right).
\end{align}

In other words, if we label by $R^{max}_j$ the best accuracy from among the sub-event delay functions of the $j^{th}$ event,
\begin{align}\label{eq:accuracymaximization}
	R^{max}_j &= \max_{i_{j-1},i_j} R \left[ \nu^{(j)}_{i_{j-1}i_j} \right],
\end{align}
then the accuracy of the $n^{th}$ event in the sequence is bounded by
\begin{align}\label{eq:accuracyresetbound}
	R \left[ \tau^{(n)} \right] \leq \sum_{j=1}^n R^{max}_j.
\end{align}

To complete the proof, we construct a canonical independent Markovian sequence from the original sequence, that saturates the above inequality.

Consider that one performs the maximization in Eq. \ref{eq:accuracymaximization} for every event $j \in \{1,2,...,n\}$. Doing so for the $j^{th}$ event will return the optimal indices $i_{j-1}$ and $i_j$, that we label as $l_{j-1}$ and $m_j$ respectively. We also label the optimal canonical sub-event delay function as $\zeta^{(j)}$,
\begin{align}\label{eq:optimalsub-eventdelay}
	\zeta^{(j)} &= \nu^{(j)}_{l_{j-1}m_j}.
\end{align}

In other words, the optimal canonical sub-event delay function for the $j^{th}$ event is obtained by starting in the canonical state $\mathbf{e}^{(j-1)}_{l_{j-1}}$, and associated with the canonical event generator $\tickmatrix^{(j)}_{m_j}$ (Eq. \ref{eq:canonicalgenerators}) that results in the state $\mathbf{e}^{(j)}_{m_j}$ when the event occurs.

Our first step in the construction of the new independent sequence is to take the original Markovian sequence, and change all of the event generators $\tickmatrix^{(j)}$ into the optimal generators $\tickmatrix^{(j)}_{m_j}$, by setting all of the rows except row $m_j$ to zero. The new sequence is now a canonical independent Markovian sequence (Def. \ref{def:independentsequence}).

However, this is not enough, as we note that $m_j \neq l_j$ in general, i.e. the optimal canonical generator for the $j^{th}$ event may not correspond to the optimal initial canonical state for event $j+1$. However, by Lemma \ref{lemma:resetinvariance}, a delay function is left unchanged under operations that leave the column sums of its event generator the same. Since $\tickmatrix^{(j)}_{m_j}$ has a single non-zero row, we shift the row from the $m_j$ position to the $l_j$ position, to obtain a new canonical generator $\tilde{\tickmatrix}^{(j)}$, that is both optimal w.r.t. its own event as well as the initial canonical state for the next event.

By construction, we now have a canonical independent Markovian sequence, whose individual sub-event delay functions (Def. \ref{def:resetsubeventdelay}) are the ones with the optimal accuracy, i.e. the $\zeta^{(j)}$ from Eq. \ref{eq:optimalsub-eventdelay}. From Lemma \ref{lemma:resetsequenceconvolution}, the delay function of the $n^{th}$ event in the new sequence is now
\begin{align}
	\tilde{\tau}^{(n)} (t) &= \left( \zeta^{(1)} \conv \zeta^{(2)} \conv ... \conv \zeta^{(n)} \right) (t).
\end{align}

Applying Lemma \ref{lemma:delaysequence} to the above delay function, we get that the accuracy is bounded by
\begin{align}
	R \left( \tilde{\tau}^{(n)} \right) &\leq \sum_{j=1}^n R \left( \zeta^{(j)} \right) = \sum_{j=1}^n R^{max}_j.
\end{align}

From Lemma \ref{lemma:delaysequence}, equality holds only if the mean $\mu$ of each optimal delay function $\zeta^{(j)}$ satisfies
\begin{align}\label{eq:havetosatisfy}
	\frac{ \mu \left( \zeta^{(j)} \right) }{ R \left( \zeta^{(j)} \right)} &= \frac{ \mu \left( \zeta^{(j)} \right) }{ R \left( \zeta^{(j)} \right)} \quad \forall j,k \in \{1,2,...,n\}.
\end{align}

This is not automatically true from our construction so far. However, from Lemma \ref{lemma:resetsequencescale}, we can scale the $j^{th}$ pair of event generators by a positive constant $a_j$ in the sequence to change the sub-event delay function from $\zeta^{(j)}(t)$ to $a \zeta^{(j)}(at)$, leaving every other sub-event delay function unchanged. Furthermore, by Lemma \ref{lemma:delayscale}, such a scaling operation does not affect the accuracy of the sub-event delay function, but does scale its mean (the new mean is divided by $a_j$).

Thus we can pick a series of positive constants $\{a_j\}$ to scale each pair of generators in the independent sequence we have constructed so that every sub-event delay function has the same ratio of mean to accuracy, and thus satisfies Eq. \ref{eq:havetosatisfy}.

As a result, we are left with the canonical independent sequence satisfying the statement of the lemma, whose accuracy saturates Eq. \ref{eq:accuracyresetbound}, which itself is an upper bound to the accuracy of the original sequence.

\end{proof}


TITLE: Particle motion with friction $F=-rv$
QUESTION [0 upvotes]: Consider initial motion of a particle with frictional damping that is proportional to the vector velocity with damping coefficient $(F=-rv)$ Assum an initial condition of $u = U$ and $v = V$ at $t = 0$. Derive and describe the solution for the trajectory of the particle in the absence of any forcing other than friction.
I tried looking this up and all I can find is harmonic oscillators but the question says friction only and does not specify to be on a spring.
Is there an ODE out there that can help me solve this?

REPLY [1 votes]: We are only interested when only friction acts on the particle. Newton's second law gives,
$$F=ma=mv'=-rv$$
This means
$$\int m \frac{v'}{v} dt = \int -r dt$$
$$m\ln|v(t)|=-rt+c$$
Let $t=0$
$$m \ln|V|=c$$
So that,
$$m\ln |\frac{v(t)}{V}|=-rt$$
$$v(t)=Ve^{\frac{-rt}{m}}$$
Integrating both sides of this with respect to time then letting $t=0$,
$$u(t)=-\frac{m}{r}Ve^{\frac{-rt}{m}}+c_2$$
$$U=-\frac{m}{r}V+c_2$$
$$u(t)=(U+\frac{m}{r}V)-\frac{m}{r}Ve^{\frac{-rt}{m}}$$
This an exponential function with a horizontal asymptote,
$$U+\frac{m}{r}V$$


text:
\begin{document}
\maketitle

\begin{abstract}
	In the paper we have analyzed spectral similarity between Barab\'asi-Albert and
Chung-lu models. We have shown the similarity of spectral distribution for
sufficiently large Barab\'asi-Albert parameter value. Contrary, extreme
eigenvalues and principal eigenvector are not similar for those model. We
provide applications of obtained results related to the spectral graph theory
and efficiency of quantum spatial search
\end{abstract}

\section{Introduction}

From the very first paper concerning random graphs \cite{erdos1959random}, many
new random graph models have appeared in the literature
\cite{albert2002statistical,watts1998collective,
	chung2002connected,penrose2003random}. They can be divided into two large
classes: those for which the edges are added independently, like \ER
\cite{erdos1959random} or \CL \cite{chung2002connected}, and those for which
such independence does not appear, like \BA \cite{albert2002statistical} or
Watts-Strogatz~\cite{watts1998collective}. The first class is usually easier to
analyze, especially in the context of its spectral properties
\cite{chung2011spectra,erdHos2013spectral}. Unfortunately graph models from the
second class have usually more desirable properties, like small-world or
power-law degree distribution \cite{albert2002statistical}.

Clearly, the models where the edges are added dependently cannot be described by
any model with independently added edges. However, it may be possible that some
properties match. As an example, let us consider the degree distribution between
\ER and Watts-Strogatz models. While they are different, the degree
distributions in both models are homogeneous. However, the spectral properties
of these models in general differ. This includes spectral distribution and
second greatest eigenvalue distribution of adjacency matrix
\cite{farkas2001spectra}. This is important as, spectral properties have
application in both computer science and physics
\cite{anand2011shannon,glos2018vertices,chakraborty2016spatial,faccin2013degree}.

Still it is interesting whether spectral properties correspond for other models.
Since \BA model has triangle-like spectral distribution
\cite{farkas2001spectra}, it should not be compared to \ER model. As the degree
distribution has strong influence on spectral distribution
\cite{nadakuditi_spectra_2013,dorogovtsev2003spectra} the difference may come
from the fact, that \BA model follows power-law degree distribution. Hence \CL
model, which can access arbitrary degree distribution, is better suited model
for spectral comparison.

In this paper we compare \BA model and properly parametrized \CL model in
context of spectral properties. Taking into account the applications in physics
and computer science \cite{anand2011shannon,glos2018vertices,
	chakraborty2016spatial,faccin2013degree}, we focus on the distribution of the
first, the second and the last eigenvalue, the principal eigenvector,
and the spectral distribution of adjacency matrix.

The paper is organized as follows. In Sec.~\ref{sec:preliminaries}, we provide
basic concepts of random graph theory and we specify the research problem. In
Sec.~\ref{sec:numerical-analysis} we specify the experiment and we perform
numerical analysis of spectral similarity between \BA and \CL models. In
Sec.~\ref{sec:conclusion}, we conclude and discuss our results.

\section{Preliminaries}\label{sec:preliminaries}

\BA model $\mathcal G^{\rm BA}_{n}(m_0)$ is an iterative random graph model.
Starting with complete graph of order $m_0$, new vertices are added and
connected randomly with already existing vertices. Instead of connecting them
uniformly at random, vertex $\bar v $ is new neighbour to a newly added vertex with
probability $p_{\bar v} = d_{\bar v}/\sum_vd_v$, where $d_v$ is the degree of
vertex $v$. This way complex graphs are most likely to be generated. Expectedly,
the degree distribution is a power-law distribution of the
form\cite{bollobasdegree}
\begin{equation}
d(k) = \frac{2m_0(m_0+1)}{k(k+1)(k+2)},
\end{equation}
which implies $d(k)\propto k^{-3}$. Contrary to \ER model, the spectrum is not a
semicircle distribution, but mostly it is triangle like
\cite{farkas2001spectra}. Currently, the formula for spectral distribution is
not known.

Contrary to \BA model, in \CL model $\mathcal{G}^{\rm CL}_n(\w)$ the edges appear
independently. The model is a generalization of \ER model with not
necessarily homogeneous degree distribution. Suppose we have real valued vector
$\w=(w_1,\dots,w_n)$ such that $0\leq w_i\leq n-1$. Then, the edge between
vertex $v_i$ and $v_j$ is added with probability
$w_iw_j/\sum_{k=1}^n w_k$ independently. Note that $w_i$ refers to the expected
degree of the vertex $v_i$. The \ER model is recovered for constant $\w$ vector.
Note that \CL is quite a general model, since there are no further restrictions
on $\w$ vector.

\begin{comment}
While for \BA model the spectral distribution is not known, the are known partial results for \CL model. Suppose $d(k)$ is limiting distribution of expected degree, and $c$ is expectation of $d$. Then if $h$ is a complex function being the solution of
\begin{equation}
h^2(z) = \frac{1}{c}\int_{0}^{\infty} \frac{k d(k)\dd k}{z/h(z)-k}, \label{eq:h-definition}
\end{equation} the spectral distribution of adjacency matrix takes the form
\begin{equation}
\varrho(z) = -\frac{c}{\pi z} \Im h^2(z), \label{eq:spectralbulk-formula-2}
\end{equation}
where $\Im$ is taken in the limit as $z$ tends to real line from above \cite{nadakuditi_spectra_2013}. Furthermore under some requirements, further spectral properties are known. Let $\widetilde \w = \sum_{i=1}^n w_i^2/\sum_{i=1}^n w_i$. For adjacency matrix, if the maximal expected degree $m =\max_{i=1,\dots,n} (w_i)$  grows as $\omega(\ln(n))$, the maximal eigenvalue satisfies
\begin{equation}
|\lambda_{1} - \widetilde \w| \leq \sqrt{8m \ln(\sqrt{2}n)}.
\end{equation}
Furthermore we have
\begin{equation}
|\lambda_i| \leq \sqrt{8m \ln(\sqrt{2}n)},
\end{equation}
for $i=2,\dots,n$ \cite{chung2011spectra}.
\end{comment}

The \BA and \CL models are necessarily different. As an example one can consider
the graphs size: for \BA model the size is fixed for fixed $n$ and $m_0$, while
for \CL model the size is a random variable. However despite this fact, it is
possible they have similar spectral properties. More precisely the question is
whether for given value $m_0$ and naturally chosen parameter $\w$, some
spectral properties of \BA and \CL are similar.

In this paper we analyze following spectral properties of adjacency matrix:
\begin{enumerate}
	\item spectral distribution,
	\item distribution of largest eigenvalue,
	\item distribution of second largest eigenvalue,
	\item distribution of smallest eigenvalue,
	\item eigenvector corresponding to the largest eigenvalue (principal eigenvector).
\end{enumerate}
All of them have application in computer science and physics
\cite{anand2011shannon,glos2018vertices,
	chakraborty2016spatial,faccin2013degree}.

Our numerical analysis can be divided into two steps. In the first we determined
$\w$ for each $m_0=1,\dots,6$, which are typical for \BA analysis. In the second
step, for various graph order we determined the values of extreme eigenvalues,
principal eigenvector and spectral distribution. We compared both models using
various similarity measures. For eigenvalues and spectral distribution we chose
the $p$-values of Kolmogorov-Smirnov test. For principal vector we chose the
measures based on uniform norm distance and Euclidean distance.

\section{Numerical analysis} \label{sec:numerical-analysis}

In this section we analyze numerically the similarity of spectral properties
listed in Sec.~\ref{sec:preliminaries} for \BA and \CL. In
Sec.~\ref{sec:experiment} we describe how the parameter $\w$ for \CL is derived
for given parameter $m_0$ of \BA. In Sec.~\ref{sec:spectrum-bulk} we analyze
similarity of spectral distributions. In Sec.~\ref{sec:extreme-eigenvalues} we
analyze similarity of first, second and last eigenvalue. In
Sec.~\ref{sec:eigenvector} we analyze similarity in principal eigenvectors.

\subsection{The experiment} \label{sec:experiment} Since \CL model has richer
parameter values space, $\w$ parameter is derived on graphs generated by \BA
model. Suppose we fix \BA parameter $m_0$ and the order of graph $n$. Let
$\varepsilon$ by an acceptable deviation for expected degree vector. We start by
generating 300 graphs according to $\mathcal{G}^{\rm BA}_n(m_0)$ and derive
degree vectors $\w^{\rm BA}_{j}$ for $j=1,\dots,300$. We calculate mean degree
vector
\begin{equation}
\overline \w ^{\rm BA}_{1} = \frac{1}{300}\sum_{j=1}^{300}\w^{\rm BA}_{j}.
\end{equation}
Then we generate another 300 graphs and calculate
\begin{equation}
\overline \w ^{\rm BA}_{2} = \frac{1}{600}\sum_{j=1}^{600}\w^{\rm BA}_{j},
\end{equation}
and in general
\begin{equation}
\overline \w ^{\rm BA}_{t} = \frac{1}{300t}\sum_{j=1}^{300t}\w^{\rm BA}_{j}.
\end{equation}
We repeat the process until
\begin{equation}
\| \overline \w ^{\rm BA}_{t} -\overline \w ^{\rm BA}_{t+1} \|_{\infty} \leq \varepsilon.
\end{equation}
We choose $\overline \w ^{\rm BA}_{n,m_0} \coloneqq\overline \w ^{\rm BA}_{t+1}$
to be the parameter for \CL model for given $n$ and $m_0$. Hence we compare
models $\mathcal G_n^{\rm BA}(m_0)$ to $\mathcal G_n^{\rm CL}(\overline \w ^{\rm
	BA}_{n,m_0})$. In our experiment we considered $m_0 =1,\dots,6$ and
$\varepsilon=0.05$. The values of graph orders depends on analyzed spectral
property.

The numerical analysis was performed using Julia language. The graphs were
generated thanks to \texttt{LightGraphs.jl} module \cite{Bromberger17}. The
module implemented the algorithm for \CL generation presented in
\cite{miller2011efficient}. The algorithm scales well for expected degrees much
smaller than the graph order which is true for \BA model \cite{flaxman2005high}

\subsection{Spectral distribution}\label{sec:spectrum-bulk}

\begin{figure}[t]\centering
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}l@{}}
		\includegraphics{pvalue-spectrumbulk-1.eps}&
		\includegraphics{pvalue-spectrumbulk-2.eps}&
		\includegraphics{pvalue-spectrumbulk-3.eps}\\[0em]
		\includegraphics{pvalue-spectrumbulk-4.eps}&
		\includegraphics{pvalue-spectrumbulk-5.eps}&
		\includegraphics{pvalue-spectrumbulk-6.eps}
	\end{tabular}
	\caption{$p$-value of Kolmogorov-Smirnov distribution equality test. Red dashed
	lines refer to critical value $\alpha=0.1$.}\label{fig:spectrum-bulk}
\end{figure}

The experiment goes as follow. For each order $n=1000,1050,\dots,8000$ and
$m_0=1,\dots,6$ we have calculated the spectrum of 200 graphs for each model. We
have paired consecutive spectra and perform a Kolmogorov-Smirnov test for each
pair. By this for each order and $m_0$ value we obtained 200 $p$-values. Our
results are presented in Fig.~\ref{fig:spectrum-bulk}.

We can see, that for $m_0=1,2$ the spectral distributions differ, as for large
graph order the $p$-values converge to 0. While for $m_0=3$ the $p$-value are
close to 1 for small graph orders, we can see that for large $n$ the $p$-values
are more robust. For $m_0>3$ almost all $p$-values are very close to 1.

The $m_0=3$ is a threshold value for spectral distribution similarity between
the models. Below that value, the spectra are almost surely different. We cannot
specify any reliable statement for $m_0=3$, however it seems for sufficiently
`small' graphs the distributions are similar. For larger values of parameters
distributions are similar.

The possible reason of such behavior is that for small values of $m_0$ we obtain
in the case of Chung-Lu model large number of disconnected small graphs. The
greater the $m_0$ is, the smaller is the number of such components. Above the
threshold value $m_0$ disconnected components have marginal impact on the
spectrum hence the models spectra are similar. Because of that we analyzed
principal vectors and extreme eigenvalues only for $m_0=4,5,6$.

\subsection{Extreme eigenvalues}\label{sec:extreme-eigenvalues}

The experiment goes as follow. For each graph order
$n=4000,8000,\dots,100\,000$ and $m_0=4,5,6$ we have calculated first, second
and last eigenvalues of $20,\!000$ graphs. Then we compare empirical
distributions of \BA and \CL model by calculating mean value, and $p$-value of
Kolmogorov-Smirnov for standardized data. By this for each graph order and $m_0$
value we obtained single mean value and $p$-value. Our results are presented in
Fig.~\ref{fig:eigenvalues-mean} and Fig.~\ref{fig:eigenvalues-pvalue}.

As one can see on the Fig.~\ref{fig:eigenvalues-mean} the mean values slightly
differ. While the gap between mean values increases with the graph order growth,
the values are still quite similar. However $p$-values presented in
Fig.~\ref{fig:eigenvalues-pvalue} show that independently of $m_0$ distributions
of first and last eigenvalues differ. For $m_0\leq 4$ this is the case for
second eigenvalue.

Surprisingly, we cannot provide any reliable statement for second eigenvalue for
$m_0=5,6$, as $p$-values appears on both side of $\alpha=0.1$. While most of the $p$-values are above
critical value $\alpha=0.1$, the result are not as evident as in
Sec.~\ref{sec:spectrum-bulk}. Hence we cannot decline the possibility, that
those distributions are similar.
\begin{figure}[t]
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}l@{}}
		\includegraphics{mean-first-4.eps}&
		\includegraphics{mean-second-4.eps}&
		\includegraphics{mean-last-4.eps} \\[0em]

		\includegraphics{mean-first-5.eps}&
		\includegraphics{mean-second-5.eps}&
		\includegraphics{mean-last-5.eps} \\[0em]

		\includegraphics{mean-first-6.eps}&
		\includegraphics{mean-second-6.eps}&
		\includegraphics{mean-last-6.eps}

	\end{tabular}
\caption{Mean value of first, second and last eigenvalues. The black crosses
	correspond to \BA model, while blue dots correspond to \CL model. }\label{fig:eigenvalues-mean}
\end{figure}
\begin{figure}[t]
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}l@{}}
		\includegraphics{pvalue-first-4.eps}&
		\includegraphics{pvalue-second-4.eps}&
		\includegraphics{pvalue-last-4.eps}\\[0em]

		\includegraphics{pvalue-first-5.eps}&
		\includegraphics{pvalue-second-5.eps}&
		\includegraphics{pvalue-last-5.eps}\\[0em]

		\includegraphics{pvalue-first-6.eps}&
		\includegraphics{pvalue-second-6.eps}&
		\includegraphics{pvalue-last-6.eps}
	\end{tabular}
	\caption{$p$-values of standardized eigenvalues data. Red dashed lines refer to
	critical value $\alpha=0.1$.}\label{fig:eigenvalues-pvalue}
\end{figure}
\subsection{Principal eigenvector}\label{sec:eigenvector}

While $p$-value  was a natural choice for eigenvalues and spectral distribution analysis,
this is not the case for eigenvector. For graph of order $n$, $n$-dimensional
variable would be considered. Furthermore, since the length of the vector goes
to infinity, norms cease to be equivalent. Hence, we chose the following measures of
similarity between vectors $\bar \lambda,\bar \kappa$:
\begin{gather}
	\|\bar \lambda -\bar \kappa \|_\infty = \max_{i=1,\dots,n} |\bar{\lambda}_i-\bar{\kappa}_i|,\\
	\|\bar \lambda -\bar \kappa \|_2 = \sqrt{\frac{1}{2}\sum_{i=1}^{n} (\bar{\lambda}_i-\bar{\kappa}_i)^2}.
\end{gather}
The constant $\frac{1}{\sqrt{2}}$ was chosen to bound the possible values to
$[0,1]$. Note that $\|x\|_2\to 0$ implies $\|x\|_\infty \to
0$, hence the first measure is the stronger one.

The choice of eigenvector is in general non-unique, as for
eigenvector $\bar \lambda$ and arbitrary $\varphi\in\R$, vector  $\ee^{\ii\varphi}\bar
\lambda_1$ is proper eigenvector corresponding to the same eigenvalue. However
based on Perron-Frobenius theorem, we choose the unique eigenvector with all
elements nonnegative. Note that in the case of similarity both measures should
converge to 0.

Based on the numerical results presented in Fig.~\ref{fig:eigenvector} this is
not the case. For all $m_0$ values Euclidean distance $\|\cdot\|_2$ is detached from 0.
In the case of infinity norm distance, we observe more robust behavior. There
exist values close to 0, however still for many samples the values are further
from 0. Hence in our opinion it is unlikely for them to be equal as well.
\begin{figure}[t]\centering
	\begin{tabular}{c@{\hspace{-0.1cm}}c}
		\includegraphics{eigv-eucl-4.eps}&
		\includegraphics{eigv-infinity-4.eps}\\[0em]

		\includegraphics{eigv-eucl-5.eps}&
		\includegraphics{eigv-infinity-5.eps}\\[0em]

		\includegraphics{eigv-eucl-6.eps}&
		\includegraphics{eigv-infinity-6.eps}
	\end{tabular}
	\caption{Various similarity measures of principals vector for \BA and \CL
	model. In the case of similarity, both measures should converge to
	0.}\label{fig:eigenvector}
\end{figure}

\section{Application of the results} To demonstrate the possible applications of
our results we consider two examples. In the first one we show that spectral
distribution similarity can be used for derivation of the spectral distribution
formula for \BA model. In the second case we show that the similarities and
differences of eigenvalues and eigenvectors have impact on the quantum spatial
search evolution.

\subsection{Spectral distribution}

\begin{figure}[t]\centering
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}l@{}}
		\includegraphics{degree-distribution-m0-4.eps}&
		\includegraphics{degree-distribution-m0-5.eps}&
		\includegraphics{degree-distribution-m0-6.eps}
	\end{tabular}
	\caption{Expected degree distribution of \BA model. The black line refers the
	analytical formula $2m_0^2/d^3$. The data were constructed as described in
	Sec.~\ref{sec:experiment} for graph order $100,000$.}\label{fig:degree}
\end{figure}

While spectral distributions are known for some models
\cite{nadakuditi_spectra_2013,dorogovtsev2003spectra}, it is not the case of \BA
model. Thanks to our results obtained in Sec.~\ref{sec:spectrum-bulk}, we can
reduce the problem of deriving it to derivation of much simpler Chung-Lu model.
We propose following approach: First, one should shown that the dependence
between edges appearance has no influence on the \BA spectral distribution,
which is numerically confirmed in the paper. Second, using methods suitable for
edge-independent random graphs we may determine the analytical formula for
spectral distribution. The first method requires degree distribution, which is
well known for the \BA model \cite{bollobasdegree}.  The methods proposed by
Dorogovstev et al. \cite{dorogovtsev2003spectra} allow to use this
characteristics for spectral distribution derivation.

The second method proposed by Nadakuditi et al. \cite{nadakuditi_spectra_2013}
requires the distribution of the expected degree. While it is not known for \BA
model, we propose $p:[m_0,\infty)$ such that $p:d\mapsto\frac{2m_0^2}{d^3}$
distribution. The formula fits the histogram very well, furthermore it is well
motivated because of several analytical requirements. First, it is decreasing
function which scales as $p \propto d^{-3}$ \cite{albert2002statistical}.
Second, $\mathbb E p(d) = 2m_0$, which coincide with the mean degree for the
model.

\subsection{Quantum spatial search} \label{sec:qss-application}

\begin{figure}[t]\centering
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}l@{}}
		\includegraphics{qss_eff_7.eps}&
		\includegraphics{qss_eff_10.eps}&
		\includegraphics{qss_eff_20.eps}
	\end{tabular}
	\caption{The optimal measurement times and probability success for \BA and \CL
	models. Dashed orange represent a success probability for single \CL graph.
	Blue line represent a success probability change for single \BA graph. Red
	crosses (black dots) represent an optimal measurement time for \CL graphs (\BA
	graphs). The procedure of deriving optimal measurement time are described in
	Sec.~\ref{sec:qss-application}  }\label{fig:qss}
\end{figure}

\begin{figure}[t]\centering
	\begin{tabular}{@{}l@{\!\!\!}l@{\!\!\!\!}@{}}
		\includegraphics{scaling_BA.eps} &
		\includegraphics{scaling_CL.eps}
	\end{tabular}
	\caption{The minimal expected time $(t+0.2\log(n))/p(t)$ for \BA and \CL model. The red line is a regression line of logarithm of expected time vs logarithm of graph order. It describes the time complexity of the quantum search, as tangent $\alpha$ implies the complexity is $\Theta(n^\alpha)$. For \BA model its tangent equals $\alpha\approx0.56$, while for \CL it is $\alpha\approx 0.53$}\label{fig:qss-scaling}
\end{figure}

The second example is motivated by the fact, that extreme eigenvalues and
principal eigenvector play important role in quantum spatial search efficiency
\cite{chakraborty2016spatial,glos2018vertices}. Let
\begin{equation}
H = -t(\gamma A + \proj{\omega})
\end{equation}
be a Hamiltonian describing continuous-time quantum spatial search
\cite{childs2004spatial}. Here $A$ denotes adjacency matrix of a graph and
$\proj{\omega}$ is an oracle of marked vertex, and $t$ denotes evolution time.
Jumping rate $\gamma$ is chosen to be $\frac{1}{\lambda_1(A)}$. After time $t$ a
measurement in computational basis is made in order to derive $\omega$. It was
shown, that large gap between largest eigenvalue and the maximum of absolute
values of second and last eigenvalue implies optimal $\sqrt n$ time of quantum
evolution \cite{chakraborty2016spatial}. While the result applies only to
regular graphs, the results from \cite{glos2018vertices} suggests this may
depend mostly on the overlap between the principal eigenvector and the subspace
corresponding to marked element.

We have designed experiment as follows. We made an evolution of quantum spatial
search on 1800 graphs from $\mathcal G_{100\,000}^{BA}(6)$ and 1800 graphs from
$\mathcal G_{100\,000}^{CL}(\bar {\mathbf{w}}^{BA}_{100\,000,6})$. The evolution
was made for marked nodes 7, 10 and 20. For marked nodes 7 and 10 we determined
the success probability for times $0,0.1,\dots,15$, while for marked node 20 we
have chosen times $0,0.1\dots, 25$. Then we chose the time, for which the
success probability $p_{\rm opt}$ is the first greatest probability, for which
all of the probabilities $p_t$ for larger evolution time satisfies $(p_t-p_{\rm
	opt})/p_t <0.2$. This prevents from choosing success probability too far from $t=0$,
which would result in not necessarily optimal quantum spatial search evolution.
For simulation purposes we used the Julia language together with \texttt{QuantumWalk.jl} package \cite{glos2018quantumwalkjl}.

The results are presented in Fig.~\ref{fig:qss}. We can observe that there are
regimes, in which the success probabilities are similar for both models for each
marked nodes. However, the greater the index of node is, the more robust results
are observed. We claim that the observed behavior can be explained by the
difference in the principal eigenvector convergence presented in
Sec.~\ref{sec:eigenvector}.

The results is stable with graph order change. For each graph order $n=2000, 4000,\ldots, 100,000$ we
have sampled 10 graphs for each model and calculated the optimal expected time for
quantum search with marked $(m_0+1)$th node. We have calculated the success probability
$p(t)$ for times $t=0,0.01\pi\sqrt{n},\ldots,\pi\sqrt{n}$ and we have chosen
time $t_{\rm opt}$ minimizing the expected time
$(t_{\rm opt} +0.1\log(n))/p(t)$. The approach was used already for analyzing
the quantum attack \cite{glos2018impact}. The results are presented in
Fig.~\ref{fig:qss-scaling}. We can see that the optimal expected time is similar
for both models. The same effect can be observed for scaling, as the calculated
complexity is $\Theta(n^{0.56})$ for \BA model and $\Theta(n^{0.53})$ for \CL
model. This confirms that the similarity of the quantum spatial search behavior
scales with graphs order.

\section{Conclusion and discussion} \label{sec:conclusion}

In the paper we analyzed the spectral similarity between \BA model and \CL
model. Our analysis includes the similarity of distribution of spectral
distribution, extreme eigenvalues and principal eigenvector.

Calculations show that $m_0=3$ is threshold value for the spectral
distributions similarity. The models may have similar spectral distributions for
$m_0>3$ and different distributions for $m_0<3$. Contrary the extreme
eigenvalues seems not to be similar. In particular for all considered values of
$m_0$, first and last eigenvalues of those models differ. Still we cannot
provide any reliable hypothesis for $m_0=5,6$.

For principal vectors we have proposed Euclidean and uniform norm distance
similarity measures. In the first case for analyzed values of $m_0$ the
principal vector differs, as the distance was detached from 0. We cannot provide
such strong statement for the infinity norm measure, due to robustness of
obtained values. We have made similar analysis for extreme eigenvalues, here the
eigenvalues are roughly the same. Still the distributions differ at least for
largest and smallest eigenvalues.

We have proposed applications of our results in graph spectral theory and
quantum spatial search. In the first case we proposed a method for deriving
analytical formula for spectral distribution of quantum spatial search. In the
second we have shown, that robustness of convergence of principal eigenvector
has impact on the quantum spatial search optimal measurement time. Still, for
 vertices with large degree the results are similar for both models. As a future research one can consider extending the results into other quantum walks problems like quantum transport \cite{mulken2011continuous}.

\paragraph{Acknowledgements} The author would like to thank Łukasz Pawela,
Zbigniew Puchała and Jarosław Adam Miszczak for discussion. Furthermore the
author would like to thank Izabela Miszczak and Jarosław Adam Miszczak for
reviewing the article. This research was supported in part by PL-Grid
Infrastructure. The work was carried out within the statutory research project of the Institute of Informatics, BKM.

\bibliographystyle{ieeetr}
\bibliography{random-graph-spectrum-comparison}

\end{document}

config: arxiv


TITLE: Understanding calculations of log/antilog tables of polynomials over finite field
QUESTION [1 upvotes]: I'm learning about finite fields and I came across this example online: http://www.csee.umbc.edu/~lomonaco/s12/443/handouts/Log-Antilog-Calculation.pdf
I'm having trouble understanding what exactly log/antilog tables are used for, and how the calculations are being done in this example. I'm guessing since it's GF(2^4) = GF(16) so there's 16 entries and the highest exponent is 4 which means I have to use at most E^4 in the calculations (I can't get that symbol correctly displayed here, using E for now).
So what exactly are the uses for these tables and how do the calculations work?
Edit: link didn't work, example pic below.

REPLY [1 votes]: How to use a log table? Oldsters like me know that if you want to multiply two quantities, like $\xi^3+\xi^2$ and $\xi^4+\xi^3+\xi^2+\xi$ in $\Bbb F_{16}$, you look up their logarithms, to find $6$ and $13$. Then add the logarithms modulo $15$ to get $4$. The quantity whose log is $4$ is $\xi+1$, and that’s your product.
To divide, subtract the logarithms, modulo $15$.


TITLE: Doubt in this question involving logarithm
QUESTION [1 upvotes]: If $\log2= 0.301$, then how many number of digits are in $2^{64}$?
What I did:
$$\log(2)^{64}=\log2^{64}=64\log2=64\log2=19.264$$
Number of digits comes out to be $5$. But answer is $20$? I have written $\log 2$ raise to the power $64$

REPLY [0 votes]: See that $100 = 10^2$ and $1000 = 10^3$ and so on.  The number of digits in both those numbers is one more than the exponent on $10$.  If we write any 3-digit number as a power of 10, then the exponent will be between $2$ and $3$.  For instance,  $423 = 10^{2.6263\ldots},$  where, of course $2.6263\ldots$ is the base-10 log of $423.$
Using this principle we can do this:
$$2^{64}= \left(10^{\log 2}\right)^{64} = 10^{64\log } = 10^{19.26\ldots}. $$
So we know the number has 20 digits.