text:
\section{Properties of the OTC Problems}\label{app:existence}
In this appendix, we prove that solutions to the OTC and constrained OTC problems exist via continuity and compactness arguments and establish the triangle inequality for the unconstrained problem.
For a metric space $\calU$ and a sequence of Borel probability measures $\{\mu^n\} \subset \calM(\calU)$, we say that $\mu^n$ \emph{converges weakly to} $\mu \in \calM(\calU)$, denoted by $\mu^n  \Rightarrow \mu$, if for every continuous and bounded function $f: \calU \rightarrow \bbR$, $\int f \, d\mu^n \rightarrow \int f \, d\mu$.
A set $\Pi \subset \calM(\calU)$ is said to be \emph{weakly compact} if every sequence in $\Pi$ contains a subsequence converging weakly to an element of $\Pi$.
$\Pi$ is said to be \emph{tight} if for every $\varepsilon > 0$, there exists a compact set $K \subset \calU$ such that $\mu(K) > 1 - \varepsilon$ for every $\mu \in \Pi$.
Tightness and relative compactness are related by Prohorov's theorem which states that if $\calU$ is a separable metric space, $\Pi \subset \calM(\calU)$ is tight if and only if its closure is relatively compact.
Note that $\X^\bbN\times\Y^\bbN$ is complete and separable when equipped with the metric
\begin{equation*}
d((\bfx^1, \bfy^1), (\bfx^2, \bfy^2)) = \sum\limits_{k=0}^\infty 2^{-k} \delta((x^1_k, y^1_k)\neq (x^2_k, y^2_k)).
\end{equation*}
Finally, we remark that since $c: \X\times\Y \rightarrow \bbR_+$ is continuous and bounded, $\tilde{c}(\bfx, \bfy) = c(x_0, y_0)$ is as well.

\subsection{Existence for the OTC Problem}
We begin by proving that $\tcrv$ is weakly compact.
\begin{lem}\label{lemma:weak_compactness_of_tc}
$\pitc(\bbP, \bbQ)$ is weakly compact.
\end{lem}
\begin{proof}
By \cite[Lemma 4.4]{villani2008optimal}, $\Pi(\bbP, \bbQ)$ is tight.
Since $\tcrv \subset \Pi(\bbP, \bbQ)$, $\tcrv$ is tight as well.
Thus by Prohorov's theorem, the closure of $\tcrv$ is weakly compact.
So we need only prove that $\tcrv$ is closed.
Take a sequence $\{\pi^n\} \subset \pitc(\bbP, \bbQ)$ such that $\pi^n \Rightarrow \pi \in \calM(\X^\bbN\times\Y^\bbN)$.
Since $\Pi(\bbP, \bbQ)$ is weakly compact \citep{villani2008optimal}, $\pi \in \Pi(\bbP, \bbQ)$.
Then it suffices to prove that $\pi$ is stationary, Markov, and has a transition matrix that satisfies the transition coupling property.

We begin by proving that $\pi$ is stationary.
Let $\sigma: \X^\bbN\times\Y^\bbN \rightarrow \X^\bbN\times\Y^\bbN$ be the left-shift map defined for every $(\bfx, \bfy) \in \X^\bbN\times\Y^\bbN$ by $\sigma(\bfx, \bfy) = (x_1^\infty, y_1^\infty)$.
Then stationarity of any $\mu \in \calM(\X^\bbN\times\Y^\bbN)$ is defined by $\mu = \mu \circ \sigma^{-1}$.
Since each $\pi^n$ is stationary, $\pi^n = \pi^n\circ \sigma^{-1}$.
Noting that $\sigma$ is continuous, the continuous mapping theorem implies that $\pi^n \circ \sigma^{-1} \Rightarrow \pi \circ \sigma^{-1}$, so $\pi^n \Rightarrow \pi \circ \sigma^{-1}$.
Since weak limits are unique, we conclude that $\pi = \pi \circ \sigma^{-1}$ and $\pi$ is stationary.

Next we prove that $\pi$ is Markov.
Since $\X\times\Y$ is finite, for any cylinder set $[s_0^k] = \{(\bfx, \bfy) \in (\X \times \Y)^\bbN: (x_j, y_j) = s_j, 0 \leq j \leq k\}$, $\pi^n([s_0^k]) \rightarrow \pi([s_0^k])$.
Then
\begin{equation}\label{eq:convergence_of_transitions1}
\frac{\pi^n([s_0\cdots s_k])}{\pi^n([s_0\cdots s_{k-1}])} \rightarrow \frac{\pi([s_0 \cdots s_k])}{\pi([s_0\cdots s_{k-1}])}
\end{equation}
and
\begin{equation}\label{eq:convergence_of_transitions2}
\frac{\pi^n([s_{k-1} s_k])}{\pi^n([s_{k-1}])} \rightarrow \frac{\pi([s_{k-1} s_k])}{\pi([s_{k-1}])},
\end{equation}
where we let $\nicefrac{0}{0} = 0$.
But since $\pi^n$ is Markov for each $n \geq 1$,
\begin{equation*}
\frac{\pi^n([s_0 \cdots s_k])}{\pi^n([s_0 \cdots s_{k-1}])} = \frac{\pi^n([s_{k-1} s_k])}{\pi^n([s_{k-1}])}.
\end{equation*}
As a result, $\pi([s_0 \cdots s_k])/\pi([s_0 \cdots s_{k-1}]) = \pi([s_{k-1} s_k]) / \pi([s_{k-1}])$.
Thus, $\pi$ is Markov.

