Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Classical Markov monogamy for every permutation

Abstract

The diagonal sum of mutual informations dominates every permuted sum along a finite classical Markov chain.

Definition 1.1 (Successive transition matrices).

Formalization. D5/S3/Entropy/MarkovMonogamyPermutationInequality.composedTransition (✓ std3).

Source. Repository-derived.

Acknowledgement. Matheus Capela; Lucas C. Céleri; Rafael Chaves; Kavan Modi (2022). Quantum Markov monogamy inequalities. DOI: 10.1103/PhysRevA.106.022218. URL: https://arxiv.org/abs/2108.11533v4.

Commentary.

For a family of finite alphabets α, the transition from position s to position t is the product of the successive matrices k at positions s through t − 1. The recursion starts with the identity matrix at s and appends one matrix by summing over the intermediate letter c. No positivity or normalization is part of this definition. The order condition supplies the implicit proof argument of composedTransition and Nat.leRecOn. The construction describes successive transitions for the Markov condition in Section II of the source (PRA-v1.tex, lines 119–126).

Definition 1.2 (The permutation inequality).

Formalization. D5/S3/Entropy/MarkovMonogamyPermutationInequality.claim (✓ std3).

Source. Repository-derived.

Acknowledgement. Matheus Capela; Lucas C. Céleri; Rafael Chaves; Kavan Modi (2022). Quantum Markov monogamy inequalities. DOI: 10.1103/PhysRevA.106.022218. URL: https://arxiv.org/abs/2108.11533v4.

Commentary.

Choose a probability mass p at position zero and stochastic matrices k between the first 2n positions. Position n − 1 − i.val represents X with one-based index i.val + 1, and position n + i.val represents the corresponding Y. The first mixture transports p to the X position; mixtureJoint combines that law with the transition to the chosen Y position. Thus each summand is the mutual information, in nats, of the indicated pair. Fin.val explicitly converts each finite index to a natural number, and subtraction is natural subtraction. Order proofs in composedTransition are implicit. For positive n this is the finite-alphabet reading of Conjecture 1 (PRA-v1.tex, lines 153–159), whose mutual information is defined at line 143. The statement also includes n = 0, when both sums are empty. No restriction is imposed on transitions outside these 2n positions.

Theorem 1.3 (The diagonal pairing maximizes the information sum).

Proof. Machine-checked in Lean as D5/S3/Entropy/MarkovMonogamyPermutationInequality.result (✓ std3). ∎

Resolves. Problems/capela-celeri-chaves-modi-2022-classical-markov-monogamy (proved) by D5/S3/Entropy/MarkovMonogamyPermutationInequality.result.

Source. Repository-derived.

Acknowledgement. Matheus Capela; Lucas C. Céleri; Rafael Chaves; Kavan Modi (2022). Quantum Markov monogamy inequalities. DOI: 10.1103/PhysRevA.106.022218. URL: https://arxiv.org/abs/2108.11533v4.

Commentary.

First establish the elementary laws of successive transitions. At equal positions the transition is the identity matrix. Appending a step multiplies by the next matrix and sums over its input. Induction on the final position, interchange of finite sums and associativity of multiplication show that a transition through an intermediate position is the product of the two composite transitions. A second induction shows that composites of nonnegative matrices with unit row sums again have those properties. Consequently transporting p directly to a position agrees with transporting it first to an intermediate position, and every transported mass is a nonnegative probability law.

The entropy chain rule gives the entropy of a channel joint law: it is the entropy of the input mass plus the input-weighted sum of the row entropies. Apply this to a four-position chain A to B to C to D, with initial law p and stochastic matrices u, v and w. Set r(b) to the sum of p(a)u(a,b), s(a,c) to the sum of u(a,b)v(b,c), t(b,d) to the sum of v(b,c)w(c,d), and z(a,d) to the sum of u(a,b)t(b,d), with each sum over its intermediate letter. These give the pair laws AB, BC, AC, BD and AD, and then the joint laws ABC, ABD, ACD and ABCD. Positivity and unit row sums pass to s, t and z.

Reindex the four-variable law, whose mass is p(a)u(a,b)v(b,c)w(c,d), as a law q on the pair (A,D) and the pair (B,C). Summing its mass gives one. Its two three-variable projections are ABD and ACD, up to coordinate rearrangement, and its first marginal is AD. Finite bijections preserve entropy. Nonnegativity of conditional mutual information for q therefore says that H(ABD) + H(ACD) − H(ABCD) − H(AD) is nonnegative. Expand the first three entropies by the channel chain rule. Summing the AB law against a function of B gives the r-weighted sum; the weighted entropy of w is the same whether its weights come from AC or ABC. These identities cancel the common row-entropy terms, leaving H(AC) − H(AD) + Σ_b r(b)[H(t(b)) − H(v(b))] as the nonnegative defect.

The C marginals of AC and BC agree, and the D marginals of AD and BD agree, by interchanging finite sums. Express the four pair mutual informations as the sum of marginal entropies minus joint entropy, and expand the BC and BD entropies by the same channel rule. Their difference is precisely the remaining nonnegative entropy defect. Hence I(B:C) + I(A:D) ≥ I(B:D) + I(A:C). For any ordered positions a ≤ b ≤ c ≤ d of the original chain, start with the transported law at a and use the three composite transitions from a to b, b to c and c to d. The composition and transport identities identify all four pair laws, so the same rectangle inequality holds at these positions.

Let X_i and Y_a denote positions n − 1 − i.val and n + a.val, and set m(i,a) = I(X_i:Y_a). For i < j and a < b, the four positions n − 1 − j.val, n − 1 − i.val, n + a.val and n + b.val are ordered. They form the chain A = X_j to B = X_i to C = Y_a to D = Y_b. The entropy calculation above identifies the rectangle defect as I(X_i:Y_a) + I(X_j:Y_b) − I(X_i:Y_b) − I(X_j:Y_a) = I(B:C | A,D) ≥ 0. Every transition used precedes the last of these positions, which is less than 2n, so the stated stochasticity hypothesis suffices.

To compare the permutation and diagonal sums for any real matrix m with these ordered rectangles, handle n = 0 by empty sums. For n = N + 1, put c = 1/(N + 1) and give each point e(i) = (i,f(i),i,f(i)) mass c, with zero mass elsewhere. The first coordinate makes e injective, so the masses sum to one. Since f is a permutation, all four coordinate marginals are the same uniform law, with mass c at every element of Fin (N + 1).

The test Φ(x) = m(x(0),x(1)) is supermodular for coordinatewise minimum and maximum. Comparing the orders of the first two coordinates gives equality when their orders agree and the rectangle inequality when they are opposed; equal indices also give equality. Apply common_marginal_supermodular_le_diagonal to this test and the uniform law on the points e(i). Its expectation comparison is c Σ_i m(i,f(i)) ≤ c Σ_i m(i,i). Cancel the positive factor c. For the mutual-information matrix above, this proves that the identity pairing is maximal for every n and every f, as asserted by claim.

References