Document detail
ID
oai:arXiv.org:2410.12721
Topic
Mathematics - Probability Computer Science - Information The...Author
Mithal, Deven Orecchia, LorenzoCategory
Computer Science
Year
2024
listing date
10/23/2024
Keywords
probability half-steps duality chainsAbstract
We realize the half-steps of a general class of Markov chains as alternating projections with respect to the reverse Kullback-Leibler divergence between sets of joint probability distributions which admit an information geometrical property known as autoparallelism.
We exhibit both a weak and strong duality between the Markov chains defined by the even and odd half-steps of the alternating projection scheme, which manifests as an equivalence of entropy decay statement regarding the chains, with a precise characterization of the entropy decrease at each half-step.
We apply this duality to several Markov chains of interest, and obtain either new results or short, alternative proofs for mixing bounds on the dual chain, with the Swendsen-Wang dynamics serving as a key example.
Additionally, we draw parallels between the half-steps of the relevant Markov chains and the Sinkhorn algorithm from the field of entropically regularized optimal transport, which are unified by the perspective of alternating projections with respect to an \alpha-divergence on the probability simplex.
Mithal, Deven,Orecchia, Lorenzo, 2024, Geometry and Duality of Alternating Markov Chains
PRACTIQ: A Practical Conversational Text-to-SQL dataset with Ambiguous and Unanswerable Queries
language sql text-to-sql clarification unanswerable user
Plastic rearrangement of basal forebrain parvalbumin-immunoreactive neurons in the kainite model of epilepsy
± lobe temporal animals µm cholinergic cell neurons vs epilepsy basal forebrain