Now, we need only show that $\pi$ satisfies the transition coupling property.
Letting $R_n$ and $R$ denote the transition matrices of $\pi^n$ and $\pi$, respectively,  \eqref{eq:convergence_of_transitions1} and \eqref{eq:convergence_of_transitions2} imply that $R_n(s, s') \rightarrow R(s, s')$ for every $s,s' \in \X\times\Y$.
Then for any $(x,y) \in \X\times\Y$ and $y' \in \Y$,
\begin{equation}\label{eq:convergence_of_trans_mat}
\sum\limits_{x'} R_n((x,y), (x',y')) \rightarrow \sum\limits_{x'} R((x,y),(x',y')).
\end{equation}
But as $R_n \in \tc$, $\sum_{x'} R_n((x,y),(x',y')) = Q(y,y')$ and it follows that $\sum_{x'} R((x,y),$ $(x',y')) = Q(y,y')$.
Employing a similar argument to the other marginal of $R$, one may show that in fact $R \in \tc$.
Therefore, $\pi \in \pitc(\bbP, \bbQ)$ and we conclude that $\pitc(\bbP, \bbQ)$ is weakly compact.
\end{proof}

\begin{prop}\label{prop:existence}
The OTC problem \eqref{eq:otc_problem_rv} has a solution.
\end{prop}
\begin{proof}
Let $\{\pi^n\} \subset \pitc(\bbP, \bbQ)$ be a sequence such that
\begin{equation*}
\int \tilde{c} \, d\pi^n \rightarrow \inf\limits_{\pi \in \pitc(\bbP, \bbQ)} \int \tilde{c} \, d\pi.
\end{equation*}
By Lemma \ref{lemma:weak_compactness_of_tc}, $\pitc(\bbP, \bbQ)$ is weakly compact.
Thus, there exists a subsequence $\{\pi^{n_k}\}$ such that $\pi^{n_k} \Rightarrow \pi^*$ for some $\pi^* \in \pitc(\bbP, \bbQ)$.
Since $\tilde{c}$ is continuous and bounded,
\begin{equation*}
\int \tilde{c} \, d\pi^* = \lim\limits_{k\rightarrow\infty} \int \tilde{c} \, d\pi^{n_k} = \inf\limits_{\pi \in \pitc(\bbP, \bbQ)}\int \tilde{c} \, d\pi.
\end{equation*}
Thus $\pi^*$ is an optimal solution for Problem \eqref{eq:otc_problem_rv}.
\end{proof}

