pith. sign in

arxiv: 2605.24445 · v1 · pith:QZOHGRRHnew · submitted 2026-05-23 · 🧮 math.PR · math.ST· stat.TH

Matrix concentration inequalities for time-inhomogeneous Markov chains

Luca Zanetti This is my paper

Pith reviewed 2026-06-30 12:42 UTC · model grok-4.3

classification 🧮 math.PR math.STstat.TH
keywords matrix concentration inequalitiestime-inhomogeneous Markov chainsOllivier-Ricci curvatureChernoff boundsWasserstein distanceElo rating systemBradley-Terry-Luce model
0
0 comments X

The pith

Chernoff-type bounds hold for the largest eigenvalue of sums of random Hermitian matrices generated by time-inhomogeneous Markov chains under positive Ollivier-Ricci curvature.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves concentration inequalities of Chernoff type for the maximum eigenvalue of sums of random Hermitian matrices whose distribution follows a Markov chain with time-varying transitions. A reader might care because many algorithms and systems, from optimization to sports ranking, use such non-stationary chains, and these bounds provide high-probability guarantees on their aggregate behavior. The main assumption is that each transition kernel contracts the Wasserstein distance between points, a condition called positive Ollivier-Ricci curvature that is often easy to verify even when the chain changes over time. Similar results are given for non-compact spaces using a spectral gap notion for inhomogeneous chains, with an application to the dynamic Elo rating model.

Core claim

We establish Chernoff-type bounds for the largest eigenvalue of sums of Hermitian random matrices generated by a time-inhomogeneous Markov chain. Our primary regime assumes a compact state space and contractivity of each Markov kernel in Wasserstein distance, i.e., positive Ollivier-Ricci curvature. This assumption is convenient to verify in inhomogeneous settings and is satisfied by several chains of practical interest, such as stochastic gradient descent on strongly convex smooth objectives. We also develop analogous bounds for noncompact state spaces under a notion of spectral gap for inhomogeneous chains. Finally, we illustrate the utility of our results through an analysis of the Elo ra

What carries the argument

Chernoff-type bounds for the largest eigenvalue of matrix sums, derived from the contractivity of each Markov kernel in Wasserstein distance (positive Ollivier-Ricci curvature) or from a spectral gap condition for inhomogeneous chains.

If this is right

  • The bounds apply to stochastic gradient descent on strongly convex smooth objectives.
  • The bounds support analysis of the Elo rating system under a dynamic Bradley-Terry-Luce model.
  • High-probability control is available for matrix sums without requiring the chain to be time-homogeneous.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The curvature condition may be checkable in other online learning or recommendation processes that evolve over time.
  • Similar techniques could be tested on simulated inhomogeneous chains to measure how tight the resulting eigenvalue bounds are in practice.
  • The approach opens the possibility of concentration results for other functionals of the matrix sum beyond the largest eigenvalue.

Load-bearing premise

Each Markov kernel is contractive in Wasserstein distance.

What would settle it

A concrete counterexample consisting of a time-inhomogeneous Markov chain without positive curvature for which the largest eigenvalue of the generated matrix sum exceeds the Chernoff bound with non-negligible probability.

read the original abstract

We establish Chernoff-type bounds for the largest eigenvalue of sums of Hermitian random matrices generated by a time-inhomogeneous Markov chain. Our primary regime assumes a compact state space and contractivity of each Markov kernel in Wasserstein distance, i.e., positive Ollivier-Ricci curvature. This assumption is convenient to verify in inhomogeneous settings and is satisfied by several chains of practical interest, such as stochastic gradient descent on strongly convex smooth objectives. We also develop analogous bounds for noncompact state spaces under a notion of spectral gap for inhomogeneous chains introduced by Saloff-Coste and Zuniga. Finally, we illustrate the utility of our results through an analysis of the Elo rating system, a popular method for ranking players in sports analytics, under a dynamic version of the Bradley-Terry-Luce model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper establishes Chernoff-type bounds on the largest eigenvalue of sums of Hermitian random matrices sampled along trajectories of a time-inhomogeneous Markov chain. The primary regime assumes a compact state space and positive Ollivier-Ricci curvature (Wasserstein contractivity) of each kernel; an analogous result is given for non-compact spaces under the Saloff-Coste–Zuniga inhomogeneous spectral gap. The results are illustrated by an analysis of the Elo rating system under a dynamic Bradley-Terry-Luce model.

Significance. If the stated bounds hold with explicit constants, the work supplies a practical extension of matrix concentration inequalities to dependent, time-inhomogeneous sampling. The emphasis on Ollivier-Ricci curvature is a strength: the condition is often easy to check for inhomogeneous kernels and covers examples such as SGD on strongly convex objectives. The application to dynamic ranking models demonstrates concrete utility.

