a bound for Feldman's **f-bar** $\bar{f}$ metric for measures

Question

My question regards properties of the f-bar metric $\bar{f}$ defined for shift invariant measures on $\mathscr{A}^\infty$ where $\mathscr{A}$ is a finite alphabet. The definition of the $\bar{f}$ metric mimics the definition of the d-bar metric $\bar{d}$ and shares many properties with the later. Unfortunately the results are scattered and the sources use different variants of the definition. I would like to know whether the following result holds true (the analogous result for $\bar{d}$ is known).

Given two $n$ words $u=u(0)u(1)\ldots u(n-1)$ and $w=w(0)w(1)\ldots w(n-1)$ over $\mathscr{A}$ we define $$ \bar{f}_n(u,w)=1-\frac{k}{n}, $$ where $k$ is the largest integer $\ell$ such that for some $0\le i_1<i_2<\ldots<i_\ell<n$ and $0\le j_1<j_2<\ldots<j_\ell<n$ we have $u(i_s)=w(j_s)$ for $s=1,\ldots,k$. For two infinite sequences $x=x_0x_1x_2\ldots$ and $y=y_0y_1y_2\ldots$ over $\mathscr{A}$ we set $$ \bar{f}(x,y)=\limsup_{n\to\infty} \bar{f}_n(x_0x_1\ldots x_{n-1},y_0y_1\ldots y_{n-1}) $$

Let $\mu$ and $\nu$ be ergodic shift invariant measures on $\mathcal{A}^\infty$. By $\mu_n$, respectively $\nu_n$ we denote the restriction of $\mu$, respectively $\nu$ to the set of all $n$-cylinders,that is, the measures that $\mu$ and $\nu$ respectively define on $\mathcal{A}^n$ via the projections onto first $n$ coordinates. Let $J_n(\mu,\nu)$ denote the set of all measures $\lambda_n$ on $\mathcal{A}^n\times \mathcal{A}^n$ whose marginals are $\mu_n$ and $\nu_n$.

Define $$ \bar{f}_n(\mu,\nu)=\inf_{\lambda_n\in J_n(\mu,\nu)}\int_{\mathcal{A}^n\times \mathcal{A}^n}\bar{f}_n(u,v) \lambda_n(u,v). $$ The f-bar distance between measures is given by $$ \bar{f}(\mu,\nu)=\sup_{n\ge 1} \bar{f}_n(\mu,\nu)=\lim_{n\to\infty}\bar{f}_n(\mu,\nu). $$

And here is the question: Assume that $x$ is a generic point (typical sequence) for $\mu$ and $y$ is a generic point (typical sequence) for $\nu$. Is it true that $$ \bar{f}(\mu,\nu)\le \bar{f}(x,y)? $$

Answer 1

I think the proof is completely analogous to the proof for $\bar d$. It amounts to Fatou's lemma for bounded functions plus replacing the infimum over all joinings by the value taken at the trivial joining. Fatou's lemma for bounded functions states: $$ \limsup\int g_n\,d\lambda\le \int\limsup g_n\,d\lambda. $$

We clearly have $$ \bar f_n(\mu,\nu)\le \int_{\mathcal A^n\times\mathcal A^n}\bar f_n(u,v)\, d(\mu_n\times\nu_n)(u,v), $$ as this is just taking the product coupling of $\mu_n$ and $\nu_n$ rather than the infimum over all couplings. Hence \begin{align*} \bar f(\mu,\nu)&=\limsup_n \bar f_n(\mu,\nu)\\ &\le \limsup_n\int_{\mathcal A^n\times\mathcal A^n}\bar f_n(u,v)\, d(\mu_n\times\nu_n)(u,v)\\ &= \limsup_n\int_{\mathcal A^\infty\times \mathcal A^\infty} \bar f_n(x_0\ldots x_{n-1},y_0\ldots,y_{n-1})\, d(\mu\times\nu)(x,y)\\ &\le \int_{\mathcal A^\infty\times \mathcal A^\infty} \limsup_n\bar f_n(x_0\ldots x_{n-1},y_0\ldots,y_{n-1})\, d(\mu\times\nu)(x,y)\\ &=\int_{\mathcal A^\infty\times\mathcal A^\infty} \bar f(x,y)\,d(\mu\times\nu)(x,y). \end{align*}

Since $\bar f(x,y)$ is invariant under $\sigma\times\iota$ and $\iota\times\sigma$, it is constant $\mu\times\nu$-almost everywhere. In particular, for $\mu$-a.e. $x$ and $\nu$-a.e. $y$, $\bar f(\mu,\nu)\le \bar f(x,y)$.

By the way, in case you didn't know already, the $\bar f$ metric has a different name in computer science: it's called the edit distance (given two strings, what is the smallest number of edits you can do to make them agree).

Answer 2

The subsequent couplings of empirical measures given by two generic points, $x\in A^{\infty}$ for an invariant measure $\mu$ and $y\in A^{\infty}$ for an invariant measure $\nu$, can be established to keep the $f$-metric as small as possible in little bit more technical manner than in the case of $d$-bar metric. I have not finished yet my writings, but it will be soon. It seems, that the bound I am able to get is $$f(\mu,\nu)\leq 3\liminf f_n(x_0x_1\ldots x_{n-1},y_0y_1\ldots y_{n-1}).$$

I reply here now mainly because I have some questions about the posts above. First question is for Dominik. Why do you use supremum and the limit in the definition of the $f$-distance for measures? This definition is possible in the case of $d$-bar metric, since the sequence $n\cdot d_n(\mu,\nu)$ is superadditive. This follows from the fact that the $d$-bar metric is additive with respect to concatenation, i.e. $$(n+m)\bar{d}(uv,u'v')=n\bar{d}(u,u')+m\bar{d}(v,v'),\qquad u,u'\in A^n, v,v'\in A^m.$$ For $f$-metric, we have subadditivity, i.e. $$(n+m)\bar{f}(uv,u'v')\leq n\bar{f}(u,u')+m\bar{f}(v,v'),\qquad u,u'\in A^n, v,v'\in A^m.$$ This inequality can be strict, e.g. $$6\bar{f}(aaabbb,bbbaaa)=3<6=3\bar{f}(aaa,bbb)+3\bar{f}(bbb,aaa).$$ Maybe the subadditivity can be somehow controlled, but I do not see it. It led me to keep limes superior in the definition for $f$-metric.

The second question is for Antony. Is it possible to conclude that $f(x,y)$ is almost surely constant even in the case when $\mu\times\nu$ is not ergodic? In all cases, I think that your ideas are true even if one replaces product joining with any ergodic joining that has to exist.