\subsection{Existence for the Constrained OTC Problem}\label{app:approx_existence}
We begin by proving that $\tceta$ is convex and compact as a subset of $\bbR^{d^2 \times d^2}$.
\begin{lem}\label{lemma:compactness_of_tceta}
For any $\eta > 0$, the constrained set of transition coupling matrices $\tceta$ is convex and compact.
\end{lem}
\begin{proof}
Fixing $\eta > 0$, we begin by showing that $\tceta$ is convex.
Let $R, R' \in \tceta$, $\lambda \in (0,1)$, and define $R_\lambda := \lambda R + (1 - \lambda) R'$.
Since $\tc$ is convex, $R_\lambda \in \tc$.
Moreover, using the convexity of the KL-divergence, for any $s \in \X\times \Y$,
\begin{align*}
\calK(R_\lambda(s,\cdot) \| P\otimes Q(s,\cdot)) &=\calK(\lambda R(s, \cdot) + (1-\lambda) R'(s,\cdot) \| P\otimes Q(s,\cdot)) \\
&\leq \lambda \calK(R(s,\cdot) \| P\otimes Q (s, \cdot)) +(1 - \lambda) \calK(R'(s,\cdot) \| P\otimes Q(s, \cdot)) \\
&\leq \lambda \eta + (1 - \lambda) \eta \\
&= \eta.
\end{align*}
Thus $R_\lambda \in \tceta$ and we conclude that $\tceta$ is convex.

Next we prove compactness.
Note that as a subset of the compact set $\tc$ we need only show that $\tceta$ is closed.
Let $\{R_n\} \subset \tceta$ be a sequence converging to $R \in \bbR^{d^2 \times d^2}$.
By the compactness of $\tc$, $R \in \tc$.
Now for any $s \in \X\times\Y$, note that $R(s,\cdot)$ is absolutely continuous with respect to $P\otimes Q(s,\cdot)$.
This implies that, for every $s' \in \X \times \Y$,
\begin{equation*}
R(s,s') \log\frac{R(s,s')}{P\otimes Q(s,s')} < \infty,
\end{equation*}
where we let $0\log(0/0) = 0$.
Then $\calK(\cdot \| P\otimes Q(s,\cdot))$ is continuous at $R(s,\cdot)$ and we have that
\begin{equation*}
\calK(R(s,\cdot) \| P\otimes Q(s,\cdot)) = \lim\limits_{n\rightarrow\infty} \calK(R_n(s,\cdot) \| P\otimes Q(s,\cdot)) \leq \eta.
\end{equation*}
Thus $R \in \tceta$ and we conclude that $\tceta$ is compact.
\end{proof}

Next, we show that $\tcetarv$ is weakly compact.

\begin{lem}\label{lemma:compactness_of_entropic_tc}
For any $\eta \geq 0$, $\tcetarv$ is weakly compact.
\end{lem}
\begin{proof}
Let $\{\pi_n\} \subset \pitc^\eta(\bbP, \bbQ)$ be a sequence such that $\pi_n \Rightarrow \pi \in \calM(\X^\bbN\times\Y^\bbN)$.
By Lemma \ref{lemma:compactness_of_tceta}, $\tcrv$ is weakly compact so $\pi \in \tcrv$.
Letting $R$ be the transition matrix of $\pi$, we need only show that $R \in \tceta$.
Letting $R_n$ be the transition matrix of $\pi_n$, it follows from \eqref{eq:convergence_of_trans_mat} that $R_n \rightarrow R$.
Using the weak lower semicontinuity of the KL-divergence, for every $s \in \X\times\Y$,
\begin{equation*}
\calK(R(s,\cdot) \| P \otimes Q(s,\cdot)) \leq \liminf\limits_{n\rightarrow\infty} \calK(R_n(s,\cdot) \|P\otimes Q(s,\cdot)) \leq \eta.
\end{equation*}
Therefore, $R \in \Pi_\eta(P,Q)$ and we find that $\pi \in \pitc^\eta(\bbP, \bbQ)$.
Thus, we conclude that $\pitc^\eta(\bbP, \bbQ)$ is weakly compact.
\end{proof}

\begin{prop}\label{prop:entropic_existence}
For any $\eta > 0$, the constrained OTC problem \eqref{eq:entropic_otc} has a solution.
\end{prop}
\begin{proof}
Let $\{\pi^n\} \subset \pitc^\eta(\bbP, \bbQ)$ be a sequence such that
\begin{equation*}
\int \tilde{c} \, d\pi^n \rightarrow \inf\limits_{\pi \in \pitc^\eta(\bbP, \bbQ)} \int \tilde{c} \, d\pi.
\end{equation*}
By Lemma \ref{lemma:compactness_of_entropic_tc}, $\tcetarv$ is weakly compact.
So there exists a subsequence $\{\pi^{n_k}\}$ such that $\pi^{n_k} \Rightarrow \pi^*$ for some $\pi^* \in \pitc^\eta(\bbP, \bbQ)$.
Since $\tilde{c}$ is continuous and bounded,
\begin{equation*}
\int \tilde{c} \, d\pi^* = \lim\limits_{k\rightarrow\infty} \int \tilde{c} \, d\pi^{n_k} = \inf\limits_{\pi \in \pitc^\eta(\bbP, \bbQ)}\int \tilde{c} \, d\pi.
\end{equation*}
Thus $\pi^*$ is an optimal solution for Problem \eqref{eq:entropic_otc}.
\end{proof}

\subsection{Triangle Inequality}
Next we prove that the optimal transition coupling cost satisfies the triangle inequality when the cost does.
For probability measures $p_1$, $p_2$, $p_3 \in \calM(\X)$, we let $\Pi(p_1, p_2, p_3)$ denote the set of three-way couplings of $p_1$, $p_2$, and $p_3$ defined in the obvious way.
For stationary Markov process measures $\bbP_1$, $\bbP_2$, $\bbP_3 \in \calM(\X^\bbN)$ we let $\Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2, \bbP_3)$ denote the set of three-way transition couplings of $\bbP_1$, $\bbP_2$, and $\bbP_3$, again defined in the obvious way.
If the three process measures have transition matrices $P_1$, $P_2$, and $P_3 \in \bbR^{d\times d}$, we let $\Pi(P_1, P_2, P_3)$ denote the set of three-way transition coupling matrices of $P_1$, $P_2$, and $P_3$.

\begin{lem}[Gluing Lemma]\label{lemma:gluing_lemma}
Let $\bbP_1$, $\bbP_2$, $\bbP_3 \in \calM(\X^\bbN)$ be stationary and irreducible Markov chains with stationary distributions $p_1$, $p_2$, $p_3 \in \calM(\X)$, and let $\pi_{12} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2)$ and $\pi_{23} \in \Pi_{\mbox{\tiny TC}}(\bbP_2, \bbP_3)$.
Then there exists $\pi_{123} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2, \bbP_3)$ such that $\pi_{123}(A_1 \times A_2 \times \X^\bbN) = \pi_{12}(A_1 \times A_2)$ and $\pi_{123}(\X^\bbN \times A_2 \times A_3) = \pi_{23}(A_2 \times A_3)$ for any $A_1$, $A_2$, $A_3 \subset \X^\bbN$.
Furthermore, any stationary distribution $\lambda_{123} \in \calM(\X\times\X\times\X)$ of $R_{123}$ necessarily satisfies $\lambda_{123} \in \Pi(p_1, p_2, p_3)$.
\begin{proof}
Let $\bbP_1$, $\bbP_2$, $\bbP_3$, $\pi_{12}$ and $\pi_{23}$ have transition matrices $P_1$, $P_2$, $P_3$, $R_{12}$ and $R_{23}$, respectively.
By the gluing lemma for optimal couplings \citep{villani2008optimal}, for every $x_1$, $x_2$, $x_3 \in \X$, there exists a coupling $r_{(x_1, x_2, x_3)} \in \Pi(P_1(x_1, \cdot), P_2(x_2, \cdot), P_3(x_3, \cdot))$ such that
\begin{equation*}
\sum_{\tilde{x}_3} r_{(x_1, x_2, x_3)}(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3) = R_{12}((x_1, x_2), (\tilde{x}_1, \tilde{x}_2))
\end{equation*}
and
\begin{equation*}
\sum_{\tilde{x}_1} r_{(x_1, x_2, x_3)}(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3) = R_{23}((x_2, x_3), (\tilde{x}_2, \tilde{x}_3)).
\end{equation*}
Let $R_{123} \in \bbR^{d^3 \times d^3}$ be the transition matrix such that for every $(x_1, x_2, x_3), (\tilde{x}_1, \tilde{x}_2, \tilde{x}_3) \in \X \times \X \times \X$, $R_{123}((x_1, x_2, x_3), (\tilde{x}_1, \tilde{x}_2, \tilde{x}_3)) = r_{(x_1, x_2, x_3)}(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3)$.
By construction, $R_{123} \in \Pi(P_1, P_2, P_3)$ and we may let $\pi_{123}$ be the stationary Markov process measure constructed from $R_{123}$ and some stationary distribution $\lambda_{123} \in \calM(\X\times\X\times\X)$ of $R_{123}$.
To see that $\lambda_{123} \in \Pi(p_1, p_2, p_3)$, let the first $\X$-marginal of $\lambda_{123}$ be $\tilde{p}_1 \in \calM(\X)$.
Then for every $x_1 \in \X$,
\begin{align*}
\tilde{p}_1(x_1) &= \sum\limits_{x_2, x_3} \lambda_{123}(x_1, x_2, x_3) \\
&= \sum\limits_{x_2, x_3} \sum\limits_{\tilde{x}_1, \tilde{x}_2, \tilde{x}_3} \lambda_{123}(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3) \times R_{123}((\tilde{x}_1, \tilde{x}_2, \tilde{x}_3), (x_1, x_2, x_3)) \\
&= \sum\limits_{\tilde{x}_1, \tilde{x}_2, \tilde{x}_3} \lambda_{123}(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3) P_1(\tilde{x}_1, x_1) \\
&= \sum\limits_{\tilde{x}_1} \tilde{p}_1(\tilde{x}_1) P_1(\tilde{x}_1, x_1),
\end{align*}
so $\tilde{p}_1$ is stationary with respect to $P_1$.
Since $\bbP_1$ is irreducible, the stationary distribution of $P_1$ is unique and it follows that $\tilde{p}_1 = p_1$.
Repeating the argument for the second and third marginals, it follows that $\lambda_{123} \in \Pi(p_1, p_2, p_3)$ and thus $\pi_{123} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2, \bbP_3)$.
\end{proof}
\end{lem}

