Cover Image

A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bienvenu, Laurent, Gimbert, Hugo, Pulari, Subin
Format:	Preprint
Published:	2025
Subjects:	Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Agafonov and Schnorr-Stimm theorems for probabilistic automata
by: Bienvenu, Laurent, et al.
Published: (2025)

Efficient Constructions of Finite-State Independent Normal Pairs
by: Pulari, Subin
Published: (2026)

Point-to-set Principle and Constructive Dimension Faithfulness
by: Nandakumar, Satyadev, et al.
Published: (2024)

Characterizing normality via automata and random matrix products
by: Bienvenu, Laurent, et al.
Published: (2026)

On Normality and Equidistribution for Separator Enumerators
by: Pulari, Subin
Published: (2026)

Finite-State Dimension and The Davenport Erdős Theorem
by: Clanin, Joe, et al.
Published: (2025)

Multi-Head Finite-State Dimension
by: Huang, Xiang, et al.
Published: (2025)

Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing
by: Watanabe, Shun, et al.
Published: (2014)

A Markov Chain Monte Carlo Method for Efficient Finite-Length LDPC Code Design
by: Tanrıkulu, Ata, et al.
Published: (2025)

Shared Information for a Markov Chain on a Tree
by: Bhattacharya, Sagnik, et al.
Published: (2023)

Virtual Quantum Markov Chains
by: Chen, Yu-Ao, et al.
Published: (2023)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Geometry and Duality of Alternating Markov Chains
by: Mithal, Deven, et al.
Published: (2024)

Coded Downlink Massive Random Access and a Finite de Finetti Theorem
by: Song, Ryan, et al.
Published: (2024)

Generalized Forms of the Kraft Inequality for Finite-State Encoders
by: Merhav, Neri
Published: (2026)

Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains
by: Makkuva, Ashok Vardhan, et al.
Published: (2024)

Near-Optimal Clustering in Mixture of Markov Chains
by: Lee, Junghyun, et al.
Published: (2025)

The Markov-Chain Polytope with Applications
by: Golin, Mordecai J., et al.
Published: (2024)

Maximum Sum-Rank Distance Codes over Finite Chain Rings
by: Martínez-Peñas, Umberto, et al.
Published: (2021)

From Markov to Laplace: How Mamba In-Context Learns Markov Chains
by: Bondaschi, Marco, et al.
Published: (2025)

Gradient-Based Markov Chain Monte Carlo for MIMO Detection
by: Zhou, Xingyu, et al.
Published: (2023)

Absorbing Markov Chain-Based Analysis of Age of Information in Discrete-Time Dual-Queue Systems
by: Feng, Yifan, et al.
Published: (2025)

Entropy Contractions in Markov Chains: Half-Step, Full-Step and Continuous-Time
by: Caputo, Pietro, et al.
Published: (2024)

Function-Correcting Codes for Linear and Locally Bounded Functions Over a Finite Chain Ring
by: Verma, Gyanendra K., et al.
Published: (2026)

A Third Information-Theoretic Approach to Finite de Finetti Theorems
by: Berta, Mario, et al.
Published: (2023)

Hermitian LCD $2$-Quasi Abelian Codes over Finite Chain Rings
by: Bhowmick, Sanjit, et al.
Published: (2026)

Algorithmic Randomness in Continuous-Time Markov Chains
by: Huang, Xiang, et al.
Published: (2019)

Multihead Finite-State Compression
by: Lutz, Neil
Published: (2025)

Adaptive Multi-Head Finite-State Gamblers
by: Cruz, Julianne, et al.
Published: (2026)

Capacity of Finite-State Channels with Delayed Feedback
by: Huleihel, Bashar, et al.
Published: (2023)

Coding Theorem for Generalized Reed-Solomon Codes
by: Zheng, Xiangping, et al.
Published: (2025)

Fastest Mixing Reversible Markov Chain: Clique Lifted Graphs and Subgraphs
by: Jafarizadeh, Saber
Published: (2025)

Optimal Source Coding of Markov Chains for Real-Time Remote Estimation
by: Cosandal, Ismail, et al.
Published: (2025)

The Duality Upper Bound for Finite-State Channels with Feedback
by: Huleihel, Bashar, et al.
Published: (2024)

A New Finite-Horizon Dynamic Programming Analysis of Nonanticipative Rate-Distortion Function for Markov Sources
by: He, Zixuan, et al.
Published: (2024)

An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains
by: Zhou, Ruida, et al.
Published: (2024)

Rate Distortion Approach to Joint Communication and Sensing With Markov States: Open Loop Case
by: Lindstrom, Colton P., et al.
Published: (2025)

Information Decomposition Diagrams Applied beyond Shannon Entropy: A Generalization of Hu's Theorem
by: Lang, Leon, et al.
Published: (2022)

Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels
by: Pfister, Henry D., et al.
Published: (2026)

Common Randomness Generation from Finite Compound Sources
by: Ezzine, Rami, et al.
Published: (2024)