Conjecture on products of tilted stochastic matrices

A sharp counterexample to reversibility of products of tilted stochastic matrices

Problem: MathDB #358167, Conjecture 1 in Assaf Hallak and Gal Dalal, On the Products of Stochastic and Diagonal Matrices, arXiv:2304.11634, April 2023.

Conclusion: The conjecture is false for every product length at least three, even when the underlying stochastic matrix is symmetric, strictly positive, positive definite, and only three-dimensional. Both the number of factors and the dimension are minimal.

1. Source definitions and the established two-factor case

For a strictly positive vector $u$ and a row-stochastic matrix $P$, write

$$T_P(u)=D(Pu)^{-1}P D(u), \tag{1}$$

where $D(w)$ denotes the diagonal matrix with diagonal $w$. Every row of $T_P(u)$ sums to one.

A row-stochastic matrix $Q$ with strictly positive stationary distribution $\pi$ is reversible when

$$\pi_iQ_{ij}=\pi_jQ_{ji} \qquad\text{for every }i,j. \tag{2}$$

The source proves in Proposition 3 that $T_P(u)$ is reversible whenever $P$ is reversible. Its Proposition 5 further proves that

$$T_P(u)T_P(v)$$

is reversible for any two strictly positive tilt vectors $u,v$. Conjecture 1 asserts that reversibility persists for products of arbitrarily many such factors. We disprove precisely this proposed extension; neither of the established one-factor or two-factor results is contradicted.

2. A strictly positive three-state counterexample

Take

$$P= \frac14 \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2 \end{pmatrix}, \qquad u= \begin{pmatrix}1\\1\\2\end{pmatrix}, \qquad v= \begin{pmatrix}2\\1\\2\end{pmatrix}. \tag{3}$$

Every entry of $P$ is strictly positive, its rows sum to one, and $P=P^{\mathsf T}$. It is therefore reversible with respect to

$$\mu_P=\left(\frac13,\frac13,\frac13\right).$$

In fact, its eigenvalues are $1,1/4,1/4$, so it is also positive definite. The normalizing vectors are

$$Pu= \begin{pmatrix}5/4\\5/4\\3/2\end{pmatrix}, \qquad Pv= \begin{pmatrix}7/4\\3/2\\7/4\end{pmatrix}.$$

Thus the two tilted matrices are

$$U=T_P(u)= \begin{pmatrix} 2/5&1/5&2/5\\ 1/5&2/5&2/5\\ 1/6&1/6&2/3 \end{pmatrix}, \qquad V=T_P(v)= \begin{pmatrix} 4/7&1/7&2/7\\ 1/3&1/3&1/3\\ 2/7&1/7&4/7 \end{pmatrix}. \tag{4}$$

Apply Conjecture 1 to the three strictly positive tilt vectors $u,u,v$. Their product is

$$Q=U^2V= \begin{pmatrix} 587/1575&293/1575&139/315\\ 572/1575&61/315&698/1575\\ 673/1890&173/945&871/1890 \end{pmatrix}. \tag{5}$$

If a strictly positive stochastic matrix is reversible, multiplying the three detailed-balance equations around a directed three-cycle gives Kolmogorov's necessary cycle identity

$$Q_{12}Q_{23}Q_{31} = Q_{13}Q_{32}Q_{21}. \tag{6}$$

But the product in (5) satisfies

$$\begin{aligned} Q_{12}Q_{23}Q_{31} -Q_{13}Q_{32}Q_{21} &= \frac{68818961}{2344190625} -\frac{13754884}{468838125}\\ &= \frac{101}{5315625} >0. \end{aligned} \tag{7}$$

Therefore $Q$ is not reversible. Its unique stationary distribution does exist and is

$$\pi= \frac1{15931}(5790,2965,7176),$$

but detailed balance fails explicitly:

$$\pi_1Q_{12}-\pi_2Q_{21} =\frac{14}{716895}>0. \tag{8}$$

The obstruction is nonreversibility, not nonexistence or nonuniqueness of a stationary distribution.

3. Failure at every product length greater than two

The same fixed strictly positive matrices give counterexamples of every length. For $k\ge2$, put