\begin{figure*}[t]
\begin{equation*}
R = \kbordermatrix{& (0, 0) & (0, 1)& (0,2)&(1,0)&(1,1)&(1,2)&(2,0)&(2,1)&(2,2) \\ (0, 0) & 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0.50 \\ (0,1) & 0 & 0 & 0.25 & 0 & 0 & 0.25 & 0.25 & 0.25 & 0 \\ (0,2) & 0 & 0 & 0.25 & 0.25 & 0 & 0 & 0.25 & 0.25 & 0 \\ (1,0) & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0.25 & 0.25 \\ (1,1) & 0 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0.25 & 0.25 \\ (1,2) & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0.50 & 0 & 0 \\ (2,0)& 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0.50 \\ (2,1) & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0.25 & 0.25 \\ (2,2) & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0.50 & 0 & 0}.
\end{equation*}
\caption{A reducible transition coupling of irreducible transition matrices $P$ and $Q$ defined in \eqref{eq:trans_mat_1} and \eqref{eq:trans_mat_2}, respectively.}
\label{fig:reducible_trans_coup}
\end{figure*}

\begin{prop}[Triangle Inequality]\label{prop:triangle_ineq}
Let $\bbP_1$, $\bbP_2$, $\bbP_3 \in \calM(\X^\bbN)$ be stationary and irreducible Markov chains and let $\tilde{c}(\bfx, \tilde{\bfx}) = c(x_0, \tilde{x}_0)$ for every $\bfx$, $\tilde{\bfx} \in \X^\bbN$.
If $c$ satisfies the triangle inequality, then the OTC problem satisfies
\begin{equation}\label{eq:otc_triangle_ineq}
\begin{split}
\min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_3)} \int \tilde{c} \, d\pi \leq \min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2)} \int \tilde{c} \, d\pi + \min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_2, \bbP_3)} \int \tilde{c} \, d\pi.
\end{split}
\end{equation}
\end{prop}
\begin{proof}
By Proposition \ref{prop:existence}, there exist $\pi_{12} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2)$ and $\pi_{23} \in \Pi_{\mbox{\tiny TC}}(\bbP_2, \bbP_3)$ that are optimal in the two problems on the right hand side of \eqref{eq:otc_triangle_ineq}.
Then by Lemma \ref{lemma:gluing_lemma}, there exists $\pi_{123} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2, \bbP_3)$ that admits $\pi_{12}$ and $\pi_{23}$ as $(\X\times\X)^\bbN$-marginals.
Define the measure $\pi_{13} \in \calM((\X\times\X)^\bbN)$ by $\pi_{13}(A_1 \times A_3) = \pi_{123}(A_1 \times \X^\bbN \times A_3)$ for every $A_1$, $A_3 \subset \X^\bbN$.
Clearly, $\pi_{13} \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_3)$.
Moreover, $\tilde{c}$ satisfies the triangle inequality on $(\X\times\X)^\bbN$ since $c$ satisfies it on $\X\times\X$.
Thus,
\begin{align*}
\min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_3)} \int \tilde{c} \, d\pi &\leq \int_{(\X\times\X)^\bbN} \tilde{c}(\bfx_1, \bfx_3) \, d\pi_{13}(\bfx_1, \bfx_3) \\
&= \int_{(\X\times\X\times\X)^\bbN} \tilde{c}(\bfx_1, \bfx_3) \, d\pi_{123}(\bfx_1, \bfx_2, \bfx_3) \\
&\leq \int_{(\X\times\X\times\X)^\bbN} (\tilde{c}(\bfx_1, \bfx_2) + \tilde{c}(\bfx_2, \bfx_3)) \, d\pi_{123}(\bfx_1, \bfx_2, \bfx_3) \\
&= \int_{(\X\times\X)^\bbN} \tilde{c}(\bfx_1, \bfx_2) \, d\pi_{12}(\bfx_1, \bfx_2) + \int_{(\X\times\X)^\bbN} \tilde{c}(\bfx_2, \bfx_3) \, d\pi_{23}(\bfx_2, \bfx_3) \\
&= \min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_1, \bbP_2)} \int \tilde{c} \, d\pi + \min\limits_{\pi \in \Pi_{\mbox{\tiny TC}}(\bbP_2, \bbP_3)} \int \tilde{c} \, d\pi.
\end{align*}
\end{proof}

