a bound for Feldman's **f-bar** $\bar{f}$ metric for measures 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)?
$$
 A: 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). 
A: 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.
