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)? $$


2 Answers 2


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).

  • $\begingroup$ Thanks for your answer! But I do not see how to exclude the possibility that $\bar{f}(x,y)< \bar{f}(\mu,\nu)$ for some $x$ and $y$. The proof for $\bar{d}$ requires the construction of empirical joining using $x$ and $y$, but it is not clear for me how to adapt it for $\bar{f}$. $\endgroup$ Nov 30, 2016 at 1:33
  • $\begingroup$ Sorry. I see now - you want to show that for every generic $x$ and generic $y$, you have this? $\endgroup$ Nov 30, 2016 at 1:54
  • $\begingroup$ I would like to know if the existence of a pair of generic points with $\bar{f}(x,y)<\varepsilon$ implies that $\bar{f}(\mu,\nu)<\varepsilon$. I found in a lecture notes written by Ornstein, Rudolph and Weiss results which (when properly combined) seem to say that for every $\varepsilon>0$ there is a $\delta>0$ such that $\bar{f}(x,y)<\delta$ implies that $\bar{f}(\mu,\nu)<\varepsilon$, but since they use a slightly different definitions I would like to see a direct proof and I wonder whether one can have $\varepsilon=\delta$. $\endgroup$ Nov 30, 2016 at 8:32

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.