\section{Reducible Transition Coupling of Irreducible Chains}\label{sec:redicible_tc}
In this appendix, we provide an example showing that a transition coupling of two irreducible transition matrices is not necessarily irreducible.
Let
\begin{equation}\label{eq:trans_mat_1}
P = \kbordermatrix{&0 & 1 & 2 \\ 0 & 0.25 & 0.25 & 0.50 \\ 1 & 0.25 & 0.25 & 0.50 \\ 2& 0.25 & 0.25 & 0.50}
\end{equation}
and
\begin{equation}\label{eq:trans_mat_2}
Q = \kbordermatrix{&0 & 1 & 2 \\ 0 & 0.25 & 0.25 & 0.50 \\ 1 & 0.25 & 0.25 & 0.50 \\ 2 & 0.50 & 0.25 & 0.25}.
\end{equation}
Both $P$ and $Q$ are clearly irreducible, but the transition coupling $R$, given in Figure \ref{fig:reducible_trans_coup}, is reducible.

While we do not provide an example here, we remark that transition coupling matrices of aperiodic and irreducible transition matrices may also have multiple recurrent classes.

\section{Comparison to 1-step Optimal Transition Coupling}
\label{app:one_step}
In this appendix, we demonstrate how the 1-step transition coupling problem described in Section \ref{sec:background_on_otc} prioritizes expected cost in the next step over long-term average cost as the OTC problem does.

\begin{ex}
\label{ex:greedyotc_comparison}
Consider stationary Markov chains $X$ and $Y$ with transition distributions defined by the graphs in Figure \ref{fig:greedy_otc_marginals}.
In order to find an OTC of $X$ and $Y$, we must specify a cost for every pair of states $(x, y) \in \X\times\Y$.
Let states $(0,0)$, $(1,2)$, $(2,1)$, $(2,2)$, and $(3,3)$ have cost 0, states $(1,1)$, $(3, 4)$ and $(4, 3)$ have cost 1,
state $(4,4)$ have cost 9, and let all other states have a cost sufficiently large 1-step OTC and OTC do not assign
them positive probability.

\begin{figure}[h]
\centering
\begin{subfigure}{0.45\linewidth}
\centering

