text:
In this part of the appendix, we review the behaviour of classical clocks, showing that reset clocks (those with a fixed state after ticking) can reach the highest accuracy, and that, for a classical clock of dimension $d$, the accuracy is upper bound by its dimension. Finally, we discuss a simple classical clock that saturates this bound.

In fact, the dynamics of classical clocks, at least those that are self-contained, is a subset of more general \textit{Markovian dynamics}, described by the Kolmogorov equation\cite{kolmo}. The ticks of a finite-dimensional clock may be understood as a sequence of events generated by Markovian dynamics on a finite-dimensional vector space. As such, we have included Appendix \ref{app:markovianpart} that introduces the mathematics of Markovian sequences that we require to prove our main results on clocks. Furthermore, we will draw on some lemmas on the behaviour of the accuracy of mixtures and sequences of delay functions, which are covered in Appendix \ref{app:delayfunction} (where delay functions and the accuracy $R$ are discussed).

Appendices \ref{app:delayfunction} and \ref{app:markoviandynamics} derive from standard theory on stochastic process and random variables, and are included here to place clocks within the larger context of the theory of stochastic processes, and for ease of reading and understanding of the proofs of our main results, which rely on multiple lemmas within this theory. For an in depth discussion on stochastic processes, see for example \cite{probability}.

In Appendix \ref{app:classicalclocks}, we introduce classical clocks and they were discussed in the main text, and relate them to Markovian sequences. Reset clocks, those that tick to a fixed state, are discussed and shown to be the same as independent Markovian sequences.

In Appendix \ref{app:resetclockaccuracy}, we first apply Theorem \ref{theorem:markovianaccuracy} to clocks to obtain our first result on clocks, that for every classical clock, there is a reset clock of at least as high accuracy. Furthermore, in Appendix \ref{sec:justifyR}, by focusing on the accuracy of reset clocks, we find that the quantity $R$ that we have denoted as the accuracy is in fact a good quantifier of how long the clock can run before being in error.

Our final result on classical clocks, that their accuracy $R$ is upper bound by their dimension, is stated and proven in Appendix \ref{app:upperbound}.

\subsection{Classical clocks}\label{app:classicalclocks}

\begin{definition}\label{def:c-clock}