$$Q_k=U^{k-1}V. \tag{9}$$

Set $r=k-1$. An exact diagonalization of $U$ is

$$U=C \begin{pmatrix} 1/5&0&0\\ 0&4/15&0\\ 0&0&1 \end{pmatrix} C^{-1}, \qquad C= \begin{pmatrix} -1&-6&1\\ 1&-6&1\\ 0&5&1 \end{pmatrix}. \tag{10}$$

Define

$$z=5^{-r}, \qquad w=\left(\frac4{15}\right)^r.$$

Substitution of

$$Q_k=C\operatorname{diag}(z,w,1)C^{-1}V$$

into the cycle expression gives

$$(Q_k)_{12}(Q_k)_{23}(Q_k)_{31} -(Q_k)_{13}(Q_k)_{32}(Q_k)_{21} =\frac{F(z,w)}{1494108}, \tag{11}$$

where

$$F(z,w) =-720w^2z-726w^2+440wz^2+4223wz +2299w-2013z^2-3503z. \tag{12}$$

For $k=2$, direct substitution gives

$$F\left(\frac15,\frac4{15}\right)=0,$$

exactly as required by the source's two-factor theorem.

Suppose now that $k\ge3$, so $r\ge2$. Then

$$0<z\le\frac1{25}, \qquad 0<w\le\frac{16}{225}, \qquad \frac zw=\left(\frac34\right)^r\le\frac9{16}. \tag{13}$$

Dividing (12) by $w$ and discarding its positive summands gives the uniform lower bound

$$\begin{aligned} \frac{F(z,w)}w &= 2299-726w-720wz+440z^2+4223z -\frac zw\left(3503+2013z\right)\\ &\ge 2299-726\frac{16}{225} -720\frac{16}{225}\frac1{25} -\frac9{16}\left(3503+\frac{2013}{25}\right)\\ &= \frac{344393}{1500} >0. \end{aligned} \tag{14}$$

Hence the cycle imbalance in (11) is strictly positive for every $k\ge3$. The conjecture fails at every product length beyond the established two-factor threshold.

4. Sharpness in matrix dimension and extension to every larger dimension

Every strictly positive two-state stochastic matrix has the form

$$R= \begin{pmatrix} 1-a&a\\ b&1-b \end{pmatrix}, \qquad a,b>0,$$

and is reversible with stationary distribution

$$\pi_R=\frac1{a+b}(b,a).$$

Thus no counterexample exists in dimension one or two. By Propositions 3 and 5 of the source, no counterexample exists with one or two tilted factors in any dimension. The three-dimensional, three-factor example (3)–(7) is therefore minimal in both parameters.

For completeness, counterexamples also exist in every dimension $d\ge3$ and at every length $k\ge3$. When $d>3$, start with

$$P_0=P\oplus I_{d-3}, \qquad u_0=(1,1,2,1,\ldots,1)^{\mathsf T}, \qquad v_0=(2,1,2,1,\ldots,1)^{\mathsf T}.$$

At $\varepsilon=0$, the first three states of the product

$$T_{P_0}(u_0)^{k-1}T_{P_0}(v_0)$$

have exactly the strictly positive cycle imbalance in (11). Now perturb to

$$P_{\varepsilon} =(1-\varepsilon)P_0 +\varepsilon\frac{J_d}{d}, \qquad 0<\varepsilon<1, \tag{15}$$

where $J_d$ is the all-ones matrix. This matrix is symmetric, strictly positive, and stochastic. Every tilted entry and every cycle imbalance is continuous at $\varepsilon=0$, because all normalizing coordinates are strictly positive there. Therefore, for all sufficiently small positive rational $\varepsilon$, the same three-state cycle remains unbalanced.

Consequently, within the class of strictly positive reversible stochastic matrices, the universal reversibility assertion holds precisely when either the matrix dimension is at most two or the number of tilted factors is at most two. It fails for every pair of parameters

$$d\ge3, \qquad k\ge3.$$

This resolves the conjecture negatively while preserving, and sharply delimiting, the source's established one-factor and two-factor results.