On Stein's method for stochastically monotone single-birth chains (Q6152250)

The paper discusses Stein's method in the special case of \textit{single-birth Markov chains} -- that is, a chain on \(\mathbb N = \{0, 1, 2, \dots\}\) which cannot jump more than \(1\) in the positive direction, and makes this jump with positive probability. Formally, it is a Markov chain with transition matrix \(P = (p_{i,j})_{i,j \in \mathbb N}\) satisfying \(p_{i,j} = 0\) if \(j > i+1\) and \(p_{i,i+1} > 0\) for all \(i \in \mathbb N\); \(p_{i,j} > 0\) for some \(j < i\) is allowed. It is assumed that an equilibrium distribution \(\pi\) exists. Bounds on the increments of the solution to Poisson's equation are derived for such a process. Namely, for a given function \(h : \mathbb N \to \mathbb R\), \textit{Poisson's equation} is \[ h(i) - \mathbb E[ h(\pi) ] = f(i) - (Pf)_i \quad\text{for all}\quad i \in \mathbb N \quad\text{for}\quad f : \mathbb N \to \mathbb R. \] For the avoidance of doubt, \(\mathbb E[ h(\pi) ] = \sum_{j=0}^\infty \pi_j h(j)\) and \((Pf)_i = \sum_{j=0}^\infty P_{i,j} f(j)\) for \(i \in \mathbb N\). The \textit{increments} of a solution \(f\) are \(f(i+1) - f(i)\) for \(i \in \mathbb N\). The bounds on the increments are used to control the convergence rate to equilibrium, measured in total variation. The \textit{total variation} distance between two distributions \(\mu\) and \(\pi\) on a discrete state space \(\Omega\) is defined by \[ d_\mathsf{TV}(\mu, \pi) := \max_{A \subseteq \Omega} | \mu(A) - \pi(A) |; \] it measures the amount that a statistic \(A\) can distingush \(\mu\) and \(\pi\). A duality standard argument gives an equivalent formulation: \[ d_\mathsf{TV}(\mu, \pi) = \sup_{h \in H} | \mathbb E[h(\mu)] - \mathbb E[h(\pi)] | \quad\text{where}\quad H := \{ h : \Omega \to \mathbb R \mid \| h \|_\infty \leq 1 \}. \] Following Stein's method, this is bounded by rewriting this last right-hand side using Poisson's equation: \[ \mathbb E[h(\mu)] - \mathbb E[h(\pi)] = \mathbb E[f(\mu)] - \mathbb E[(Pf)_\mu], \] and gathering this under a single sum; see the text immediately before Theorem 1.1 for details. In particular, for single-birth chains, Theorem 1.1 provides the bound \[ d_\mathsf{TV}(\mu, \pi) \leq \textstyle \sum_{j=0}^\infty | \mathbb P(\mu > j) - \sum_{k > j} \sum_{i \in \mathbb N} \mathbb P(\mu = i) p_{i,k} | \displaystyle \cdot \sup_{h \in H} \sup_{i \in \mathbb N} | m_i(h) |, \] where \(m_i(h)\) is an explicity function given by (1.2). This function is then bounded in the case of birth-death chains, including single-server queueing systems. If \(\mu\) is the law of a Markov chain \(X = (X_t)_{t \in \mathbb N}\) evaluated at time \(t\), then \[ \textstyle \sum_{k > j} \sum_{i \in \mathbb N} \mathbb P(\mu = i) p_{i,k} = \sum_{k > j} \sum_{i \in \mathbb N} \mathbb P(X_t = i) p_{i,k} = \sum_{k > j} \mathbb P(X_{t+1} = k) = \mathbb P(X_{t+1} > j). \] When the chain is \textit{stochastically monotone}, \(\mathbb P(X_{t+1} > j) \geq \mathbb P(X_t > j)\) for all \(j, t \in \mathbb N\). Hence, the absolute values can be removed from the TV bound: \[ d_\mathsf{TV}(X_t, \pi) \leq \bigl( \mathbb E[X_{t+1}] - \mathbb E[X_t] \bigr) \cdot \sup_{h \in H} \sup_{i \in \mathbb N} | m_i(h) |. \] Related bounds are established to compare the TV distance between the equilibrium distributions of two single-birth Markov chains in the case where one transition matrix dominates the other. To be explicity, transition matrix \(P = (p_{i,j})_{i,j \in \mathbb N}\) \textit{dominates} \(Q = (q_{i,j})_{i,j \in \mathbb N}\) if \[ \textstyle \sum_{j > k} p_{i,j} > \sum_{j > k} q_{i,j} \quad\text{for all}\quad i,k \in \mathbb N. \]