As discussed in the main text (Section \ref{sec:classicalspecialcase}, a \textbf{self-contained stochastic finite-dimensional classical clock}, or for simplicity, a \textbf{classical clock}, is represented by a time-dependent vector $V(t) \in \mathbb{R}^d$, that represents the state of the clock, such that $V(0)$ is a population vector (Def. \ref{def:popvector}), together with a pair of time-independent stochastic generators $\{\notickmatrix, \tickmatrix\}$ (Def. \ref{def:stochasticgenerators}), that generate the dynamics of the clock via the relation
\begin{align}\label{eq:clockstate}
	\frac{d}{dt} V(t) &= \left( \notickmatrix + \tickmatrix \right) V(t),
\end{align}
and where the probability per unit time of a tick being observed, that we label the ``tick density" and denote by $p_{tick}(t)$, is given by
\begin{align}\label{eq:tickdensity}
	p_{tick}(t) &= \onenorm{\tickmatrix V(t)}.
\end{align}

\end{definition}

\begin{remark}

The clock is \textbf{self-contained} because its generators are time-independent, and \textbf{finite-dimensional} as the vector space of clock states is taken to be finite dimensional. Finally, the clock is \textbf{stochastic/classical}, as the states are population vectors evolving under stochastic generators, which is equivalent, in the context of quantum theory, to restricting the initial state to be diagonal in some preferred basis, and restricting the dynamical generators to Lindbladian operators that keep the states diagonal in the same basis, as discussed in Section \ref{sec:classicalspecialcase} of the main text.

In the entirety of this work, we only consider self-contained and finite-dimensional clocks. For simplicity, we continue for the remainder of this appendix by shortening the term to simply \textbf{classical clocks}, with the implicit understanding that they are also self-contained, and finite-dimensional, and that the term classical implies stochastic.

\end{remark}

\begin{remark}

In the context of classical clocks, since $\tickmatrix$ is associated to the generation of ticks, we shall refer to it as the \textbf{tick generator}, and to $\notickmatrix$ as the \textbf{non-tick generator}.

\end{remark}

\subsubsection{Tick-states and tick delay functions}

The state $V(t)$ and tick density $p_{tick}(t)$ in the above description of classical clocks (Def. \ref{def:c-clock}) do not contain any information about how many times the clock has already ticked in the past. In order to distinguish between each tick, one can split the state into a sequence $\{V^{(n)}\}$ of ``tick-states", each corresponding to a fixed number of ticks.

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

The \textbf{tick-states} of a classical clock (Def. \ref{def:c-clock} are a sequence of states $\{V^{(n)}(t)\}$, $n \in \{0,1,2,...\}$, where the initial conditions and dynamics for each state in the sequence are determined w.r.t. the pair of stochastic generators $\{\notickmatrix,\tickmatrix\}$ of the clock as
\begin{subequations}\label{eq:tickstates}
\begin{align}
	\quad V^{(n)}(0) &= \begin{cases}
			V(0) & \text{for $n=0$}, \\
			0 & \text{for $n>0$}.
		\end{cases}, \label{eq:tickstateinitial}\\
	\text{and} \quad \frac{d}{dt} V^{(n)}(t) &= \begin{cases}
			\notickmatrix V_0(t) & \text{for $n=0$}, \\
			\notickmatrix V^{(n)}(t) + \tickmatrix V^{(n-1)}(t) & \text{for $n>0$}.
		\end{cases} \label{eq:tickstatedynamics}
\end{align}
\end{subequations}

\end{definition}

\begin{remark}

The choice of initial conditions (Eq. \ref{eq:tickstateinitial}) corresponds to the fact that the clock has not ticked yet, and thus the entire state of the clock is associated with $V^{(0)}$, the state corresponding to no ticks.

For $t>0$, in every infinitesimal time interval, the tick generator moves probability from a state in the sequence to the next, while the non-tick generator keeps the probability within the same tick subspace (albeit moving it around, and possibly decreasing it). Thus each $V^{(n)}(t)$ evolves due to only two contributions: firstly, its own evolution, as $\notickmatrix V^{(n)}(t)$, and because of a tick, from $\tickmatrix V^{(n-1)}(t)$.

\end{remark}

In an analogous manner to the state, one can split the tick density (Eq. \ref{eq:tickdensity}) of the clock into the contributions of the first, second, and following ticks.

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

We define the \textbf{tick delay function} of the $n^{th}$ tick to be
\begin{align}\label{eq:tickdelayfunction}
	\tau^{(n)}(t) &= \onenorm{\tickmatrix V^{(n-1)}(t)}.
\end{align}

\end{definition}

\begin{remark}

The expression for the $n^{th}$ tick delay function reflects the fact that the $n^{th}$ tick can only occur after $n-1$ ticks, and the corresponding state of the clock is $V^{(n-1)}(t)$.

\end{remark}

\begin{remark}

By construction, the tick-states (Def. \ref{def:tickstates} and the tick delay functions (Def. \ref{def:tickdelay}) of a classical clock form a Markovian sequence of events (Def. \ref{def:markoviansequence}). In the case of clocks however, the dynamics of every event (tick) is identical to the previous one, featuring the same pair of generators on the same vector space.

\end{remark}

\subsubsection{Reset clocks}

In our discussion on Markovian sequences of events, it was useful to discuss independent Markovian sequences (Def. \ref{def:independentsequence}), those that had fixed states following the occurrence of each event. The equivalent for clocks is a ``reset clock", which we now characterize.

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

A \textbf{classical reset clock}, (in this appendix simply a \textbf{reset clock}), is a classical clock (Def. \ref{def:c-clock}) for which the event of ticking always causes the clock to return to a fixed state which is also the initial state, i.e.
\begin{align}\label{eq:resetdefinition}
	\tickmatrix V \propto V(0) \quad \forall V \in \mathbb{R}^d.
\end{align}
Equivalently, a reset clock is one for which the tick generator $\tickmatrix$ is a rank-1 operator, all of whose columns are proportional to the initial state $V(0)$.

\end{definition}

\begin{remark}

By definition, the tick-states and tick delay functions of a reset clock form an independent Markovian sequence of events, Def. \ref{def:independentsequence}. Since the events in the case of clocks are ticks, and the dynamics of each tick is generated identically to all the others, the ticks of a reset clock correspond to an \textit{i.i.d.} sequence, i.e. a sequence of independent and identically distributed events \cite{probability}.

\end{remark}

\subsection{The accuracy of reset clocks}\label{app:resetclockaccuracy}

\subsubsection{The accuracy $R$ quantifies the average run-time of reset clocks}\label{sec:justifyR}

If we apply Lemma \ref{lemma:resetsequenceconvolution} to the case of reset clocks (Def. \ref{def:resetclock}), we find that the delay function of the $n^{th}$ tick of the clock is given by the $n$-fold convolution of the delay function of the first tick,
\begin{align}
	\tau^{(n)}(t) &= \left( \tau_1 \conv \tau_1 \conv... \conv \tau_1 \right) (t).
\end{align}

If we denote the zeroth moment, first moment, second moment, variance and accuracy (Defs. \ref{def:delayfunctionmoments}, \ref{def:accuracydelayfunction}) of a single tick of a reset clock (i.e. the delay function of a single tick) by $Q,\mu,\chi,\sigma,R$ respectively, and those of the $n^{th}$ tick by $Q^{(n)},\mu^{(n)},\chi^{(n)},\sigma^{(n)},R^{(n)}$, we find from the application of Eq. \ref{eq:sequencemoments} for the moments of a convolution of delay functions, and Eq. \ref{eq:accuracygamma} for the accuracy of a delay function, that
\begin{align}\label{eq:resetmomentscaling}
	\left\{ \begin{array}{c}
		Q^{(n)} \\
		\mu^{(n)} \\
		\chi^{(n)} \\
		\sigma^{(n)} \\
		R^{(n)}
	\end{array} \right\} &=
	\left\{ \begin{array}{c}
		Q^n \\
		n \mu \\
		n \chi + n(n-1) \mu^2 \\
		\sqrt{n} \cdot \sigma \\
		n R
	\end{array} \right\}.
\end{align}

Consider that one asks the question \textit{``How many ticks can the clock produce until the uncertainty in the time of occurrence of the next tick has grown to be equal to the time interval between ticks?"}, which is a universally accepted mark of a clock's accuracy.

For reset clocks, the average time interval between ticks is $\mu^{(n)} - \mu^{(n-1)} = \mu$,  and is independent of which tick we are at. On the other hand, the uncertainty in the time of occurrence of the $n^{th}$ tick, $\sigma^{(n)} = \sqrt{n} \sigma$, grows with the number of ticks. If we denote the average number of ticks before the uncertainty equals the interval between ticks as $N$,
\begin{align}
	\sigma^{(n)} &= \mu^{(n)} - \mu^{(n-1)} \\
	\therefore \; \sqrt{N} \sigma &= \mu \\
	\therefore \; N &= \frac{\mu^2}{\sigma^2} = R.
\end{align}

\subsubsection{Result: The accuracy of all classical clocks is bound by that of reset classical clocks}

\begin{theorem}\label{theorem:resetclockaccuracy}

For every classical clock (Def. \ref{def:c-clock}), there exists a reset clock (Def. \ref{def:resetclock}) of the same dimension such that the accuracies of the delay functions of every tick of the original clock are upper bounded by the corresponding accuracies of the reset clock. Furthermore, such a reset clock can be obtained from the original clock by
\begin{itemize}
	\item picking a single well chosen canonical state to be the initial state,
	\item setting all but one of the rows of the tick generator $\tickmatrix$ to be zero, and shifting the single non-zero row to the location corresponding to the initial canonical state.
\end{itemize}

\end{theorem}

\begin{proof}

The theorem follows from the direct application of Theorem \ref{theorem:markovianaccuracy} to the case of classical clocks, when one identifies the tick-states (Def.  \ref{def:tickstates}) and tick delay functions (Def. \ref{def:tickdelay}) as a Markovian sequence of events (Def. \ref{def:markoviansequence}), while those of a reset clock (Def. \ref{def:resetclock}) are an independent Markovian sequence (Def. \ref{def:independentsequence}).

\end{proof}

\subsection{An upper bound on the accuracy of classical clocks}\label{app:upperbound}

\begin{theorem}\label{theorem:classicalclockaccuracy}

For a classical clock of dimension $d$ (Def. \ref{def:c-clock}), where $d \in \mathbb{N}^+$, the accuracy of its $n^{th}$ tick, i.e. the accuracy $R$ (Def. \ref{def:accuracydelayfunction}) of the delay function of the $n^{th}$ tick (Def. \ref{def:tickdelay}), is upper bound by
\begin{align}
	R\left[ \tau^{(n)} \right] \leq n d,
\end{align}

In particular, for reset clocks of dimension $d$, which upper bound the accuracies of the ticks of arbitrary $d$-dimensional clocks (see Theorem \ref{theorem:resetclockaccuracy}), the accuracy of every single tick w.r.t. the previous one is upper bound by
\begin{align}
	R \left[ \tau \right] \leq d,
\end{align}
which, as discussed in Sec. \ref{sec:justifyR}, is a quantifier for the number of ticks outputted before the clock is expected to fail.

\end{theorem}

\textbf{Proof.} The rest of this section is dedicated to the proof of Theorem \ref{theorem:classicalclockaccuracy}. We prove the theorem by fixing the dimension $d$ and optimizing the accuracy over classical clocks of that dimension. From Theorem \ref{theorem:resetclockaccuracy}, we know that the accuracies of the ticks of any clock are upper bound by that of at least one reset clock with a canonical initial (and reset) state, and thus we may restrict our optimization to the case of reset clocks of dimension $d$ whose initial and reset state is the same canonical state.

Furthermore, as discussed in Sec. \ref{sec:justifyR}, the accuracy of the $n^{th}$ tick of a reset clock is simply $n$ times the accuracy of the first tick, and the delay functions of every tick w.r.t. the time of occurrence of the previous tick are identical to each other, and equal to the delay function of the first tick.

Thus the quantity we are left to optimize is simply the accuracy of the first tick, and the restricted set we optimize over is that of reset clocks with a canonical initial state, and a canonical tick generator chosen so that the reset state is the initial state.

More precisely, we work in a $d$-dimensional real vector space, spanned by the canonical basis $\mathbf{e}_i$, where $i \in \{0,1,...,d-1\}$. Since the initial and reset state must be a canonical state, we label this as $\mathbf{e}_0$ without loss of generality. Thus the tick generator $\tickmatrix$ has only one non-zero row, i.e. its first row, that corresponds to $\mathbf{e}_0$. On the other hand, the non-tick generator $\notickmatrix$ is arbitrary. The state and corresponding delay function of a single tick of the clock are thus
\begin{subequations}\label{eq:singletickstatedelay}
\begin{align}
	V(t) &= e^{\notickmatrix t} \mathbf{e}_0, \\
	\tau(t) &= \onenorm{ \tickmatrix e^{\notickmatrix t} \mathbf{e}_0 }.
\end{align}
\end{subequations}

To prove that the accuracy of the above delay function is bounded by the dimension $d$ for all $d \in \mathbb{N}^+$, we employ the method of induction, starting with the case $d=1$. In this case, both $\notickmatrix$ and $\tickmatrix$ are real  numbers, that we label $\notickmatrix = -p$ and $\tickmatrix = g$ respectively, where $p\geq g > 0$ in order to ensure that $\{\notickmatrix,\tickmatrix\}$ are a pair of stochastic generators (Def. \ref{def:stochasticgenerators}). The delay function is thus
\begin{align}
	\tau(t) &= g e^{-pt}.
\end{align}

One can calculate all of the moments (Def. \ref{def:delayfunctionmoments}) explicitly,
\begin{align}
	Q &= \braket{t^0} = \frac{g}{p} \\
	\mu &= \frac{\braket{t^1}}{Q} = \frac{1}{p} \\
	\chi &= \frac{\braket{t^2}}{Q} = \frac{2}{p^2},
\end{align}
from which the $\gamma$-value (Eq. \ref{eq:accuracygamma}) is $\gamma = \chi/\mu^2 = 2$, and the accuracy is
\begin{align}
	R \left[ \tau \right] &= \frac{1}{\gamma - 1} = 1,
\end{align}
which satisfies the statement of the theorem.

We continue by assuming the theorem applies for dimensions $\{1,2,...,d-1\}$, and prove that it applies to a $d$-dimensional clock.

The rest of the proof is structured as follows. In Sec. \ref{proof:splitdimension}, we divide the $d$ dimensional vector space of the clock into two subspaces, a one-dimensional space corresponding to the initial (canonical) state, and the complementary $d-1$ dimensional space, and define sequences of states and delay functions that correspond to this division. In Sec. \ref{proof:sequenceproperties}, we prove that we can recover the dynamics of the state $V(t)$ and the delay function $\tau(t)$ of a single tick from these defined sequences. In Sec. \ref{proof:delayexplicit}, we calculate the moments of the delay function $\tau(t)$ explicitly using the defined sequences, and upper bound the accuracy of $\tau(t)$.

\subsubsection{Dividing the vector space of the clock into a sum of one-dimensional and $d-1$ dimensional spaces}\label{proof:splitdimension}

In order to use the result for $d-1$ dimensional clocks, we divide the $d$-dimensional space of states into the direct sum of two subspaces, firstly, the one-dimensional space corresponding to the initial state $\mathbf{e}_0$, that we label $S_0$, and its complement, that is spanned by the rest of the canonical basis, that we label $S_1$. Thus $S_0$ is one-dimensional, while $S_1$ is $d-1$ dimensional. We denote the projectors onto these spaces as $\Pi_0$ and $\Pi_1$. In matrix form w.r.t. the canonical basis, these projectors are
\begin{align}
	\Pi_0 &= 	\left( \begin{array}{c|ccc}
	1 & & \mathbf{0} &\\
	\hline & & &\\
	\mathbf{0} & & \mathbf{0} & \\
	& & &
	\end{array} \right), &
	\Pi_1 &= 	\left( \begin{array}{c|ccc}
	0 & & \mathbf{0} &\\
	\hline & & &\\
	\mathbf{0} & & \mathds{1}_{d-1} & \\
	& & &
	\end{array} \right),
\end{align}
where $\mathds{1}_{d-1}$ represents the identity operator on a $d-1$ dimensional real vector space. Note that $\Pi_0 + \Pi_1 = \mathds{1}_d$, corresponding to $S_0 \oplus S_1 = \mathbb{R}^d$.

One may split the non-tick generator $\notickmatrix$ into the corresponding sum of four matrices, w.r.t. the subspaces $S_0$ and $S_1$,
\begin{subequations}\label{eq:spacegenerators}
\begin{align}
	\notickmatrix &= \left( \Pi_0 + \Pi_1 \right) \notickmatrix \left( \Pi_0 + \Pi_1 \right) \\
	&= \notickmatrix_{00} + \notickmatrix_{01} + \notickmatrix_{10} + \notickmatrix_{11}, \\
	\text{where} \quad \notickmatrix_{xy} &= \Pi_x \; \notickmatrix \; \Pi_y.
\end{align}
\end{subequations}

Visually, this corresponds to the expressing $\notickmatrix$ w.r.t. the canonical basis as
\begin{align}\label{eq:generatorvisual}
\notickmatrix &\equiv \quad \left( \begin{array}{c|ccc}
\star & & \mathbf{0} &\\
\hline & & &\\
\mathbf{0} & & \mathbf{0} & \\
& & &
\end{array} \right)
\quad + \quad \left( \begin{array}{c|ccc}
0 & & \star &\\
\hline & & &\\
\mathbf{0} & & \mathbf{0} & \\
& & &
\end{array} \right)
\quad + \quad \left( \begin{array}{c|ccc}
0 & & \mathbf{0} &\\
\hline & & &\\
\star & & \mathbf{0} & \\
& & &
\end{array} \right)
\quad + \quad \left( \begin{array}{c|ccc}
0 & & \mathbf{0} &\\
\hline & & &\\
\mathbf{0} & & \star & \\
& & &
\end{array} \right),
\end{align}
where $\star$ denote the original elements, and the matrices above are respectively $\notickmatrix_{00},\notickmatrix_{01},\notickmatrix_{10}\notickmatrix_{11}$.

One may understand each of the above generators $\notickmatrix_{xy}$ as the part of the non-tick generator that is responsible for moving the state \emph{from} the subspace $S_y$ \emph{into} the subspace $S_x$. More precisely, given the state of the clock at some time is $V(t)$, the part of the state that is in the subspace $S_y$ is given by the projection $\Pi_y V(t)$. On this part of the state, the infinitesimal change generated by the non-tick generator is $\notickmatrix \Pi_y V(t)$. Finally, the part of this infinitesimal state-change that is in the space $S_x$ is the projection $\Pi_x \notickmatrix \Pi_y V(t)$.

We follow the same procedure for the tick generator $\tickmatrix$. However, $\tickmatrix$ only takes states to the reset state $\mathbf{e}_0$, i.e. for all $V \in \mathbb{R}^d$,
\begin{align}
	\tickmatrix V \propto \mathbf{e}_0 \quad \Longleftrightarrow \quad \tickmatrix V \in S_0 \quad \Longleftrightarrow \quad \Pi_1 \tickmatrix = 0,
\end{align}
and thus
\begin{align}\label{eq:spacetickers}
	\tickmatrix &= \tickmatrix_{00} + \tickmatrix_{01}, \\
	\text{where} \quad \tickmatrix_{xy} &= \Pi_x \; \tickmatrix \; \Pi_y, \\
	\text{and} \quad \tickmatrix_{10} &= \tickmatrix_{11} = 0.
\end{align}

At this point, we have split both of the generators into components that describe the movement of the state within and between the subspaces $S_0$ and $S_1$. We proceed to do the same for the state of the clock, and construct an independent Markovian sequence of states and corresponding delay functions that does this. Each state in the sequence must be distinguished by two indices, first, an $x \in \{0,1\}$ to denote that the state belongs to $S_x$, and $n \in \mathbb{N}^0 = \{0,1,2,...\}$ to mean that the state corresponds to population having moved from the initial state $\mathbf{e}_0 \in S_0$ to the space $S_1$ and back $n$ times.

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

We define the set of \textbf{path-specific clock states} $v_{n,x}(t)$, where $n \in \{0,1,2,...\}$ and $x \in \{0,1\}$, by the initial conditions
\begin{align}\label{eq:spacestateinitial}
	v_{n,x} (0) &= \begin{cases}
		\mathbf{e}_0 & \text{if $n=x=0$}, \\
		\mathbf{0} &\text{otherwise},
	\end{cases},
\end{align}
and the dynamics
\begin{align}\label{eq:spacestatedynamics}
	\frac{d}{dt} v_{n,x}(t) &= \begin{cases}
		\notickmatrix_{00} v_{0,0}(t) &\text{if $n=x=0$}, \\
		\notickmatrix_{xx} v_{n,x}(t) + \notickmatrix_{x\bar{x}} v_{n-\bar{x},\bar{x}}(t), &\text{otherwise}.
		\end{cases}
\end{align}
where $\bar{x} = x \oplus 1$ is the complement of $x$.

\end{definition}

\begin{remark}

Roughly speaking, $v_{n,x}(t)$ is the part of the state of the clock (of the first tick) corresponding to being in the subspace $S_x$ and having gone from $S_0$ to $S_1$ and back $n$ times.

\end{remark}

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

We define the set of \textbf{path-specific delay functions}
$\xi_{n,x}(t)$, where $n \in \{0,1,2,...\}$ and $x \in \{0,1\}$, barring $n=x=0$, by
\begin{align}
	\xi_{n,x}(t) &= \onenorm{\notickmatrix_{x\bar{x}} v_{n-\bar{x},\bar{x}}(t)},
\end{align}

\end{definition}

\begin{remark}

$\xi_{n,x}(t)$ refers to the delay function of arriving at the $\{n,x\}$ state $v_{n,x}$ at time $t$.

\end{remark}

In anticipation of dividing the delay function of a single tick of the clock using the above sequences, we define the following ``component delay functions".

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

We define the set of \textbf{component delay functions} $\tau_{n,x}(t)$, where $n \in \{0,1,2,...\}$ and $x \in \{0,1\}$, barring $n=x=0$, by
\begin{align}
	\tau_{n,x}(t) &= \onenorm{ \tickmatrix_{0\bar{x}} v_{n-\bar{x},\bar{x}}(t) }.
\end{align}

\end{definition}

\begin{remark}

The term ``delay function" (Def. \ref{def:delayfunction}) for the above is appropriate. We will shortly show that the $v_{n,x}(t)$ are an independent Markovian sequence of states, and the event generator $\tickmatrix_{x\bar{x}}$, taken together with $\notickmatrix_{\bar{x}\bar{x}}$, which is the relevant non-event generator for the state $v_{n-\bar{x},\bar{x}}(t)$, form a pair of stochastic generators $\{\notickmatrix_{\bar{x}\bar{x}},\tickmatrix_{x\bar{x}}\}$ (Def. \ref{def:stochasticgenerators}). From Corollary \ref{cor:validdelayfunction}, we conclude that the $\tau_{n,x}(t)$ are delay functions.

\end{remark}

Finally, as we will eventually prove, the sequences above are found to involve repetitive convolutions of a small set of delay functions, which we proceed to define.

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

We define the pair of \textbf{path-generating reset states} $\mathbf{u}_x$, where $x \in \{0,1\}$ in the following manner. $\mathbf{u}_0 = \mathbf{e}_0$, and $\mathbf{u}_1$ is constructed by taking the single non-zero column of $\notickmatrix_{10}$ (Eq. \ref{eq:generatorvisual}), and normalising it.

\end{definition}

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

We define the pair of \textbf{path-generating delay functions} $\Theta_x$, where $x \in \{0,1\}$ by
\begin{align}
	\Theta_x &= \onenorm{ \notickmatrix_{x\bar{x}} e^{\notickmatrix_{\bar{x}\bar{x}} t} \mathbf{u}_{\bar{x}} },
\end{align}
where $\mathbf{u}_x$, are the path-generating reset states (Def. \ref{def:spaceresetstates}).

\end{definition}

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

We define the pair of \textbf{tick-generating delay functions} $\Gamma_x$, where $x \in \{0,1\}$ by
\begin{align}
	\Gamma_x &= \onenorm{ \tickmatrix_{0\bar{x}} e^{\notickmatrix_{\bar{x}\bar{x}} t} \mathbf{u}_{\bar{x}} },
\end{align}
where $\mathbf{u}_x$, are the path-generating reset states (Def. \ref{def:spaceresetstates}).

\end{definition}

\begin{remark}

Put very simply, $\Theta_x$ is the delay function of the event of moving from $S_{\bar{x}}$ to $S_x$, while $\Gamma_x$ is the delay function of ticking from the subspace $S_{\bar{x}}$.

\end{remark}

\begin{remark}

The above two definitions are justified in using the terminology ``delay function" as both the pair $\{\notickmatrix_{\bar{x}\bar{x}},\notickmatrix_{x\bar{x}}\}$ as well as the pair $\{\notickmatrix_{\bar{x}\bar{x}},\tickmatrix_{x\bar{x}}\}$ can be proven to be pairs of stochastic generators, and from Corollary \ref{cor:validdelayfunction}, it follows that the $\Theta_x$ and $\Gamma_x$ defined above satisfy the requirements of a delay function (Def. \ref{def:delayfunction}).

\end{remark}

\subsubsection{Proving the necessary properties of the path-specific states and delay functions.}\label{proof:sequenceproperties}

\begin{lemma}\label{lemma:pathmarkoviansequence}

The set of path-specific clock states (Def. \ref{def:pathstates}) and delay functions (Def. \ref{def:pathdensities}) form an independent Markovian sequence of events (Defs. \ref{def:markoviansequence}, \ref{def:independentsequence}) w.r.t. the ordering where the event $\{n,x\}$ is followed by $\{n+x,\bar{x}\}$, corresponding to $\{ \{0,0\}, \{0,1\}, \{1,0\}, \{1,1\}, \{2,0\}, \{2,1\}, \{3,0\}, ... \}$; and via the identification of $\{\notickmatrix_{xx},\notickmatrix_{\bar{x}x}\}$ as the pair of event and non-event stochastic generators for the event $\{n,x\}$.

Furthermore, the state $v_{n,x}(t) \in S_x$ for all $t \geq 0$, i.e.
\begin{align}
	\Pi_0 v_{n,0}(t) &= v_{n,0}(t) \quad \text{and} \quad \Pi_1 v_{n,1}(t) = v_{n,1}(t) \quad \text{and} \quad \Pi_0 v_{n,1}(t) = \Pi_1 v_{n,0}(t) = \mathbf{0}.
\end{align}

\end{lemma}

\begin{proof}

Following the definition of a Markovian sequence of events, Def. \ref{def:markoviansequence}, we note that the definition of the initial states in the sequence satisfy the definition by construction. In addition, we require the pairs of event generators for each event in the sequence, $\{\notickmatrix_{xx},\notickmatrix_{\bar{x}x}\}$ to be a pair of stochastic generators, Def. \ref{def:stochasticgenerators}.

First off, to prove that $\notickmatrix_{xx}$ is a non-event generator, note that since $\notickmatrix_{xx} = \Pi_x \notickmatrix \Pi_x$, each element of $\notickmatrix_{xx}$ is equal to either the original value of the element in $\notickmatrix$ or to zero. Thus Eq. \ref{eq:nontickcondition} is still satisfied because $\notickmatrix$ is a non-event generator. On the other hand, $\notickmatrix_{\bar{x}x} = \Pi_{\bar{x}} \notickmatrix \Pi_x$, and thus all of its diagonal elements are zero. Its off-diagonal elements are either equal to those of $\notickmatrix$ which are non-negative, or zero. Thus Eq. \ref{eq:tickcondition} is satisfied, proving that $\notickmatrix_{\bar{x}x}$ is an event generator. Finally, the sum of the generators satisfies (from Eq. \ref{eq:spacegenerators})
\begin{align}
	\notickmatrix_{xx} + \notickmatrix_{\bar{x}x} &= \Pi_{\bar{x}} \notickmatrix \Pi_x + \Pi_x \notickmatrix \Pi_x = \notickmatrix \Pi_x, \quad \text{because $\Pi_{\bar{x}} + \Pi_x = \mathds{1}$}.
\end{align}
Thus the sum of the two generators is the original non-event generator $\notickmatrix$ with some of its columns set to zero (those outside the support of $\Pi_x$). Thus adding the column sums of $\notickmatrix_{xx}$ and $\notickmatrix_{\bar{x}x}$ gives either the corresponding column sum of $\notickmatrix$, or zero. In either case, Eq. \ref{eq:stochasticcondition} is satisfied, completing the conditions that determine that $\{\notickmatrix_{xx}, \notickmatrix_{\bar{x}x}\}$ is a pair of stochastic generators.

To prove that the sequence is an independent one (Def. \ref{def:independentsequence}), one has to show that both of the non-event generators in the sequence, the $\notickmatrix_{\bar{x}x}$, are rank-1. From Eq. \ref{eq:generatorvisual}, one observes that $\notickmatrix_{01}$ has a single non-zero row, while $\notickmatrix_{10}$ has a single non-zero column. Thus Def. \ref{def:independentsequence} is satisfied.

To demonstrate that each $v_{n,x}(t) \in S_x$, we express them as (for all cases except $n=x=0$) the solution to their differential equations (Eq. \ref{eq:spacestatedynamics}),
\begin{align}
v_{n,x}(t) &= v_{n,x}(t=0) + \int_0^t \frac{d}{dt^\prime} v_{n,x}(t^\prime) dt^\prime \\
&= \int_0^t \notickmatrix_{xx} v_{n,x}(t^\prime) + \notickmatrix_{x\bar{x}} v_{n-\bar{x},\bar{x}}(t^\prime) dt^\prime \\
&= \int_0^t \Pi_x \notickmatrix \Pi_x v_{n,x}(t^\prime) + \Pi_x \notickmatrix \Pi_{\bar{x}} v_{n-\bar{x},\bar{x}}(t^\prime) dt^\prime,
\end{align}
using the definition of the $\notickmatrix_{xy}$ (Eq. \ref{eq:spacegenerators}, and since the initial states are all zero vectors except for $n=x=0$. Left-multiplying the above expression by the projects $\Pi_x$ and $\Pi_{\bar{x}}$ respectively recovers the statement of the lemma.

For the special case $n=x=0$, the initial state $v_{0,0}(0)$ is the canonical state $\mathbf{e}_0$ and thus satisfies the lemma. Furthermore, the derivative of the state is proportional only to $\notickmatrix_{00} = \Pi_0 \notickmatrix \Pi_0$. The proof thus follows in an analogous manner.

\end{proof}

\begin{lemma}[Decomposing the path-specific delay functions w.r.t. the path-generating delay functions]\label{lemma:pathdensityconv}

The path-specific delay functions $\xi_{n,x}(t)$ (Def. \ref{def:pathdensities}) are sequential convolutions of the path-generating delay functions $\Theta_x$ (Def. \ref{def:pathgeneratingdelay}),
\begin{align}\label{eq:tempdelayconvolution}
\xi_{n,x}(t) &= \left( \Theta_1 \conv \Theta_0 \conv \Theta_1 \conv \Theta_0 \conv ... \conv \Theta_x \right) (t),
\end{align}
where $\Theta_1$ appears $n+x$ times and $\Theta_0$ appears $n$ times.

\end{lemma}

\begin{proof}

As Lemma \ref{lemma:pathmarkoviansequence} has proven that $\xi_{n,x}(t)$ are the delay functions of an independent Markovian sequence, we may apply Lemma \ref{lemma:resetsequenceconvolution}, to express them as
\begin{align}
\xi_{n,x}(t) &= \left( \nu_{0,1} \conv \nu_{1,0} \conv \nu_{1,1} \conv \nu_{2,0} \conv ... \conv \nu_{n,x} \right) (t),
\end{align}
where the sub-event delay functions $\nu_{n,x}$ are defined in Def. \ref{def:resetsubeventdelay}, and for the present sequence, take on the form
\begin{align}\label{eq:tempgeneratingdelay}
	\nu_{n,x}(t) &= \onenorm{ \notickmatrix_{x\bar{x}} e^{\notickmatrix_{\bar{x}\bar{x}} t} \mathbf{w}_{n,\bar{x}} },
\end{align}
where $\mathbf{w}_{n,\bar{x}}$ is the reset state (Def. \ref{def:eventresetstate} for the event $\{n,x\}$ in the sequence.

Consider the reset state $\mathbf{w}_{n,0}$. This is defined to be (Def. \ref{def:eventresetstate}) the unique normalised state that is proportional to every column of the corresponding generator in the sequence, which in this case is $\notickmatrix_{01}$ (see Lemma \ref{lemma:pathmarkoviansequence}). From the definition of $\notickmatrix_{xy}$ (see Eq. \ref{eq:generatorvisual}), we conclude that this is simply the canonical state $\mathbf{e}_0$, and thus $\mathbf{w}_{n,0} = \mathbf{u}_0$, the path-generating reset state defined in Def. \ref{def:spaceresetstates}.

In a similar manner, the reset state $\mathbf{w}_{n,1}$ is the unique normalised state proportional to every column of $\notickmatrix_{10}$. This operator has only a single non-zero column, and the corresponding normalised state has already been defined to be the other path-generating reset state, $\mathbf{u}_1$ (Def. \ref{def:spaceresetstates}).

Thus, returning to Eq. \ref{eq:tempgeneratingdelay}, we see that the sub-event delay functions $\nu_{n,x}(t)$ are in fact, indpendent of $n$, and equal to the path-generating delay functions $\Theta_x$ defined in Def. \ref{def:pathgeneratingdelay}. Substituting these back into Eq. \ref{eq:tempdelayconvolution}, we recover the statement of the lemma.

\end{proof}

\begin{lemma}[Explicit form and properties of the path-generating delay function $\Theta_1$ (Def. \ref{def:pathgeneratingdelay}) and tick-generating delay function $\Gamma_1$ (Def. \ref{def:tickgeneratingdelay}).]\label{lemma:pathgeneratingdelay1}

\begin{align}\label{eq:theta1}
	\Theta_1(t) &= A e^{-gt}, \\
	\Gamma_1(t) &= B e^{-gt},
\end{align}
where $A \geq 0$ is the sum of the first (and only non-zero) column of $\notickmatrix_{10}$, $B \geq 0$ is the only (possibly) non-zero element of $\tickmatrix_{00}$, and $g \geq 0$ is the negation of the singular non-zero element in $\notickmatrix_{00}$. (see Eq. \ref{eq:generatorvisual}). If $g=0$, then $\Theta_1(t) = \Gamma_1(t) = 0$ for all $t$. Denoting the moments (Def. \ref{def:delayfunctionmoments}) of $\Theta_1$ by $\{Q_1,\mu_1,\chi_1\}$ and those of $\Gamma_1$ by $\{Q_3,\mu_3,\chi_3\}$, they are (in the case $g > 0$)
\begin{subequations}\label{eq:1dmoments}
	\begin{align}
		Q_1 &= \frac{A}{g} \\
		Q_3 &= \frac{B}{g} \\
		\mu_1 &= \mu_3 =  \frac{1}{g} \\
		\chi_1 &= \chi_3 = \frac{2}{g^2},
	\end{align}
\end{subequations}
and their $\gamma$-values and accuracies $R$ (Def. \ref{def:accuracydelayfunction} and Eq. \ref{eq:accuracygamma}) are therefore
\begin{align}
	\gamma_1 &= \gamma_3 = 2, \\
	R \left[ \Theta_1 \right] &= R \left[ \Gamma_1 \right] = 1.
\end{align}

\end{lemma}

\begin{proof}

Via the definition of $\Theta_1$ in Def. \ref{def:pathgeneratingdelay}, and since $\mathbf{u}_0 = \mathbf{e}_0$ (Def. \ref{def:spaceresetstates},
\begin{align}
	\Theta_1(t) &= \onenorm{ \notickmatrix_{10} e^{\notickmatrix_{00} t} \mathbf{e}_0 }.
\end{align}

However, the operator $\notickmatrix_{00}$, (see Eq. \ref{eq:generatorvisual}), has only a single non-zero element, on the diagonal, and corresponding to $\mathbf{e}_0$. We label this element by , $-g$, where $g \geq 0$ (recall that the diagonal elements of $\notickmatrix$ are non-positive (Def. \ref{def:stochasticgenerators}). One thus simplifies the action of $e^{\notickmatrix_{00} t}$ on $\mathbf{e}_0$, obtaining
\begin{align}
	\Theta_1(t) &= \onenorm{ \notickmatrix_{10} e^{-g t} \mathbf{e}_0 } \\
	&= A e^{-gt},
\end{align}
where $A = \onenorm{ \notickmatrix_{10} \mathbf{e}_0 }$ is the sum of the first column of $\notickmatrix_{10}$.

If $g=0$, then from the definition of stochastic generators, Def. \ref{def:stochasticgenerators} and Corollary \ref{cor:zerotickmatrix}, it follows that the entire first column of $\notickmatrix$ is zero, and thus $A$ is also zero, leading to $\Theta_1$ being the zero function.

In a similar manner, using the definition of $\Gamma_1$ (Def. \ref{def:tickgeneratingdelay}),
\begin{align}
	\Gamma_1 &= \onenorm{ \tickmatrix_{00} e^{\notickmatrix_{00} t} \mathbf{e}_0 } = B e^{-gt},
\end{align}
where $B$ is the single (possibly) non-zero element in $\tickmatrix_{00}$. If $g=0$, then it follows from the fact that $\{\notickmatrix_{00},\tickmatrix_{00}\}$ is also a pair of stochastic generators (Def. \ref{def:stochasticgenerators}), that $B=0$ as well, and therefore $\Gamma_1$ is the zero function in this case.

The rest of the lemma follows from the direct application of the definition of the moments (Def. \ref{def:delayfunctionmoments}), the accuracy $R$ (Def. \ref{def:accuracydelayfunction}), and the $\gamma$-value (Eq. \ref{eq:accuracygamma}), in the case that $g>0$.

\end{proof}

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

The partial norm (Def. \ref{def:partialnorm}) of the path-generation delay function $\Theta_1$ is strictly smaller than $1$ for all $t \geq 0$.

\end{corollary}

\begin{proof}

From the explicit form of $\Theta_1$ (Lemma \ref{lemma:pathgeneratingdelay1}), we can calculate its partial norm (Def. \ref{def:partialnorm}) explicitly,
\begin{align}
	P_t \left[ \Theta_1 \right] &= \int_0^t \Theta_1(t) dt = \begin{cases}
		0 & \text{if $g=0$}, \\
		\frac{A}{g} \left( 1 - e^{-gt} \right) & \text{if $g>0$.}
	\end{cases}
\end{align}

The case $g=0$ satisfies the corollary trivially. For the case $g>0$, note that
\begin{align}
	P_t \left[ \Theta_1 \right] &= \frac{A}{g} \left( 1 - e^{-gt} \right) = Q_1 \left( 1 - e^{-gt} \right) < Q_1 \quad \forall t,
\end{align}
where $Q_1$ is the zeroth moment of $\Theta_1$ (Lemma \ref{lemma:pathgeneratingdelay1}), and is itself upper bounded by $1$ (see Def. \ref{def:delayfunction}). Thus the partial norm is strictly less than $1$ for all $t$.

\end{proof}

\begin{lemma}\label{lemma:pathgeneratindelay2}

The delay functions $\Theta_0$ (Def. \ref{def:pathgeneratingdelay}) and $\Gamma_0$ (Def. \ref{def:tickgeneratingdelay}) can be generated by $d-1$ dimensional clocks.

\end{lemma}

\begin{proof}

We prove the statement for $\Theta_0$, the proof for $\Gamma_0$ is analogous. From Def. \ref{def:pathgeneratingdelay},
\begin{align}\label{eq:pathdelay0}
\Theta_0(t) &= \onenorm{ \notickmatrix_{01} e^{\notickmatrix_{11} t} \mathbf{u}_1 }.
\end{align}

While the expression above appears to involve the entire vector space $\mathbb{R}^d$, in fact, one can generate the same delay function with only $d-1$ dimensional objects, as we proceed to show.

First off, take the event generator $\notickmatrix_{01}$. From Eq. \ref{eq:generatorvisual}, we observe that only the first row is non-zero, and of this row, the first element is zero. Consider the modified event generator $\notickmatrix_{01}^\prime$, formed by swapping the first row with any other. By Lemma \ref{lemma:resetinvariance}, this leaves the delay function $\Theta_0(t)$ unchanged. The entire first row and column of the modified generator are zero. Next, we note that $\notickmatrix_{11}$ by construction (see Eq. \ref{eq:generatorvisual}) already has a zero first row and column. Thus both $\notickmatrix_{11}$ and $\notickmatrix_{01}^\prime$ act trivially on the canonical state $\mathbf{e}_0$.

Finally, $\mathbf{u}_1$ (Def. \ref{def:spaceresetstates}) is constructed from the first column of $\notickmatrix_{10}$, that has a zero element at the top (see Eq. \ref{eq:generatorvisual}), and thus $\mathbf{u}_1$ has no component from the canonical state $\mathbf{e}_0$. Thus we may simply remove this space entirely from $\mathbf{u}_1$, and correspondingly from the operators $\notickmatrix_{11}$ and $\notickmatrix_{01}^\prime$, and still generate the same delay function $\Theta_0$.

\end{proof}

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

Assuming that the accuracy of a single tick of a $d-1$ dimensional clock is upper bound by $R \leq d-1$, as is done during this proof, one can lower bound the second moments of $\Theta_0$ and $\Gamma_0$ w.r.t. their first moments,
\begin{subequations}
\begin{align}
	\chi_0 &\geq \mu_0^2 \left( 1 + \frac{1}{d-1} \right) \\
	\chi_2 &\geq \mu_2^2 \left( 1 + \frac{1}{d-1} \right),
\end{align}
\end{subequations}
if the first moments $\mu_0$ and $\mu_2$ do not diverge.
\end{corollary}

\begin{proof}

From Lemma \ref{lemma:pathgeneratindelay2}, we know that both $\Theta_0$ and $\Gamma_0$ can be generated by $d-1$ dimensional clocks, but we have assumed the accuracy $R$ (Def. \ref{def:accuracydelayfunction}) of these clocks to be upper bound by $R \leq d-1$. The corollary then follows from the definition of the $\gamma$-value (Eq. \ref{eq:accuracygamma}) and its relationship with the accuracy $R$.

\end{proof}

\begin{lemma}[Recovering the clock state and delay function from the path-specific states and component delay functions]\label{lemma:recoverstatedelay}

The state of the clock $V(t)$ corresponding to the first tick (Eq. \ref{eq:singletickstatedelay}) is the series sum of the path-specific states (Def. \ref{def:pathstates}),
\begin{align}
	V(t) &= \sum_{n=0}^\infty \sum_{x\in\{0,1\}} v_{n,x}(t).
\end{align}

Furthermore, the delay function $\tau(t)$ of a single tick of the clock (Eq. \ref{eq:singletickstatedelay}) is the series sum of the component delay functions (Def. \ref{def:componentdelay}),
\begin{align}
	\tau(t) &= \tau_{0,1}(t) + \sum_{n=1}^\infty \sum_{x\in\{0,1\}} \tau_{n,x}(t).
\end{align}

\end{lemma}

\begin{proof}

Consider the following sequence of states, $\{v^{(M)}_{n,x}(t)\}$, defined for $x \in \{0,1\}$ and $n \in \{0,1,...,M\}$, where $M \in \mathbb{N}^+$, and whose initial states and dynamics are identical to those of the path-specific states $v_{n,x}(t)$ (see Def. \ref{def:pathstates}) except for the last one $v^{(M)}_{M,1}(t)$, that evolves as
\begin{align}\label{eq:endstatedynamics}
	\frac{d}{dt} v^{(M)}_{M,1} &= \notickmatrix_{10} v^{(M)}_{M,0} + \notickmatrix v^{(M)}_{M,1}.
\end{align}
where the last term above differentiates it from the dynamics of the original sequence, by including the entire non-event generator $\notickmatrix$ rather than only $\notickmatrix_{11}$. Intuitively this corresponds to interrupting the sequence at $n=M,x=1$ by stopping the flow of of population to further states. It is straightforward to verify that this too is an independent Markovian sequence of events (Def. \ref{def:independentsequence}).

Since the initial states and dynamical equations of all but the last state in the sequence $v^{(M)}_{n,x}$ are identical to those of the sequence $v_{n,x}$, and because the dynamics of every state in a Markovian sequence only depend on the previous states in the sequence, it follows that $v^{(M)}_{n,x}(t) = v_{n,x}(t)$ for all $x$ and $M$ except for the final state $v^{(M)}_{M,1}(t)$. Furthermore, this also implies that the corresponding delay functions of the sequence of states $v^{(M)}_{n,x}$ are the path-specific delay functions $\xi_{n,x}$ (Def. \ref{def:pathdensities}), upto and including $n=M,x=1$.

Consider the vector $V^{(M)}$, defined as the sum
\begin{align}\label{eq:tempstatesum}
	V^{(M)}(t) &= \sum_{n=0}^{M} \sum_{x\in\{0,1\}} v^{(M)}_{n,x}(t),
\end{align}
that we proceed to show is equal to $V(t)$, the state of the clock for a single tick (Eq. \ref{eq:singletickstatedelay}). For $t=0$, by construction $V^{(M)}(0) = V(0)$. For $t \geq 0$, the dynamics of the sum is given by (Eqs. \ref{eq:spacestatedynamics} and \ref{eq:endstatedynamics})
\begin{align}
	\frac{d}{dt} V^{(M)}(t) &= \sum_{n=0}^{M} \sum_{x\in\{0,1\}} \frac{d}{dt} v^{(M)}_{n,x}(t) \\
	&= \sum_{n=0}^{M-1} \sum_{x\in\{0,1\}} \left( \notickmatrix_{xx} + \notickmatrix_{\bar{x}x} \right) v^{(M)}_{n,x}(t) + \left( \notickmatrix_{00} + \notickmatrix_{10} \right) v^{(M)}_{M,0}(t) + \notickmatrix v^{(M)}_{M,1}(t) \\
	&= \sum_{n=0}^{M-1} \sum_{x\in\{0,1\}} \left( \notickmatrix_{xx} + \notickmatrix_{\bar{x}x} \right) v_{n,x}(t) + \left( \notickmatrix_{00} + \notickmatrix_{10} \right) v_{M,0}(t) + \notickmatrix v^{(M)}_{M,1}(t). \label{eq:tempref1}
\end{align}

We may use the fact that each $v_{n,x}(t) \in S_x$ for all $t \geq 0$ (Lemma \ref{lemma:pathmarkoviansequence}), together with the definition of the generators $\notickmatrix_{xy}$ (Eq. \ref{eq:spacegenerators}) to conclude that for all $n$ and $x$,
\begin{align}
	\left( \notickmatrix_{\bar{x}\bar{x}} + \notickmatrix_{x\bar{x}} \right) v_{n,x}(t) = \mathbf{0}.
\end{align}
Adding these trivial zeros to Eq. \ref{eq:tempref1}, and using the decomposition of $\notickmatrix$, (Eq. \ref{eq:spacegenerators}),
\begin{align}
	\frac{d}{dt} V^{(M)}(t) &= \sum_{n=0}^M \sum_{x\in\{0,1\}} \notickmatrix v^{(M)}_{n,x}(t) \\
	&= \notickmatrix V^{(M)}(t). \\
	\therefore \; V^{(M)}(t) &= e^{\notickmatrix t} V^{(M)}(0) = e^{\notickmatrix t} V(0) = V(t). \label{eq:tempstateequal}
\end{align}

Finally, we investigate the limit $M \rightarrow \infty$ of $V^{(M)}(t)$,
\begin{align}
	\lim_{M\rightarrow\infty} V^{(M)}(t) &= \lim_{M\rightarrow\infty} \left( \sum_{n=0}^{M-1} \sum_{x\in\{0,1\}} v_{n,x}(t) + v_{M,0}(t) + v^{(M)}_{M,1}(t) \right) \\
	&= \sum_{n=0}^\infty \sum_{x\in\{0,1\}} v_{n,x}(t) + \lim_{M\rightarrow\infty} v^{(M)}_{M,1}(t). \label{eq:tempstateMinfty}
\end{align}

To prove that the state $v^{(M)}_{M,1}(t)$ goes to zero, we first apply Lemma \ref{lemma:resetsequenceconvolution} to express it as
\begin{align}
	v^{(M)}_{M,1}(t) &= \int_0^t e^{\notickmatrix (t-t^\prime)} \mathbf{w}_{M,1} \; \xi_{M,1}(t^\prime) (t^\prime) dt^\prime,
\end{align}
where $\mathbf{w}_{M,1}$ is the event reset state (Def. \ref{def:eventresetstate}) for the $n=M,x=1$ event, that has already been proven to be equal to $\mathbf{u}_1$ (see discussion after Eq. \ref{eq:tempgeneratingdelay}). Calculating the norm (Def. \ref{def:norm}) of the above,
\begin{align}
	\onenorm{v_{M,1}(t)} &= \int_0^t \onenorm{ e^{\notickmatrix_{11} (t-t^\prime)} \mathbf{u}_1 } \xi_{M,1}(t^\prime) dt^\prime.
\end{align}
However the term in the e-sum above is a population vector for all $t-t^\prime \geq 0$ (see Lemma \ref{lemma:stochasticgenerators}), and thus the norm is upper bounded by $1$, leading to
\begin{align}
	\onenorm{v_{M,1}(t)} &\leq \int_0^t \xi_{M,1}(t^\prime) dt^\prime = P_t \left[ \xi_{M,1} \right].
\end{align}
where the partial norm $P_t[\cdot]$ is defined in Def. \ref{def:partialnorm}. As $\xi_{n,x}$ is itself a convolution of delay functions (Lemma \ref{lemma:pathdensityconv}), we can apply Lemma \ref{lemma:delaynorm}, to obtain
\begin{align}
	\onenorm{v_{M,1}(t)} &\leq \left( P_t \left[ \Theta_1 \right] \right)^{M+1} \left( P_t \left[ \Theta_0 \right] \right)^M \\
	&\leq \left( P_t \left[ \Theta_1 \right] \right)^{M+1},
\end{align}
using the fact that the partial norm is upper bounded by 1.

However, from Corollary \ref{cor:boundedpartialnorm}, the partial norm of $\Theta_1$ is srictly less than $1$ for all $t \geq 0$, and thus
\begin{align}\label{eq:templimitzero}
	\lim_{M\rightarrow\infty} \onenorm{ v_{M,1}(t) } = 0,
\end{align}
which in turn implies that every element of $v_{M,1}(t)$ must individually go to zero. Combining this with Eqs. \ref{eq:tempstateequal} and \ref{eq:tempstateMinfty}, we recover
\begin{align}
	V(t) &= \sum_{n=0}^\infty \sum_{x\in\{0,1\}} v_{n,x}(t).
\end{align}

The proof of the second statement of the lemma, concerning the delay function, proceeds in an analogous manner. Consider the following sequence of delay functions, $\{\tau^{(M)}(t)\}$, defined w.r.t. the sequence of states $v^{(M)}_{n,x}(t)$ as
\begin{align}
	\tau^{(M)}_{n,x}(t) &= \onenorm{ \tickmatrix_{0\bar{x}} v^{(M)}_{n-\bar{x},\bar{x}}(t) },
\end{align}
for all $n,x$ from $n=0,x=1$ up to and including $n=M,x=1$. Finally, the end delay function of the sequence is defined as
\begin{align}
	\tau^{(M)}_{M+1,0}(t) &= \onenorm{ \tickmatrix v^{(M)}_{M,1}(t) }.
\end{align}

Note immediately that since $v^{(M)}_{n,x}(t) = v_{n,x}(t)$ for all the states except $v^{(M)}_{M,1}(t)$, it follows that $\tau^{(M)}_{n,x}(t) = \tau_{n,x}(t)$ (Def. \ref{def:pathdensities}) except for the final delay function $\tau^{(M)}_{M+1,0}(t)$.

Consider the sum
\begin{align}
	f^{(M)}(t) &= \tau^{(M)}_{0,1}(t) + \sum_{n=1}^{M} \sum_{x\in\{0,1\}} \tau^{(M)}_{n,x}(t) + \tau^{(M)}_{M+1,0}(t),
\end{align}
which we proceed to show is equal to the delay function $\tau(t)$ of a single tick of the clock, Eq. \ref{eq:singletickstatedelay}.
\begin{align}
	f^{(M)}(t) &= \onenorm{ \tickmatrix_{00} v^{(M)}_{0,0}(t) } + \sum_{n=1}^{M-1} \sum_{x\in\{0,1\}} \onenorm{ \tickmatrix_{0\bar{x}} v^{(M)}_{n-\bar{x},\bar{x}}(t) } + \onenorm{ \tickmatrix_{00} v^{(M)}_{M,0}(t) } + \onenorm{ \tickmatrix v^{(M)}_{M,1}(t) } \\
	&= \onenorm{ \tickmatrix_{00} v_{0,0}(t) } + \sum_{n=1}^{M} \sum_{x\in\{0,1\}} \onenorm{ \tickmatrix_{0\bar{x}} v_{n-\bar{x},\bar{x}}(t) } + \onenorm{ \tickmatrix_{00} v_{M,0}(t) }  + \onenorm{ \tickmatrix v^{(M)}_{M,1}(t) }
\end{align}

Using the definition of $\tickmatrix_{xy} = \Pi_x \tickmatrix \Pi_y$ (Eq. \ref{eq:spacetickers}), and also the fact that each $v_{n,x} \in S_x$ (Lemma \ref{lemma:pathmarkoviansequence}), we can trivially add $\tickmatrix_{0 \bar{x}} v^{(M)}_{n,x} = \mathbf{0}$ to any expression, and doing so to the above equation results in
\begin{align}
	f^{(M)}(t) &= \onenorm{ \sum_{n=0}^{M-1} \sum_{x\in\{0,1\}} \left( \tickmatrix_{0x} + \tickmatrix_{0\bar{x}} \right) v^{(M)}_{n,x}(t) } + \onenorm{ \left( \tickmatrix_{0x} + \tickmatrix_{0\bar{x}} \right) v^{(M)}_{M,0}(t) } + \onenorm{ \tickmatrix v^{(M)}_{M,1}(t) } \\
	&= \onenorm{ \tickmatrix V^{(M)}(t) } = \onenorm{ \tickmatrix V(t) } = \tau(t). \label{eq:temppartialsumdelay}
\end{align}

Thus $f^{(M)}(t)$ is the delay function of a single tick of the clock (Eq. \ref{eq:singletickstatedelay}). To complete the proof, we investigate the limit as $M \rightarrow \infty$,
\begin{align}
	\lim_{M\rightarrow\infty} f^{(M)} &= \lim_{M\rightarrow\infty} \left( \tau^{(M)}_{0,1}(t) + \sum_{n=1}^{M} \sum_{x\in\{0,1\}} \tau^{(M)}_{n,x}(t) + \tau^{(M)}_{M+1,0}(t) \right) \\
	&= \lim_{M\rightarrow\infty} \left( \tau_{0,1}(t) + \sum_{n=1}^{M} \sum_{x\in\{0,1\}} \tau_{n,x}(t) \right) + \lim_{M\rightarrow\infty} \tau^{(M)}_{M+1,0}(t) \\
	&= \sum_{n=0}^\infty \sum_{x\in\{0,1\}} \tau_{n,x}(t) + \lim_{M\rightarrow\infty}  \onenorm{ \tickmatrix v^{(M)}_{M,1}(t) }.
\end{align}

But the remaining term on the right goes to zero, as we have already proved that $v^{(M)}_{M,1}(t)$ goes to zero (see Eq. \ref{eq:templimitzero}), and $\tickmatrix$ is a bounded linear operator. From the above expression and Eq. \ref{eq:temppartialsumdelay}, we recover
\begin{align}
	\tau(t) &= \sum_{n=0}^\infty \sum_{x\in\{0,1\}} \tau_{n,x}(t),
\end{align}
which completes the proof of the lemma.

\end{proof}

\subsubsection{The moments of the delay function of a single tick of the clock}\label{proof:delayexplicit}

We proceed by calculating the moments of the delay function of a single tick of a clock by using the path-specific delay functions and component delay functions.

Consider the component delay function (Def. \ref{def:componentdelay}),
\begin{align}
	\tau_{n,x}(t) &= \onenorm{ \tickmatrix_{0\bar{x}} v_{n-\bar{x},\bar{x}}(t) } \\
	&= \onenorm{ \int_0^t \tickmatrix_{0\bar{x}} e^{\notickmatrix_{\bar{x}\bar{x}} (t-t^\prime)} \mathbf{u}_{\bar{x}} \xi_{n-\bar{x},\bar{x}}(t^\prime) dt^\prime },
\end{align}
where we have applied Lemma \ref{lemma:resetsequenceconvolution} to express the path-specific state $v_{n-\bar{x},\bar{x}}(t)$ w.r.t. it's corresponding path-specific delay function, as they form an independent Markovian sequence (Lemma \ref{lemma:pathmarkoviansequence}). Continuing, we simplify the above to
\begin{align}
	\tau_{n,x}(t) &= \int_0^t \onenorm{ \tickmatrix_{0\bar{x}} e^{\notickmatrix_{\bar{x}\bar{x}} (t-t^\prime)} \mathbf{u}_{\bar{x}} } \xi_{n-\bar{x},\bar{x}}(t^\prime) dt^\prime \\
	&= \int_0^t \Gamma_x(t-t^\prime)  \xi_{n-\bar{x},\bar{x}}(t^\prime) dt^\prime,
\end{align}
using the definition of the tick-generating delay functions $\Gamma_x$ (Def. \ref{def:tickgeneratingdelay}). Finally,
\begin{align}
	\tau_{n,x}(t) &= \left( \Gamma_x \conv \xi_{n-\bar{x},\bar{x}} \right) (t) \\
	&= \left( \Gamma_x \conv \Theta_1 \conv \Theta_0 \conv \Theta_1 \conv \Theta_0 \conv ... \conv \Theta_{\bar{x}} \right) (t),
\end{align}
using Lemma \ref{lemma:pathdensityconv}. In the above convolution, $\Theta_1$ appears $n$ times, and $\Theta_0$ appears $n-\bar{x}$ times.

We can now calculate the moments of the component delay function $\tau_{n,x}$ using Eq. \ref{eq:sequencemoments} for a convolution of a sequence of delay functions. The moments (Def. \ref{def:delayfunctionmoments}) of $\Theta_1$ and $\Gamma_1$ have already been labelled and calculated in Lemma \ref{lemma:pathgeneratingdelay1}. For now, we label them (in order of zeroth, first and second moments) as $\{Q_1,\mu_1,\chi_1\}$ for $\Theta_1$ and $\{Q_3,\mu_1,\chi_1\}$ for $\Gamma_1$ (the first and second moments of these two delay functions were proven equal in Lemma \ref{lemma:pathgeneratingdelay1}). The moments of $\Theta_0$ (Def. \ref{def:pathgeneratingdelay}) are denoted as $\{Q_0,\mu_0,\chi_0\}$ and the moments of $\Gamma_0$ (Def. \ref{def:tickgeneratingdelay}) by $\{Q_2,\mu_2,\chi_2\}$.

Finally, denoting the zeroth, first and second moments of the component delay function $\tau_{n,x}(t)$ by $Q_{n,x}$, $\mu_{n,x}$ and $\chi_{n,x}$ respectively, from Eq. \ref{eq:sequencemoments},
\begin{align}
	Q_{n,0} &= Q_1^n Q_0^{n-1} Q_2 \\
	\mu_{n,0} &= n \mu_1 + (n-1) \mu_0 + \mu_2 \\
	\chi_{n,0} &= n \chi_1 + (n-1) \chi_0 + \chi_2 + n(n-1) \mu_1^2 + (n-1)(n-2) \mu_0^2 + 2 n(n-1) \mu_1 \mu_0 + 2 n \mu_1 \mu_2 + 2 (n-1) \mu_0 \mu_2 \\
	Q_{n,1} &= Q_1^n Q_0^n Q_3 \\
	\mu_{n,1} &= (n+1) \mu_1 + n \mu_0 \\
	\chi_{n,1} &= (n+1) \chi_1 + n \chi_0 + n(n+1) \mu_1^2 + n(n-1) \chi_0^2 + 2 n(n+1) \mu_1 \mu_0. \\
\end{align}

We are now in a position to calculate the accuracy of a single tick of the clock. First off, we split the delay function of a single tick of the clock into two parts, w.r.t. the some over component delay functions,
\begin{align}
	\tau(t) &= \tau_{0,1}(t) + \sum_{n=0}^\infty \sum_{x\in\{0,1\}} \tau_{n,x}(t) \\
	&= \sum_{n=1}^\infty \tau_{n,0}(t) + \sum_{n=0}^\infty \tau_{n,1}(t) \\
	&= \tau^{(1)}(t) + \tau^{(0)}(t).
\end{align}

We may understand the above division in the following manner. The component delay function $\tau_{n,x}$ is generated by $\tickmatrix_{0\bar{x}}$ (see Def. \ref{def:componentdelay}), and thus represents a tick being generated from the $S_{\bar{x}}$ subspace of the clock vector space. Thus the two $\tau^{(x)}(t)$ above each correspond to the delay function of a single tick generated from $S_{x}$.

From Lemma \ref{lemma:delaymixture}, the accuracy of the sum of two delay functions is upper bound by the maximum accuracy from among the two, and we proceed to bound each of the accuracies individually.

For $\tau^{(0)}$, (that corresponds to the tick arising from the $S_0$ subspace), we find the zeroth, first and second moments of the entire tick density to be (on application of Def. \ref{def:delayfunctionmoments}),
\begin{align}
	Q^{(0)} &= \sum_{n=0}^\infty Q_{n,1} = \frac{Q_3}{1 - Q_1 Q_0} \\
	\mu^{(0)} &= \frac{\sum_{n=0}^\infty Q_{n,1} \mu_{n,1}}{Q^{(0)}} = \frac{Q_0 Q_1 \mu_0 + \mu_1}{1 - Q_0 Q_1} \\
	\chi^{(0)} &= \frac{\sum_{n=0}^\infty Q_{n,1} \chi_{n,1}}{Q^{(0)}} = \frac{(Q_0 Q_1 \mu_0 + \mu_1)^2 + Q_0 Q_1 \chi_0 (1 - Q_0 Q_1)}{(1 - Q_0 Q_1)^2},
\end{align}
where we have replaced $\chi_1 = 2 \mu_1^2$ (Eq. \ref{eq:1dmoments}) to simplify the expressions. Proceeding, we find that the accuracy is given by (Eq. \ref{eq:accuracygamma})
\begin{align}
	R \left[ \tau^{(0)} \right] &= \left( \frac{\chi^{(0)}}{\left( \mu^{(0)} \right)^2} - 1 \right)^{-1} = \frac{\left( Q_0 Q_1 \mu_0 + \mu_1 \right)^2}{ \left( Q_0 Q_1 \mu_0 + \mu_1 \right)^2 + Q_0 Q_1 \chi_0 \left( 1 - Q_0 Q_1 \right) }.
\end{align}

As $Q_0 Q_1$ is the product of the zeroth moments of delay functions and thus $\leq 1$, we see that the accuracy decreases monotonically w.r.t. $\chi_0$. As such, we may upper bound it by replacing $\chi_0$ by its minimum value using Corollary \ref{cor:previousbound}. Furthermore, noting that the moments $Q_0$ and $Q_1$ only appear as the product, and that $\mu_0$ and $\mu_1$ only affect the accuracy via their relative ratio, we can simplify the expression to
\begin{align}
	R \left[ \tau^{(0)} \right] &\leq \frac{(d-1)(1+pr)^2}{d + dpr(2+r) - (1+pr)^2},
\end{align}
where $p = Q_0 Q_1 \in (0,1]$ and $r=\mu_0/\mu_1 \in (0,\infty)$. One can analytically optimize the above expression w.r.t. $p$ and $r$, and we find that the maximal value of the accuracy is
\begin{align}
	R \left[ \tau^{(0)} \right] &\leq 1,
\end{align}
which is only the accuracy of a one-dimensional clock, and not very interesting.

On the other hand, consider the delay function $\tau^{(1)}(t)$, that corresponds to the tick being generated from $S_1$. We find the moments of the delay function to be
\begin{align}
Q^{(1)} &= \sum_{n=0}^\infty Q_{n,0} = \frac{Q_1 Q_2}{1 - Q_0 Q_1} \\
\mu^{(1)} &= \frac{\sum_{n=0}^\infty Q_{n,0} \mu_{n,0}}{Q^{(1)}} = \frac{Q_0 Q_1 \mu_0 + \mu_1}{1 - Q_0 Q_1} + \mu_2 \\
\chi^{(1)} &= \frac{\sum_{n=0}^\infty Q_{n,0} \chi_{n,0}}{Q^{(1)}} = \frac{2 \left( Q_0 Q_1 \mu_0 + \mu_1 \right) \left( \mu_1 + Q_0 Q_1 \left( \mu_0 - \mu_2 \right) + \mu_2 \right) + \left( 1 - Q_0 Q_1 \right) \left( Q_0 Q_1 \chi_0 + \left( 1 - Q_0 Q_1 \right) \chi_2 \right) }{(1 - Q_0 Q_1)^2}.
\end{align}

Here too, the second moment is seen to increase monotonically w.r.t both $\chi_0$ and $\chi_2$. As the accuracy itself is inversely related to the second moment, we may substitute the minimum $\chi_0$ and $\chi_2$ by their minimum values using Corollary \ref{cor:previousbound} to upper bound the accuracy. Furthermore, we replace $Q_0 Q_1 = p \in (0,1]$, $\mu_0/\mu_1 = r \in (0,\infty)$ and $\mu_2/\mu_1 = s \in (0,\infty)$ to find that the bound on the accuracy takes on the form
\begin{align}
	R \left[ \tau^{(1)} \right] &= \left( \frac{\chi^{(1)}}{\left( \mu^{(1)} \right)^2} - 1 \right)^{-1} \leq \frac{ (d-1) (1 + p(r-s) + s)^2}{ d + dpr(2+r) - (1-pr)^2 + (1-p)^2 s^2}.
\end{align}

One may analytically optimize the above expression w.r.t. $\{p,r,s\}$, and doing so returns the maximal value
\begin{align}
	R \left[ \tau^{(1)} \right] &\leq d.
\end{align}

Thus the accuracy of $\tau^{(1)}$, and thus $\tau$, the delay function of a single tick of a $d$-dimensional reset clock, is upper bound by $d$. By induction the result follows for all $d$. From Sec. \ref{sec:justifyR}, we can then conclude that the accuracy of the $n^{th}$ tick of the reset clock (and thus any clock, from Theorem \ref{theorem:resetclockaccuracy}) is upper bound by $n d$, completing the statement of the theorem.


TITLE: Show that the group $G$ is of order $12$
QUESTION [4 upvotes]: I am studying some exercises about semi-direct product and facing this solved one:

Show that the order of group $G=\langle a,b| a^6=1,a^3=b^2,aba=b\rangle$ is $12$.

Our aim is to show that $|G|\leq 12$ and then $G=\mathbb Z_3 \rtimes\mathbb Z_4=\langle x\rangle\rtimes\langle y\rangle$. So we need a homomorphism from $\mathbb Z_4$ to $\mathrm{Aut}(\mathbb Z_3)\cong\mathbb Z_2=\langle t\rangle$ to construct the semi-direct product as we wish: $$\phi:=\begin{cases} 1\longrightarrow \mathrm{id},& \\\\y^2\longrightarrow \mathrm{id},& \\\\y\longrightarrow t,& \\\\y^3\longrightarrow t, \end{cases}
$$ Here, I do know how to construct $\mathbb Z_3 \rtimes_{\phi}\mathbb Z_4$ by using $\phi$ and according to the definition. My question starts from this point:
The solution suddenly goes another way instead of doing $(a,b)(a',b')=(a\phi_b(a'),bb')$. It takes $$\alpha=(x,y^2), \beta=(1,y)$$ and note that these elements satisfy the relations in group $G$. All is right and understandable but how could I find such these later element $\alpha, \beta$?? Is really the formal way for this kind problems finding some generators like $\alpha, \beta$? Thanks for your help.

REPLY [0 votes]: $aba=b$ implies that $bab^{-1}=a^{-1}$, hence $bab^{-1}a^{-1}=a^{-2}$; it follows that $G'\supseteq \langle a^{-2}\rangle\cong \mathbb{Z}_3$. Also,
$b^{-1}a^2b=(b^{-1}ab)^2 = (b^{-1}aba.a^{-1})^2=(b^{-1}.ba^{-1})^2=a^{-2}\in \langle a^2\rangle$.
Hence $\langle a^2\rangle$ is normalised by both $b$, and $a$; $\langle a^2\rangle\triangleleft G$. Then $G/\langle a^2\rangle=\langle \bar{a},\bar{b}\colon \bar{a}^2=1, \bar{b}^2=\bar{a}, \bar{b}\bar{a}\bar{b}^{-1}\bar{a}^{-1}=1\rangle  = \langle \bar{b}\colon \bar{b}^4=1\rangle \cong \mathbb{Z}_4$.
Hence $G'=\langle a^2\rangle\cong \mathbb{Z}_3$, and $G/G'\cong \mathbb{Z}_4$.
Further $aba=b$ implies $abab=b^2$, i.e. $(ab)^2=b^2=a^3$. Therefore, $(ab)^4=(a^3)^2=1$, and $(ab)^2\neq 1$; hence $\langle ab\rangle$ is cyclic subgroup of $G$ of order $4$, and clearly, it should intersect trivially with $G'$ (compare orders). Hence $G=G'\rtimes \langle ab\rangle \cong \mathbb{Z}_3\rtimes \mathbb{Z}_4$.
...........................................................
To construct semidirect product of $\mathbb{Z}_3=\langle x\rangle$ by $\mathbb{Z}_4=\langle y\rangle$, note that $y$ acts on $\langle x\rangle$ by conjugation, and hence $y^{-1}xy\in \{x,x^2\}$. If $y^{-1}xy=x$, then $G$ will be abelian, and if $y^{-1}xy=x^2$, then $G$ will be the non-abelian group of order 12 (it is different from $D_{12}$, and $A_4$; why?).


TITLE: The Projection of a Vector onto a Plane
QUESTION [2 upvotes]: I want to find the orthogonal projection of the vector $\vec y$ onto a plane.
I have $\vec y = (1, -1, 2)$ and a plane that goes through the points
\begin{align*}u_1 = (1, 0, 0) \\ u_2 = (1, 1, 1) \\ u_3 = (0, 0, 1)
\end{align*}
I started by finding the equation for the plane by calculating: $\vec{PQ} = u_2 - u_1$ and $\vec{PR} = u_3 - u_1$.
I then took the cross product between $\vec{PQ}$ and $\vec{PR}$ and got $(1, -1, 1)$. I used the cross product as coefficients $a, b, c$ in the equation:
$$a(x - x_0) + b(y-y_0) + c(z-z_0) = 0$$
With this I got the plane equation to become $x - y + z = 1$.
Building on this, I went on to calculate the point where the vector $\vec y$ intersects the plane. I used $(0, 0, 0)$ as a starting point and $(1, -1, 2)$ as the endpoint.
$$r(t) = \{x_0, y_0, z_0\} + t\{x_1-x_0, y_1-y_0, z_1-z_0\} = (t, -t, 2t)$$
I inserted these parameters into the plane equation and got $t = 1/4$.
So the vector intersects the plane in $(1/4, -1/4, 1/2)$.
Now my task is to find the projection of the vector y onto the plane. My idea was to use the point of intersection together with the cross product to find a vector that is perpendicular to the plane. By using the point of intersection as the starting point and the cross product as the endpoint.
I could subtract y with this perpendicular vector and get the endpoint for the projection of y onto the plane, while also here using the point of intersection as the starting point.
Howevever, the resulting projection is not correct. Apparently, both the starting point and the end point has to be calculated differently.
I also tried using the Gram-Schmidt process to transform the base vectors $u_1$, $u_2$, $u_3$ into an ortogonal base. With this I tried to use the equation  $$\vec y' = \frac{\vec y·u_1}{u_1·u_1}\cdot u_1 + \frac{\vec y·u_2}{u_2·u_2}\cdot u_2 + \frac{\vec y·u_3}{u_3·u_3}\cdot u_3$$ to find the projection but a bit surprisingly arrived back at the original vector y when doing this.
Tremendously grateful for any tips.
Image of my problem:

REPLY [1 votes]: It looks like you’ve corrected the fundamental conceptual error that you were making in trying to find where $\vec y$ (really the line segment from the origin to $\vec y$) intersects the plane. That line of attack is suspect since there’s no a priori reason to believe that this intersection even exists.
However, once you’ve found an equation for the plane, the orthogonal projection of $\vec y$ onto this plane can be computed directly: it’s simply the foot of the perpendicular from $\vec y$ to the plane. A simple way to compute this point is to substitute $\vec y+t\vec n$, where $\vec n$ is normal to the plane, into the equation of the plane, and then solve for $t$: $$(1+t)-(-1-t)+(2+t)-1 = 3t+3 = 0,$$ so $t=-1$ and the orthogonal projection of $\vec y$ onto the plane is $(0,0,1)$.
You can instead compute the projection without finding an implicit Cartesian equation for the plane or even computing its normal by using the fact that the orthogonal projection of $\vec y$ onto the plane is the nearest point on the plane to $\vec y$. The plane can be parameterized by the affine combination $$\vec r(\alpha,\beta)=\alpha u_1+\beta u_2+(1-\alpha-\beta)u_3 = (\alpha+\beta,\beta,1-\alpha).$$ Minimizing the distance between $\vec y$ and $\vec r$ is equivalent to minimizing the square of the distance, namely $$(\alpha+\beta-1)^2+(\beta+1)^2+(1-\alpha-2)^2 = 2\alpha^2+2\alpha\beta+2\beta^2+3=\frac12(\alpha-\beta)^2+\frac32(\alpha+\beta)^2+3,$$ from which it’s obvious that the minimum is attained when $\alpha=\beta=0$, i.e., that the closest point to $\vec y$ is $(0,0,1)$.


TITLE: Solving birthday problem without complement
QUESTION [6 upvotes]: I'm trying to find the probability of at least 2 people in a room of 4 sharing the same birthday (without using complements).
I began by breaking the problem down into 4 cases:
Let E = the event that at least 2 people share the same birthday in a room of 4.
Our sample size: $365^4$
Case 1: 4 people share the same birthday: 365 ways
Case 2: 3 people share the same birthday, 1 distinct birthday: $365 \cdot 364 \cdot C(4,3)$
Case 3: 2 people share a birthday, another 2 people share some other birthday: $365 \cdot 364 \cdot \frac{C(4,2)}{2}$
Case 4: 2 people share same birthday, 2 distinct birthdays: $365 \cdot 364 \cdot 363 \cdot C(4,2) \cdot 2$
After adding up all the cases and dividing by the sample size to find probability the answer had an over-count. I checked my answer by doing $$P(E) = 1- \frac{365 \cdot 364 \cdot 363 \cdot 362}{365^4}$$
Where did I have an over-count? Thank you!

Here is an example that works with n = 3 people and at least 2 people share same birthday.
Case 1: 3 people share same birthday: 365
Case 2: 2 Same birthdays, 1 different: $365 \cdot 364 \cdot \binom{3}{2}$
$$P(E) = \frac{365 + (365 \cdot 364 \cdot \binom{3}{2})}{365^3} \equiv 1 - \frac{365 \cdot 364 \cdot 363}{365^3}$$
Those are both equivalent answers because in the complement we're subtracting away the event that all birthdays are distinct.

REPLY [2 votes]: When trying out a new way, it is prudent to look to a familiar class of problem, like die tosses in Yahtzee, ( except that here it is a $365$ sided die tossed 4 times.)
We  can then "straightjacket" it into a format  as [ Choose faces to come up ] $\times$ [ Permute ]
There are four possibilities:
$4\;of\;a\;kind: [\binom{365}1] \times [\frac {4!}{4!}]$
$3-1\;of\;a\;kind: [\binom{365}1\binom{364}1] \times [\frac{4!}{3!1!}]$
$2-2\;of\;a\;kind: [ \binom{365}2] \times [\frac{4!}{2!2!}]$
$2-1-1\;of\;a\;kind: [\binom{365}1\binom{364}2 \times [\frac{4!}{2!1!1!}]$
Add up to get favorable ways, and divide by $365^4$ to get the final result.


TITLE: How to rewrite this totient summation in terms of Mertens?
QUESTION [2 upvotes]: The totient sum function has an identity:
$\displaystyle\sum_{k=1}^{N}\varphi(k) = \sum_{k=1}^N {\rm M}(\lfloor\frac{N}{k}\rfloor)k $
$\varphi(k)$ is the Euler totient function, and $M$ is the Mertens function $\displaystyle M(N)=\sum_{k=1}^N \mu (k)$ where $\mu$ is the Moebius function.
My question: What is the Mertens function summation equivalent of $\displaystyle\sum_{k=1}^{N}k\varphi(k) $ and $\displaystyle\sum_{k=1}^{N}k^2\varphi(k)$?

REPLY [1 votes]: Since $\varphi(n)=n\sum_{d|n}\frac{\mu(d)}{d},$  by switching the order of summation we have that for fixed $l$  $$\sum_{n\leq x}\varphi(n)n^{l}=\sum_{kd\leq x}\mu(d)k^{l}d^{l}k$$
$$=\sum_{k\leq x}k^{l+1}\sum_{d\leq\frac{x}{d}}\mu(d)d^{l}.$$ Now, $$\sum_{d\leq y}\mu(d)d^{l}=\int_{0}^{y}t^{l}d\left(M(t)\right)=M(y)y^{l}-l\int_{0}^{y}M(t)t^{l-1}dt,$$ so you can write  $$\sum_{n\leq x}\varphi(n)n^{l}=\sum_{k\leq x}k^{l+1}\left(\frac{x}{k}\right)^{l}M\left(\frac{x}{k}\right)-l\int_{0}^{\frac{x}{k}}t^{l-1}M(t)dt.$$ This may be rearranged as
$$x^{l}\sum_{k\leq x}kM\left(\frac{x}{k}\right)-l\sum_{k\leq x}k^{l+1}\int_{0}^{\frac{x}{k}}t^{l-1}M(t)dt,$$ which is equal to
$$x^{l}\sum_{k\leq x}kM\left(\frac{x}{k}\right)-l\int_{0}^{x}t^{l-1}\sum_{k\leq x}k^{2}M\left(\frac{t}{k}\right)dt.$$