Orateur
Description
Introduced in 1993 by Merhav and Ziv, the Merhav-Ziv estimator $Q_n$ is an analogue of the well-known Lempel-Ziv estimator, which estimates the Cross Entropy of two unknown probability measures $\mathbb{P}$ and $\mathbb{Q}$. The algorithm takes as an input two strings $y_1^n$ and $x_1^n$ and does the following: it starts by considering the largest word $y_{1}^m$ which appears inside $x_1^n$, then looks at the largest second word $y_{m+1}^{m'}$ which appears inside $x_1^n$ and continues as such until the entire string $y_1^n$ has been parsed into subwords. $Q_n$ is then the number of parsed words created by this procedure. In their paper, Merhav and Ziv show the $\mathbb{P}\times \mathbb{Q}$ a.s convergence of $n^{-1}\log(n) Q_n$ to the cross entropy of $\mathbb P$ relative to $\mathbb Q$ under the seemingly restrictive assumption that both the probability measures are stationary Markov measures. Surprisingly, no rigorous generalisation of this result, covering more general measures, can be found. I will present the most recent generalisation of the result under fairly general decoupling assumption and talk about the next steps in getting the most general result we can hope for.