minor comments (2)
  1. The abstract states that the curvature assumption is 'convenient to verify' but does not indicate the explicit form of the resulting concentration bound (e.g., whether the deviation scale depends on the curvature constant or on the number of steps). Adding one sentence clarifying the dependence would help readers assess the result's strength.
  2. Notation for the inhomogeneous spectral gap (Saloff-Coste–Zuniga) is introduced only in the non-compact section; a brief comparison with the curvature regime in the introduction would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of extending matrix concentration inequalities to time-inhomogeneous Markov chains via Ollivier-Ricci curvature, and the recommendation of minor revision. The report correctly identifies the main contributions and the illustrative application to dynamic Bradley-Terry-Luce models.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes Chernoff-type matrix concentration bounds for time-inhomogeneous Markov chains under the external assumption of positive Ollivier-Ricci curvature (Wasserstein contractivity of each kernel) or a spectral gap notion from Saloff-Coste and Zuniga. These are standard, independently defined concepts from prior literature with no indicated self-citation load-bearing on the central claim, no fitted parameters renamed as predictions, and no self-definitional reductions in the stated regime or examples. The derivation chain relies on these external inputs without reducing the main result to its own definitions or prior self-citations by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on two domain assumptions drawn from prior literature; no free parameters or invented entities are visible in the abstract.

axioms (2)
  • domain assumption Each Markov kernel is contractive in Wasserstein distance (positive Ollivier-Ricci curvature)
    Stated as the primary regime that makes the bounds convenient to verify in inhomogeneous settings.
  • domain assumption Spectral gap for inhomogeneous chains as introduced by Saloff-Coste and Zuniga
    Invoked for the noncompact state-space case.

