Optimal probability measure

Question

Let $A$ be a finite set and let $\Bbb P$ be a probability measure on $A^{\Bbb N_0}$. Further, let $x_i:A^{\Bbb N_0}\to A$ be projection maps, so that $(x_i)_{i=0}^\infty$ can be treated as a stochastic process. Suppose that for some integer number $m\geq 1$ the measure $\Bbb P$ satisfies the following condition: $$ (x_i,\dots,x_{i+m})_*\Bbb P = (x_0,\dots,x_m)_*\Bbb P\quad \forall i\in \Bbb N,\tag{1} $$ that is any sequence of the length $m+1$ has equal probability of appearance anywhere along the trajectory of the process. For example, $\Bbb P$ is shift-invariant (stationary) if and only if it satisfies $(1)$ for any choice of $m$. In my case, the number $m$ is fixed though, so $\Bbb P$ does not have to be a stationary measure.

Let us denote $\Bbb P^m := (x_0,\dots,x_m)_*\Bbb P$ to be a measure on $A^{m+1}$, and let $F:A^{m+1}\to\Bbb R$ be some arbitrary function. Suppose, I need to maximize $$ \Bbb P^m[F]:=\sum_{s\in A^{m+1}}F(s)\cdot\Bbb P^m(\{s\}) \tag{2}. $$ where the optimization is done over all possible measures $\Bbb P$ that satisfy $(1)$. Have such problem been already studied, perhaps the solution is already known?

Answer 1

For a finite sequence $Y= (y_0,\dots,y_m)$ let $\left <Y\right>\subset A^{m+1}$ be the set of sequences $$\left<Y\right> = \{ (y_i, y_{i+1 \mod (m+1)}, \dots y_{i+1 \mod (m+1)}) : 0 \leq i \leq m \}$$ be the set of shifts of $Y$.

Now let $$\mathscr F = \left\{\left<Y\right> : Y\in A^{m+1}\right\}$$ be the shift invariant $\sigma$-algebra on $A^{m+1}$. As $\mathscr F$ is a partition $\sigma$-algebra we have $$\mathbb P^m\left[F \left| \mathscr F\right.\right](Y) = \frac 1{m+1} \sum_{\hat Y\in\left<Y\right>} F(\hat Y).$$

Therefore if $\bar Y$ is such that $\sum_{\hat Y\in\left<\bar Y\right>} F(\hat Y)\geq\sum_{\hat Y\in\left< Y\right>} F(\hat Y)$ for every $Y\in A^{m+1}$ we have

$$\begin{array}{rl} \mathbb P^m\left[F \right] &= \int_{A^{m+1}} \mathbb P^m\left[F \left| \mathscr F\right.\right](X) d \mathbb P^m(X) \\ &\leq \int_{A^{m+1}} \mathbb P^m\left[F \left| \mathscr F\right.\right](\bar Y) d \mathbb P^m(X) \\ &=\frac 1{m+1}\sum_{\hat Y\in\left<\bar Y\right>} F(\hat Y) \end{array}$$

So set $\mathbb P$ to be the measure constructed by choosing $(x_0,\dots,x_m)$ uniformly from $\left<\bar Y\right>$ and setting $x_k = x_{k \mod (m+1)}$ for $k> m$ then $\mathbb P$ is shift invariant by construction and $$\mathbb P^m\left[F \right] =\frac 1{m+1}\sum_{\hat Y\in\left<\bar Y\right>} F(\hat Y)$$ attains its maximal value.

Answer 2

Consider the following counterexample.

Let $A=\{0,1\}$ and $m=2$. Consider the optimization problem with $$F(110) = F(100) = F(001) = F(011) = 1,\qquad F=0\; \text{otherwise}. $$

This problem is solved by $$\mathbb{P}^m(110) = \mathbb{P}^m(100) = \mathbb{P}^m(001) = \mathbb{P}^m(011) = 1/4, \qquad \mathbb{P}^m=0\; \text{otherwise}.$$ and the optimal value is $1$.

The stochastic process can be build by choosing with equal probability $1/4$ one of the realizations

$(00110011\dots), (01100110\dots), (11001100\dots), (10011001\dots)$

Note that $\{(110),(100),(001),(011)\}$ is not a shift-invariant class and the average of the objective function is less than 1 for all the possible shift-invariant classes.

The problem in the proof (I guess) is assigning equal probability $\frac{1}{m+1}$ to all the elements inside a shift-invariant class (it does not need to be the case).