\scalebox{0.5}{
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (0) {0};
  \node[main node] (1) [right of=0, above of=0]{1};
  \node[main node] (2) [right of=0, below of=0]{2};
  \node[main node] (3) [right of=1]{3};
  \node[main node] (4) [right of=2]{4};

  \path[every node/.style={font=\sffamily\small}]
    (0) edge [right] node[above, left] {0.25} (1)
    (0) edge [right] node[below, left] {0.75} (2)
    (1) edge [right] node[above] {1} (3)
    (2) edge [right] node[above] {1} (4);

\end{tikzpicture}
}
\vspace{5mm}
\caption{$X$ transition probabilities}
\end{subfigure}
\begin{subfigure}{0.45\linewidth}
\centering

\scalebox{0.5}{
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (0) {0};
  \node[main node] (1) [right of=0, above of=0]{1};
  \node[main node] (2) [right of=0, below of=0]{2};
  \node[main node] (3) [right of=1]{3};
  \node[main node] (4) [right of=2]{4};

  \path[every node/.style={font=\sffamily\small}]
    (0) edge [right] node[above, left] {0.5} (1)
    (0) edge [right] node[below, left] {0.5} (2)
    (1) edge [right] node[above] {1} (3)
    (2) edge [right] node[above] {1} (4);

\end{tikzpicture}
}
\vspace{5mm}
\caption{$Y$ transition probabilities}
\end{subfigure}
\caption{Marginal stationary Markov chains.
Both chains return to state $0$ from states $3$ and $4$ with probability one.}
\label{fig:greedy_otc_marginals}
\end{figure}
\noindent
The transition distributions of the OTC and 1-step OTC are largely the same except for the transitions from $(0, 0)$ to  $(1, 1)$, $(1, 2)$, $(2, 1)$ and $(2,2)$ (see Figure \ref{fig:greedy_otc} for an illustration).
In particular, since the OTC chooses the transitions to minimize expected cost over the complete trajectory of the chain, it assigns lower probability to the transition $(0, 0) \rightarrow (2, 2)$ in order to avoid the costly state $(4, 4)$.
On the other hand, the 1-step OTC does not utilize this information in deciding how to transition from $(0, 0)$ and assigns a higher probability to the transition $(0, 0) \rightarrow (2, 2)$.
As a result, the expected cost of the 1-step OTC is $5/3$ compared to an expected cost of $1$ for the OTC.
In fact, by increasing the cost of the state $(4, 4)$, one can make the difference between the 1-step OTC and OTC costs arbitrarily large.
The lower expected cost indicates that the OTC constitutes a better alignment of $X$ and $Y$ as compared to the 1-step OTC.

\begin{figure}[h]
\centering
\begin{subfigure}{0.45\linewidth}
\centering

\scalebox{0.5}{
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (00) {(0,0)};
  \node[main node] (12) [right of=0, above of=0]{(1,2)};
  \node[main node] (21) [right of=0]{(2,1)};
  \node[main node] (22) [right of=0, below of=0]{(2,2)};
  \node[main node] (11) [above of=12]{(1,1)};
  \node[main node] (34) [right of=12]{(3,4)};
  \node[main node] (43) [right of=21]{(4,3)};
  \node[main node] (44) [right of=22]{(4,4)};
  \node[main node] (33) [above of=34]{(3,3)};

  \path[every node/.style={font=\sffamily\small}]
	(00) edge [right] node[above, left] {0.25} (11)
	(00) edge [right] node[above] {0.25} (21)
	(00) edge [right] node[below, left] {0.5} (22)
	(11) edge [right] node[above] {1} (33)
	(12) edge [right] node[above] {1} (34)
	(21) edge [right] node[above] {1} (43)
	(22) edge [right] node[above] {1} (44);

\end{tikzpicture}

}
\vspace{5mm}
\caption{1-step OTC (expected cost of $5/3$)}
\label{fig:greedy_otc_1}
\end{subfigure}
\begin{subfigure}{0.45\linewidth}
\centering

\scalebox{0.5}{
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (00) {(0,0)};
  \node[main node] (12) [right of=0, above of=0]{(1,2)};
  \node[main node] (21) [right of=0]{(2,1)};
  \node[main node] (22) [right of=0, below of=0]{(2,2)};
  \node[main node] (11) [above of=12]{(1,1)};
  \node[main node] (34) [right of=12]{(3,4)};
  \node[main node] (43) [right of=21]{(4,3)};
  \node[main node] (44) [right of=22]{(4,4)};
  \node[main node] (33) [above of=34]{(3,3)};

  \path[every node/.style={font=\sffamily\small}]
	(00) edge [right] node[above, left] {0.25} (12)
	(00) edge [right] node[above] {0.5} (21)
	(00) edge [right] node[below, left] {0.25} (22)
	(11) edge [right] node[above] {1} (33)
	(12) edge [right] node[above] {1} (34)
	(21) edge [right] node[above] {1} (43)
	(22) edge [right] node[above] {1} (44);

\end{tikzpicture}
}
\vspace{5mm}
\caption{OTC (expected cost of $1$)}
\label{fig:greedy_otc_2}
\end{subfigure}
\caption{An example where the 1-step OTC has sub-optimal expected cost. Both chains return to state $(0, 0)$ from states $(3, 3)$, $(3, 4)$, $(4, 3)$, and $(4, 4)$ with probability one.
Note that Figures \ref{fig:greedy_otc_1} and \ref{fig:greedy_otc_2} omit the edges that are the same between the two transition couplings.}
\label{fig:greedy_otc}
\end{figure}
\end{ex}