pith-pipeline@v0.9.1-grok · 5652 in / 1276 out tokens · 28973 ms · 2026-06-30T12:42:14.100298+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 22 canonical work pages · 1 internal anchor

  1. [1]

    Strong converse for identification via quantum channels.IEEE Trans

    Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels.IEEE Trans. Inform. Theory, 48(3):569–579, 2002. ISSN0018-9448,1557-9654. https://doi.org/10.1109/18.985947

    work page doi:10.1109/18.985947 2002

  2. [2]

    Elo ratings and the sports model: A neglected topic in ap- plied probability?Statistical Science, 32(4):616–629, 2017

    David Aldous. Elo ratings and the sports model: A neglected topic in ap- plied probability?Statistical Science, 32(4):616–629, 2017. ISSN 0883-4237. https://doi.org/10.1214/17-STS628

    work page doi:10.1214/17-sts628 2017

  3. [3]

    Mathematical probability foundations of dynamic sports rat- ings

    David Aldous. Mathematical probability foundations of dynamic sports rat- ings. Available athttps://www.stat.berkeley.edu/~aldous/157/Papers/aldous_ sports_draft.pdf, 2017

    2017

  4. [4]

    Nonpara- metric Estimation in the Dynamic Bradley-Terry Model

    Heejong Bong, Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo. Nonpara- metric Estimation in the Dynamic Bradley-Terry Model. In Silvia Chiappa and Roberto Calandra, editors,Proceedings of the Twenty Third International Conference on Artifi- cial Intelligence and Statistics, volume 108 ofProceedings of Machine Learning Research, pages 3317–3326. P...

    2020

  5. [5]

    Elo uncovered: Robustness and best practices in language model evaluation.Advances in Neural Information Processing Systems, 37:106135–106161, 2024

    Meriem Boubdir, Edward Kim, Beyza Ermis, Sara Hooker, and Marzieh Fadaee. Elo uncovered: Robustness and best practices in language model evaluation.Advances in Neural Information Processing Systems, 37:106135–106161, 2024

    2024

  6. [6]

    Bridging the gap between con- stant step size stochastic gradient descent and Markov chains.Ann

    Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between con- stant step size stochastic gradient descent and Markov chains.Ann. Statist., 48(3): 1348–1382, 2020. ISSN 0090-5364,2168-8966. https://doi.org/10.1214/19-AOS1850

    work page doi:10.1214/19-aos1850 2020

  7. [7]

    Rosenthal-type inequalities for linear statistics of Markov chains.arXiv preprint arXiv:2303.05838, 2023

    Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Marina Sheshukova. Rosenthal-type inequalities for linear statistics of Markov chains.arXiv preprint arXiv:2303.05838, 2023

    work page arXiv 2023

  8. [8]

    Andreas Eberle and Mateusz B. Majka. Quantitative contraction rates for Markov chains on general state spaces.Electron. J. Probab., 24:Paper No. 26, 36, 2019. ISSN 1083-6489. https://doi.org/10.1214/19-EJP287

    work page doi:10.1214/19-ejp287 2019

  9. [9]

    A matrix expander Chernoff bound

    Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava. A matrix expander Chernoff bound. InSTOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1102–1114. ACM, New York, 2018. ISBN 978-1-4503-5559- 9

    2018

  10. [10]

    A Chernoff bound for random walks on expander graphs

    David Gillman. A Chernoff bound for random walks on expander graphs. In34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993), pages 680–691. IEEE Comput. Soc. Press, Los Alamitos, CA, 1993. ISBN 0-8186-4370-6. https://doi.org/10.1109/SFCS.1993.366819

    work page doi:10.1109/sfcs.1993.366819 1993

  11. [11]

    Randomness-efficient sampling within NC1.Computational Com- plexity, 17(1):3–37, 2008

    Alexander D Healy. Randomness-efficient sampling within NC1.Computational Com- plexity, 17(1):3–37, 2008

    2008

  12. [12]

    Non-asymptotic estimates for Markov transition matrices via spectral gap methods.Electron

    De Huang and Xiangyuan Li. Non-asymptotic estimates for Markov transition matrices via spectral gap methods.Electron. J. Probab., 30:Paper No. 171, 28, 2025. ISSN 1083-6489. https://doi.org/10.1214/25-ejp1426

    work page doi:10.1214/25-ejp1426 2025

  13. [13]

    Curvature, concentration and error estimates for Markov chain Monte Carlo.Ann

    Aldéric Joulin and Yann Ollivier. Curvature, concentration and error estimates for Markov chain Monte Carlo.Ann. Probab., 38(6):2418–2442, 2010. ISSN 0091-1798,2168- 894X. https://doi.org/10.1214/10-AOP541

    work page doi:10.1214/10-aop541 2010

  14. [14]

    Dynamic ranking with the BTL model: a nearest neighbor based rank centrality method.J

    Eglantine Karlé and Hemant Tyagi. Dynamic ranking with the BTL model: a nearest neighbor based rank centrality method.J. Mach. Learn. Res., 24:Paper No. [269], 57,

  15. [15]

    ISSN 1532-4435,1533-7928

  16. [16]

    Concentration of measure without indepen- dence: a unified approach via the martingale method

    Aryeh Kontorovich and Maxim Raginsky. Concentration of measure without indepen- dence: a unified approach via the martingale method. InConvexity and concentration, volume 161 ofIMA Vol. Math. Appl., pages 183–210. Springer, New York, 2017. ISBN 978-1-4939-7004-9; 978-1-4939-7005-6

    2017

  17. [17]

    Concentration inequalities for dependent random variables via the martingale method.Ann

    Aryeh Kontorovich and Kavita Ramanan. Concentration inequalities for dependent random variables via the martingale method.Ann. Probab., 36(6):2126–2158, 2008. ISSN 0091-1798,2168-894X. https://doi.org/10.1214/07-AOP384

    work page doi:10.1214/07-aop384 2008

  18. [18]

    Streaming PCA for Markovian data.Ad- vances in Neural Information Processing Systems, 36:64650–64662, 2023

    Syamantak Kumar and Purnamrita Sarkar. Streaming PCA for Markovian data.Ad- vances in Neural Information Processing Systems, 36:64650–64662, 2023

    2023

  19. [19]

    León and Fran¸cois Perron

    Carlos A. León and Fran¸cois Perron. Optimal Hoeffding bounds for discrete reversible Markov chains.Ann. Appl. Probab., 14(2):958–970, 2004. ISSN 1050-5164,2168-8737. https://doi.org/10.1214/105051604000000170

    work page doi:10.1214/105051604000000170 2004

  20. [20]

    Chernoff-type bound for finite Markov chains.Ann

    Pascal Lezaud. Chernoff-type bound for finite Markov chains.Ann. Appl. Probab., 8 (3):849–867, 1998. ISSN 1050-5164. https://doi.org/10.1214/aoap/1028903453. MATRIX CONCENTRATION INEQUALITIES FOR TIME-INHOMOGENEOUS MARKOV CHAINS 35

    work page doi:10.1214/aoap/1028903453 1998

  21. [21]

    Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo.ℓ∞-bounds of the MLE in the BTL model under general comparison graphs. In James Cussens and Kun Zhang, editors,Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial In- telligence, volume 180 ofProceedings of Machine Learning Research, page 1178–1187. PMLR, 2022

    2022

  22. [22]

    Concentration inequalities for sums of Markov-dependent random matrices.Inf

    Joe Neeman, Bobby Shi, and Rachel Ward. Concentration inequalities for sums of Markov-dependent random matrices.Inf. Inference, 13(4):Paper No. iaae032, 52, 2024. ISSN 2049-8764,2049-8772. https://doi.org/10.1093/imaiai/iaae032

    work page doi:10.1093/imaiai/iaae032 2024

  23. [23]

    Rank centrality: Ranking from pairwise comparisons.Operations Research, 65(1):266–287, 2017

    Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons.Operations Research, 65(1):266–287, 2017. ISSN 0030364X, 15265463. URLhttp://www.jstor.org/stable/26153541

    work page arXiv 2017

  24. [24]

    An Analysis of Elo Rating Systems via Markov Chains

    Sam Olesker-Taylor and Luca Zanetti. An Analysis of Elo Rating Systems via Markov Chains. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors,Advances in Neural Information Processing Systems, volume 37, pages 138289–138323. Curran Associates, Inc., 2024

    2024

  25. [25]

    Ricci curvature of M arkov chains on metric spaces

    Yann Ollivier. Ricci curvature of Markov chains on metric spaces. J. Funct. Anal., 256(3):810–864, 2009. ISSN 0022-1236,1096-0783. https://doi.org/10.1016/j.jfa.2008.11.001

    work page doi:10.1016/j.jfa.2008.11.001 2009

  26. [26]

    Concentration inequalities for Markov chains by Marton couplings and spectral methods.Electronic Journal of Probability, 20 (none):1 – 32, 2015

    Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods.Electronic Journal of Probability, 20:no. 79, 32, 2015. https://doi.org/10.1214/EJP.v20-4039

    work page doi:10.1214/ejp.v20-4039 2015

  27. [27]

    Matrix moment and concentration inequal- ities for martingales and ergodic Markov chains with applications in statistical learning

    Yang Peng, Yuchen Xin, and Zhihua Zhang. Matrix moment and concentration inequal- ities for martingales and ergodic Markov chains with applications in statistical learning. arXiv preprint arXiv:2508.04327, 2025

    work page arXiv 2025

  28. [28]

    Finite Sample Properties of Adaptive Markov Chains via Curvature

    Natesh S. Pillai and Aaron Smith. Finite sample properties of adaptive Markov chains via curvature.arXiv preprint arXiv:1309.6699, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  29. [29]

    Saloff-Coste and J

    L. Saloff-Coste and J. Zúñiga. Merging for time inhomogeneous finite Markov chains. I. Singular values and stability.Electron. J. Probab., 14:1456–1494, 2009. ISSN 1083-6489. https://doi.org/10.1214/EJP.v14-656

    work page doi:10.1214/ejp.v14-656 2009

  30. [30]

    Time inhomogeneous Markov chains with wave-like behavior.Ann

    Laurent Saloff-Coste and Jessica Zúñiga. Time inhomogeneous Markov chains with wave-like behavior.Ann. Appl. Probab., 20(5):1831–1853, 2010. ISSN 1050-5164,2168-

    2010

  31. [31]

    https://doi.org/10.1214/09-AAP661

    work page doi:10.1214/09-aap661

  32. [32]

    Merging and stability for time inhomo- geneous finite Markov chains

    Laurent Saloff-Coste and Jessica Zúñiga. Merging and stability for time inhomo- geneous finite Markov chains. InSurveys in stochastic processes, EMS Ser. Congr. Rep., pages 127–151. Eur. Math. Soc., Zürich, 2011. ISBN 978-3-03719-072-2. https://doi.org/10.4171/072-1/7

    work page doi:10.4171/072-1/7 2011

  33. [33]

    Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

    Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ram- chandran, and Martin Wainwright. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. In Guy Lebanon and S. V. N. Vish- wanathan, editors,Proceedings of the Eighteenth International Conference on Arti- ficial Intelligence and Statistics, volume 38...

    2015

  34. [34]

    Multivariate trace in- equalities.Comm

    David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace in- equalities.Comm. Math. Phys., 352(1):37–58, 2017. ISSN 0010-3616,1432-0916. https://doi.org/10.1007/s00220-016-2778-5. 36 LUCA ZANETTI

    work page doi:10.1007/s00220-016-2778-5 2017

  35. [35]

    Joel A. Tropp. User-friendly tail bounds for sums of random matri- ces.Found. Comput. Math., 12(4):389–434, 2012. ISSN 1615-3375,1615-3383. https://doi.org/10.1007/s10208-011-9099-z

    work page doi:10.1007/s10208-011-9099-z 2012

  36. [36]

    Norm of difference in exponential of matrices

    Frederik vom Ende. Answer to: “Norm of difference in exponential of matrices”. Math- ematics Stack Exchange, March 2024. URLhttps://math.stackexchange.com/a/ 4885075. Accessed: 2026-01-08. AppendixA.Auxiliary results We prove a generalisation of Hoeffding’s lemma to the Hermitian setting. While similar results are well known (see, e.g., [33]), we have not...

    2024