The convergence rate of a Markov chain towards its stationary distribution is typically assessed using the concept of worst-case total variation *mixing time*. However, this quantity is pessimistic and is challenging to infer from a single stream of data. The goal of our research program, in collaboration with Pierre Alquier (ESSEC Business School, Singapore) is to advocate for the use of the average-mixing time as a more optimistic and demonstrably easier-to-estimate alternative.

We had already demonstrated that estimating the average mixing time was both possible and beneficial in some settings and our plan was to improve our estimation procedures, both theoretically and in practice.

Towards our goal, we have obtained the following results in FY24:

1/ We improved minimax Probably Approximately Correct (PAC) rates for estimating individual β-mixing coefficients of discrete time, time homogeneous Markov chains over countable state spaces by obtaining finite sample bounds in the *general ergodic* setting. Until now, rates in the general ergodic setting were only known for the Mean Absolute Deviation (MAD), and PAC rates were only available in the *uniformly ergodic* setting, i.e. in the restrictive setting where the (worst-case) mixing time is finite. Our new bound depends on the *average* mixing time instead, and thus remains valid even when the mixing time is infinite.

2/ Building upon 1/ we obtained a PAC bound for estimating the average mixing time from a single countable Markovian trajectory in a *general ergodic setting*. Until now, only rates in the uniformly ergodic setting were available.

3/ Finally, we obtained estimation rates for Kernel Mean Embeddings (KME) with time-dependent data. Specifically, we extended our previous estimation results from an iid setting to mixing processes by obtaining confidence intervals involving a covariance parameter in the Reproducing Kernel Hilbert Space (RKHS) and mixing coefficients for both φ-mixing and β-mixing processes. In particular, we demonstrated that when the underlying process is a countable Markov chain, our framework based on the average mixing time is readily applicable.

We presented our research results on the average mixing time at the following venues:

[1] IEEE East Asian School of Information Theory 2024 (EASIT'24)
Shonan, Kanagawa, July 30-August 2, 2024

[2] Bernoulli-IMS 11th World Congress in Probability and Statistics (Bernoulli-IMS'24) 
Bochum, Germany, August 12-16, 2024

[3] The 27th Information-Based Induction Sciences Workshop (IBIS'24)
Omiya, Saitama, November 4-7, 2024 

[4] The 46th Symposium on Information Theory and its Applications (SITA'24)
Awara, Fukui, December 10-13, 2024