\clearpage


TITLE: probability that minimum value in set A is larger than maximum value in set B
QUESTION [3 upvotes]: There are two sets, called $A$ and $B$ which have $K$ number of elements, respectively.
Each element in both group follows one of two exponential distribution.
One is $f_X(x) = \alpha e^{-\alpha x}$ (easily called alpha exponential), the other is $f_X(x) = \beta e^{-\beta x}$ (beta exponential), where $\beta \ll \alpha$ and $\alpha,\beta > 0$.
Each element in set $A$ follows alpha exponential with probability 0.2 and follow beta exponential with probability 0.8.
Also, each element in set $B$ follow alpha exponential with probability 0.8 and follow beta exponential with probability 0.2.
I want to find the probability that the smallest elements in set $A$ is larger than the largest value in set $B$.
How can I find the probability that the smallest elements in group A is larger than the largest value in group $B$?

REPLY [2 votes]: Let $A_1,\ldots, A_K$ be i.i.d. random variables with density
$$
f_A(t) = \frac15\alpha e^{-\alpha t} + \frac45\beta e^{-\beta t}
$$
and $B_1,\ldots, B_K$ be i.i.d. random variables, independent of the $A_i$, with density
$$
f_B(t) = \frac45\alpha e^{-\alpha t} + \frac15\beta e^{-\beta t}.
$$
The corresponding distribution functions are
$$
F_A(t) = 1 - \left(\frac15\alpha e^{-\alpha t} + \frac45\beta e^{-\beta t}\right),\quad F_B(t) = 1-\left(\frac45\alpha e^{-\alpha t} + \frac15\beta e^{-\beta t}\right).
$$
Let $\mathcal A=\min_i A_i$ and $\mathcal B=\max_i B_i$. Then
\begin{align}
\mathbb P(\mathcal A>t) &= \mathbb P\left(\bigcap_{i=1}^K \{A_i > t\} \right)\\
&= \prod_{i=1}^K \mathbb P(A_i>t)\\
&= \left(\frac15\alpha e^{-\alpha t} + \frac45\beta e^{-\beta t}\right)^K,
\end{align}
so the distribution function of $\mathcal A$ is
$$
F_{\mathcal A}(t) = 1 - \left(\frac15\alpha e^{-\alpha t} + \frac45\beta e^{-\beta t}\right)^K.
$$
By a similar computation we find that
$$
F_{\mathcal B}(t) = \left(1-\left(\frac45\alpha e^{-\alpha t} + \frac15\beta e^{-\beta t}\right)\right)^K.
$$
We then compute the probability of $\{\mathcal A\leqslant B\}$ by integrating over the joint density:
\begin{align}
\mathbb P(\mathcal A\leqslant B\} &= \int_0^\infty \int_0^\infty f_{\mathcal A}(s)f_{\mathcal B}(t)\mathsf 1_{s\leqslant t}\ \mathsf ds\ \mathsf dt\\
&=\int_0^\infty \int_0^t f_{\mathcal A}(s)f_{\mathcal B}(t)\mathsf 1_{s\leqslant t}\ \mathsf ds\ \mathsf dt\\
&= \int_0^\infty \int_0^t K \left(\frac{1}{5} \alpha ^2 e^{-\alpha s}\frac{4}{5} \beta ^2 e^{-\beta s}\right) \left(\frac{1}{5} \alpha  e^{-\alpha s}+\frac{4}{5} \beta  e^{-\beta s}\right)^{K-1}\cdot\\
&\quad\quad\quad\quad\quad\! K \left(\frac{4}{5} \alpha ^2 e^{-\alpha t}+\frac{1}{5} \beta ^2 e^{-\beta t}\right) \left(1-\frac{1}{5} 4 \alpha  e^{-\beta t}-\frac{1}{5} \beta  e^{-\beta t}\right)^{K-1}\mathsf ds\ \mathsf dt.
\end{align}
I was not able to evaluate this integral with Mathematica, however.


text:
\begin{definition}[Definition:Consistent (Logic)/Proof System/Propositional Logic/Definition 2]
Suppose that in $\mathscr P$, the [[Rule of Explosion/Variant 3|Rule of Explosion (Variant 3)]] holds.
Then $\mathscr P$ is '''consistent''' {{iff}}:
:For every [[Definition:Logical Formula|logical formula]] $\phi$, not ''both'' of $\phi$ and $\neg \phi$ are [[Definition:Theorem (Formal Systems)|theorems]] of $\mathscr P$
\end{definition}

config: wiki


TITLE: Are there any ways to turn natural density into a measure?
QUESTION [4 upvotes]: Natural density measures how fat a subset of natural numbers is. The definition can be seen in https://en.wikipedia.org/wiki/Natural_density#Definition.
However, natural density is only a outer measure. Is there any ways to make it a measure? For example, would it be a measure under some domain restriction?

REPLY [3 votes]: Note if it was a turned into a (countably additive) measure, then $\mu(\{n\}) = 0$ for all $n \in \mathbb{N}$, which would mean $\mu(\mathbb{N}) = 0$, which I don't think you want. However, one wonders if you can turn it into a finitely additive measure. And indeed, finitely additive, shift invariant measures on $\mathbb{N}$ do exist, and they equal the natural density on subsets where the natural density exists. One way to construct this measure is to actually create it out of natural density, by viewing natural density as a linear functional on a certain subspace of $[0,1]^\mathbb{N}$ (where $A \subseteq \mathbb{N} \sim (1_A(n))_{n=1}^\infty$), and then extending it to a linear functional on all of $[0,1]^\mathbb{N}$ via Hahn-Banach.


TITLE: What does it mean when a topology has a non-trivial countable base?
QUESTION [0 upvotes]: I recently found that the standard topology has a countable base by utilizing the density of the rationals. Are there topologies that cannot have a countable base? If so, what makes them so different that they cannot have a countable base?

REPLY [0 votes]: Examples of spaces without countable bases are
the ordinals $\omega_n$ for nonzero n,
uncountable discrete spaces.
2nd countable (has countable base) compact spaces have the property that every sequence has a convergent subsequence.


text:
\section{Preliminaries}
Here, we recall the definitions of nonlinear negative-imaginary systems and nonlinear output strictly negative-imaginary systems.

Consider the following general nonlinear system:
\begin{align}
    \dot x(t)=&\ f(x(t),u(t));\label{eq:state equation of nonlinear OSNI}\\
    y(t)=&\ h(x(t))\label{eq:output equation of nonlinear OSNI}
\end{align}
where $f:\mathbb R^n\times \mathbb R^m \to \mathbb R^n$ is a Lipschitz continuous function and $h:\mathbb R^n \to \mathbb R^m$ is a class $C^1$ function.
\begin{definition}\cite{shi2020robust}\label{def:nonlinear NI}
The system (\ref{eq:state equation of nonlinear OSNI}), (\ref{eq:output equation of nonlinear OSNI}) is said to be a nonlinear negative-imaginary system if there exists a positive definite storage function $V:\mathbb R^n\to \mathbb R$ of class $C^1$ such that
\begin{equation}\label{eq:NI MIMO definition inequality}
    \dot V(x(t))\leq u(t)^T\dot y(t),\qquad \forall t\geq 0.
\end{equation}
\end{definition}

\begin{definition}\cite{shi2020robust}\label{def:nonlinear OSNI}
The system (\ref{eq:state equation of nonlinear OSNI}), (\ref{eq:output equation of nonlinear OSNI}) is said to be a nonlinear output strictly negative-imaginary system if there exists a positive definite storage function $V:\mathbb R^n\to\mathbb R$ of class $C^1$ and a constant $\epsilon>0$ such that
\begin{equation}\label{eq:dissipativity of OSNI}
    \dot V(x(t))\leq u(t)^T\dot y(t) -\epsilon \left|\dot y(t)\right|^2, \qquad \forall t\geq 0.
\end{equation}
The quantity $\epsilon$ describes the level of output strictness of the system.
\end{definition}

config: arxiv


TITLE: factor $x^9 + 243x^3 + 729$
QUESTION [1 upvotes]: Factor the polynomial $$x^{9} + 243x^{3} + 729$$
it might be helpful to see it like this $$x^{9}+3^{5}x^{3}+3^{6}$$
I would imagine this being done without a calculator, but I don't see how to do it.

REPLY [7 votes]: Observe that $x^9+243x^3+729$ = $(x^3+9)^3 - 27x^6$ = $(x^3+9)^3-(3x^2)^3$.
Now using the formula for difference of cubes we obtain:
$(x^3+9)^3-(3x^2)^3$ = $(x^3+9-3x^2)((x^3+9)^2+(x^3+9)3x^2+(3x^2)^2)$ .
Doing the calculations on the second parenthesis and reordering the terms we get that:
$x^9+243x^3+729 = (x^3 - 3 x^2 + 9) (x^6 + 3 x^5 + 9 x^4 + 18 x^3 + 27 x^2 + 81)$


TITLE: Can we use metatheory of set theory for proof statements in set theory?
QUESTION [0 upvotes]: I wanna know if is possible or have examples of theorems in set theory, for example $\beta$, that have a demonstration of forme
$Cons(ZFC)\Rightarrow \beta$
but $\beta$ is independent of axioms of $ZFC$.

REPLY [2 votes]: Yes, it is possible.  You can add $Con(ZFC)$ as an assumption.  If you then derive $\beta$ you have proven within $ZFC$ that $Con(ZFC)\implies \beta$.  If you can then prove that $\beta$ is not provable from $ZFC$ you are there.
A trivial example is to take $\beta = Con(ZFC)$.  Then ordinary logic proves $Con(ZFC) \implies \beta$ even without $ZFC$.