Minimax and dynamic (in)consistency

post by Vanessa Kosoy (vanessa-kosoy) · 2016-12-11T10:42:08.000Z · LW · GW · 0 comments

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

The asymptotic optimality theorem for minimax we proved previously was formulated in terms of the "optimal value" $v\left(x\right)$. Compared to the Bayesian case, $v\left(x\right)$ has the strange property that its definition depends on rewards other than those received after observing $x$. This is a direct consequence of the dynamic inconsistency of minimax. In an attempt to get around this, we show that the minimax decision rule is dynamically consistent in a certain special case and demonstrate that this special case can occur often for a natural class of models. However, this doesn't immediately solve the problem: doing so requires replacing the minimax decision rule by a stronger condition that ensures subgame perfection in some sense. The formalization of the latter idea is left for future posts.

Appendix A contains the proofs of all results.

##Notation

Given $X$ a topological space, $P\left(X\right)$ will denote the space of Borel probability measures on $X$. We regard it as a topological space using the weak${}^{\ast }$ topology. Given $x\in X$, ${\delta }_x\in P\left(X\right)$ is defined by ${\delta }_x\left(A\right):=\left[\right[x\in A\left]\right]$. Given $\mu ,\nu \in P\left(X\right)$, $d_{\text{tv}}(\mu ,\nu )$ stands for the total variation distance between $\mu$ and $\nu$. We denote $P_C\left(X\right)$ the set of non-empty convex compact subsets of $P\left(X\right)$.

Given $X$ a finite set, $X^{\ast }$ denotes the set of finite strings in alphabet $X$, i.e. $X^{\ast }:={⨆}_{n\in N}{X}^n$. $X^{\omega }$ denotes the set of infinite strings in alphabet $X$. Given $x\in X^{\ast }\bigsqcup X^{\omega }$, $\left|x\right|\in N\bigsqcup \left\{\infty \right\}$ is the length of string. Given $0\le n<\left|x\right|$, $x_n\in X$ is the $n$-th symbol in $x$. Given $0\le n\le \left|x\right|$, $x_{<n}$ is the prefix of $x$ of length $n$. Given $x,y\in X^{\ast }\bigsqcup X^{\omega }$, the notations $x⊏y$, $x⊑y$, $x⊏/y$ and $x⋢y$ mean "$x$ is a proper prefix of $y$", "$x$ is a prefix of $y$" and their negations. ${\lambda }_X\in X^{\ast }$ is the empty string and $X^{+}:=X^{\ast }\setminus {\lambda }_X$.

##Factorization

We recall the result of the previous post regarding subagents of minimax agents:

#Proposition 0

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{\mu \in \Phi }{min}\left(E_{{\pi }_1^{\ast }\times \mu }\right[u_1]+\mu (A\left)E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\right[E_{{\pi }_2\left(t\right)\times \mu \mid A}\left[u_2\right(t\left)\right]\left]\right)$$

In general, ${\pi }_2^{\ast }$ is not a minimax policy for any natural model i.e. the minimax decision rule is not "dynamically consistent". However, if we assume a certain factorization condition, it is. Specifically, assume $E_1,E_2$ are compact Polish, $f:E_1\times E_2\to E$ is Borel measurable, ${\overline{u}}_1:S_1\times E_1\to R$ and ${\overline{u}}_2:S_2\times T\times E_2\to R$ are continuous s.t.

$$u_1(s_1,f(e_1,e_2\left)\right)={\overline{u}}_1(s_1,e_1)$$

$$u_2(s_2,t,f(e_1,e_2\left)\right)={\overline{u}}_1(s_2,t,e_2)$$

Further assume that $A_1\subseteq E_1$ is Borel s.t. $f^{-1}\left(A\right)=A_1\times E_2$ and ${\Phi }_{1,2}\in P_C\left(E_{1,2}\right)$ are s.t. $\Phi$ is the closure of the convex hull of $f_{\ast }({\Phi }_1\times {\Phi }_2)$.

#Proposition 1

Assume that ${min}_{\mu \in {\Phi }_1}{\mu }_1\left(A_1\right)>0$. Then,

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{\mu \in {\Phi }_2}{min}{E}_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\left[E_{{\pi }_2\left(t\right)\times \mu }\right[{\overline{u}}_2\left(t\right)\left]\right]$$

Moreover, define ${\overline{S}}_2:=T\to S_2$ equipped with the product topology, define ${\overline{\pi }}_2^{\ast }\in P\left({\overline{S}}_2\right)$ by

$${\overline{\pi }}_2^{\ast }:=\prod _{t\in T}{\pi }_2^{\ast }\left(t\right)$$

Define ${\overline{E}}_2:=T\times E_2$ and define ${\overline{\Phi }}_2\in P_C\left({\overline{E}}_2\right)$ by

$${\overline{\Phi }}_2:=\{{\alpha }_{\ast }{\pi }_1^{\ast }\times \mu \mid \mu \in {\Phi }_2\}$$

Finally, define ${\hat{u}}_2:{\overline{S}}_2\times {\overline{E}}_2\to R$ by

$${\hat{u}}_2(s,t,e):={\overline{u}}_2\left(s\right(t),t,e)$$

Then, ${\overline{\pi }}_2^{\ast }$ is a minimax policy for ${\overline{\Phi }}_2$ w.r.t. the utility function ${\hat{u}}_2$.

##Factorization everywhere

We now formulate a condition that ensures that factorizations happens "often" in a certain sense.

#Definition 1

Consider $\Phi \in P_C\left(O^{\omega }\right)$ and $x\in O^{\ast }$. Define $f^x:O^{\omega }\times O^{\omega }\to O^{\omega }$ by

$$f^x(e_1,e_2):=\{\begin{array}{c}{e}_1\text{if}x⊏/e_1\\ x{e}_2\text{if}x⊏e_1\end{array}$$

$\Phi$ is said to factorize at $x$ when there are ${\Phi }_1,{\Phi }_2\subseteq P\left(O^{\omega }\right)$ s.t. $\Phi$ is the closure of the convex hull of $f_{\ast }^x({\Phi }_1\times {\Phi }_2)$.

Given $e\in O^{\omega }$, $\Phi$ is said to factorize over $e$ when there are infinitely many $n\in N$ s.t. $\Phi$ factorizes at $e_{<n}$.

Given a time discount function $\gamma$, $\Phi$ is said to factorize frequently over $e$ (w.r.t. $\gamma$) when there is an increasing sequence $\{n_k\in N{\}}_{k\in N}$ s.t.

i. $\Phi$ factorizes at $e_{<n_k}$ for all $k$.

ii. There is $ϵ>0$ s.t. for all $k$

$$\frac{{\sum }_{n=n_{k+1}-1}^{\infty }\gamma \left(n\right)}{{\sum }_{n=n_k}^{\infty }\gamma \left(n\right)}>ϵ$$

For example, for geometric discount ($\gamma \left(n\right)={\beta }^n)$, condition ii means that $n_{k+1}-n_k$ is bounded.

$\Phi$ is said to factorize everywhere when

$$\forall \mu \in \Phi :{\mathrm{Pr}}_{e\sim \mu }\left[\Phi \text{factorizes over}e\right]=1$$

$\Phi$ is said to factorize frequently everywhere (w.r.t. $\gamma$) when

$$\forall \mu \in \Phi :{\mathrm{Pr}}_{e\sim \mu }\left[\Phi \text{factorizes frequently over}e\right]=1$$

---

Note that any singleton $\left\{\mu \right\}$ factorizes frequently everywhere w.r.t. any time discount function. More generally, we can give the following explicit description of models that factorize everywhere:

#Construction

Consider some $F:O^{\ast }\to P_C\left(O^{+}\right)$ ($O^{+}$ is considered to be a discrete space). Assume that for any $x\in O$, there is $A_x\subseteq O^{+}$ prefix-free s.t. any $\mu \in F\left(x\right)$ is supported on $A_x$.

We define $X_F\subseteq O^{\ast }$ as the minimal set with the following properties:

i. ${\lambda }_O\in X_F$

ii. If $x\in X_F$, $\mu \in F\left(x\right)$ and $y\in O^{+}$ is s.t. $\mu \left(y\right)>0$, then $xy\in X_F$.

We define ${\Phi }_F\subseteq P\left(O^{\omega }\right)$ as follows. $\mu \in {\Phi }_F$ iff for any $x\in X_F$, there is ${\mu }_x\in F\left(x\right)$ s.t. for any $y\in O^{+}$, if ${\mu }_x\left(y\right)>0$ then

$${\mathrm{Pr}}_{e\sim \mu }[xy⊏e]={\mathrm{Pr}}_{e\sim \mu }[x⊏e]{\mu }_x\left(y\right)$$

#Proposition 2

For any $F$ as above, ${\Phi }_F\in P_C\left(O^{\omega }\right)$ and factorizes everywhere.

---

It is also easy to use the above construction to get $\Phi$ that factorizes frequently everywhere w.r.t. given $\gamma$ (for example, if we require that for every $x\in X_F$, $F\left(x\right)$ is supported on strings of uniformly bounded length, ${\Phi }_F$ will factorize frequently everywhere w.r.t. geometric discount; this condition on $F$ is sufficient but not necessary).

We now formulate the optimality condition that we would like to hold (but for which minimax is unfortunately insufficent). Consider again $\Phi$, $\Psi$ and ${\pi }^{\ast }$ as before. Define $u_{>n}:O^{\omega }\times (O^{\ast }\to A)\to R$ to be normalized sum of rewards from time $n$, i.e.

$$u_{>n}(s,e):=\frac{{\sum }_{m>n}\gamma \left(m\right)r\left(e_{<m}^s\right)}{{\sum }_{m>n}\gamma \left(m\right)}$$

Define $w:O^{\ast }\to R$ by

$$w\left(x\right):=\underset{\rho \in A^{\left|x\right|}\to P(O^{\ast }\to A)}{max}\underset{\mu \in \Phi }{min}{E}_{\begin{array}{c}s\sim {\pi }^{\ast }{\otimes }_x\rho \\ e\sim \mu \end{array}}\left[u_{>\left|x\right|}\right(s,e)\mid x⊏e]$$

#Hypothesis

If ${\pi }^{\ast }$ satisfies the (yet unformulated) subgame perfection condition, we should have the following:

Assume $\Phi$ factorizes everywhere. Then,

$$\forall \mu \in \Phi :{\mathrm{Pr}}_{e\sim \mu }[\underset{n\to \infty }{liminf}max(w\left(e_{<n}\right)-E_{\begin{array}{c}s\sim {\pi }^{\ast }\\ e^{\prime }\sim \mu \end{array}}\left[u_{>n}\right(s,e^{\prime })\mid e_{<n}⊏e^{\prime }],0)=0]=1$$

Moreover, if $\Phi$ factorizes frequently everywhere, then

$$\forall \mu \in \Phi :{\mathrm{Pr}}_{e\sim \mu }[\underset{n\to \infty }{lim}max(w\left(e_{<n}\right)-E_{\begin{array}{c}s\sim {\pi }^{\ast }\\ e^{\prime }\sim \mu \end{array}}\left[u_{>n}\right(s,e^{\prime })\mid e_{<n}⊏e^{\prime }],0)=0]=1$$

##Appendix A

#Proof of Proposition 1

Recalling that minimization over $\Phi$ can be replaced by minimization over any set s.t. $\Phi$ is the closure of its convex hull, and using Proposition 0, we have

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{\begin{array}{c}{\mu }_1\in {\Phi }_1\\ {\mu }_2\in {\Phi }_2\end{array}}{min}\left(E_{{\pi }_1^{\ast }\times f_{\ast }({\mu }_1\times {\mu }_2)}\right[u_1]+({\mu }_1\times {\mu }_2\left)\right(f^{-1}\left(A\right)\left)E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\right[E_{{\pi }_2\left(t\right)\times f_{\ast }({\mu }_1\times {\mu }_2)\mid A}\left[u_2\right(t\left)\right]\left]\right)$$

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{\begin{array}{c}{\mu }_1\in {\Phi }_1\\ {\mu }_2\in {\Phi }_2\end{array}}{min}\left(E_{{\pi }_1^{\ast }\times {\mu }_1}\right[{\overline{u}}_1]+{\mu }_1(A_1\left)E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\right[E_{{\pi }_2\left(t\right)\times {\mu }_2}\left[{\overline{u}}_2\right(t\left)\right]\left]\right)$$

$${\pi }_2^{\ast }\in \underset{{\pi }_2:T\to P\left(S_2\right)}{argmax}\underset{{\mu }_1\in {\Phi }_1}{min}\left(E_{{\pi }_1^{\ast }\times {\mu }_1}\right[{\overline{u}}_1]+{\mu }_1(A_1\left)\underset{{\mu }_2\in {\Phi }_2}{min}{E}_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\right[E_{{\pi }_2\left(t\right)\times {\mu }_2}\left[{\overline{u}}_2\right(t\left)\right]\left]\right)$$

Using the assumption ${min}_{{\mu }_1\in {\Phi }_1}{\mu }_1\left(A_1\right)>0$, we get the desired result.

Now consider any ${\overline{\pi }}_2\in P\left({\overline{S}}_2\right)$. Define ${\pi }_2:T\to P\left(S_2\right)$ by $\left({\pi }_2\right(t\left)\right)\left(B\right):={\mathrm{Pr}}_{\sigma \sim {\overline{\pi }}_2}\left[\sigma \right(t)\in B]$. We have

$$E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\left[E_{\begin{array}{c}s\sim {\pi }_2\left(t\right)\\ e\sim {\mu }_2\end{array}}\right[{\overline{u}}_2(s,t,e)\left]\right]=E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\left[E_{\begin{array}{c}\sigma \sim {\overline{\pi }}_2\\ e\sim {\mu }_2\end{array}}\right[{\overline{u}}_2\left(\sigma \right(t),t,e)\left]\right]$$

$$E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\left[E_{\begin{array}{c}s\sim {\pi }_2\left(t\right)\\ e\sim {\mu }_2\end{array}}\right[{\overline{u}}_2(s,t,e)\left]\right]=E_{{\overline{\pi }}_2\times {\alpha }_{\ast }{\pi }_1^{\ast }\times \mu }\left[{\hat{u}}_2\right]$$

For the special case ${\overline{\pi }}_2={\overline{\pi }}_2^{\ast }={\prod }_{t\in T}{\pi }_2^{\ast }\left(t\right)$, we get ${\pi }_2={\pi }_2^{\ast }$ and therefore

$$E_{t\sim {\alpha }_{\ast }{\pi }_1^{\ast }}\left[E_{\begin{array}{c}s\sim {\pi }_2^{\ast }\left(t\right)\\ e\sim {\mu }_2\end{array}}\right[{\overline{u}}_2(s,t,e)\left]\right]=E_{{\overline{\pi }}_2^{\ast }\times {\alpha }_{\ast }{\pi }_1^{\ast }\times \mu }\left[{\hat{u}}_2\right]$$

Using the property of ${\pi }_2^{\ast }$, it follows that

$$\forall \mu \in {\Phi }_2:E_{{\overline{\pi }}_2\times {\alpha }_{\ast }{\pi }_1^{\ast }\times \mu }\left[{\hat{u}}_2\right]\le E_{{\overline{\pi }}_2^{\ast }\times {\alpha }_{\ast }{\pi }_1^{\ast }\times \mu }\left[{\hat{u}}_2\right]$$

$$\forall \overline{\mu }\in {\overline{\Phi }}_2:E_{{\overline{\pi }}_2\times \overline{\mu }}\left[{\hat{u}}_2\right]\le E_{{\overline{\pi }}_2^{\ast }\times \overline{\mu }}\left[{\hat{u}}_2\right]$$

#Proposition A.0

In the setting of the Construction, consider any $\mu \in {\Phi }_F$. Then:

$$\forall x\in X_F\exists {\mu }_x\in F\left(x\right)\forall y\in A_x:\mu \left(xy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)$$

#Proof of Proposition A.0

Given $x\in X_F$, we know there is ${\mu }_x\in F\left(x\right)$ s.t. the identity holds whenever ${\mu }_x\left(y\right)>0$. Summing these identities over y, we get

$$\sum _{{\mu }_x\left(y\right)>0}\mu \left(xy{O}^{\omega }\right)=\sum _{{\mu }_x\left(y\right)>0}\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)$$

$$\sum _{{\mu }_x\left(y\right)>0}\mu \left(xy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right)$$

Since $A_x$ is prefix-free, for any $y,y^{\prime }\in A_x$ we have $xy{O}^{\omega }\cap x{y}^{\prime }{O}^{\omega }=\varnothing$. Also, obviously, $xy{O}^{\omega }\subseteq x{O}^{\omega }$. It follows that

$$\sum _{y\in A_x}\mu \left(xy{O}^{\omega }\right)=\mu \left(\bigcup _{y\in A_x}xy{O}^{\omega }\right)\le \mu \left(x{O}^{\omega }\right)=\sum _{{\mu }_x\left(y\right)>0}\mu \left(xy{O}^{\omega }\right)$$

Since ${\mu }_x\left(y\right)>0$ implies $y\in A_x$, we conclude that for any $y\in A_x$, if ${\mu }_x\left(y\right)=0$ then $\mu \left(xy{O}^{\omega }\right)=0$. This, together with the property of ${\mu }_x$, gives the desired result.

#Proposition A.1

In the setting of the Construction, ${\Phi }_F$ is convex.

#Proof of Proposition A.1

Consider $\mu ,\nu \in {\Phi }_F$ and $p\in (0,1)$ and define $\xi =p\mu +(1-p)\nu$. Consider some $x\in X_F$, and let $A_x\subseteq O^{+}$ be as in the Construction. If $\xi \left(x{O}^{\omega }\right)=0$, we can choose any ${\xi }_x\in F\left(x\right)$ to satisfy the desired condition. Therefore, we can assume $\xi \left(x{O}^{\omega }\right)>0$. By Proposition A.0, there are ${\mu }_x,{\nu }_x\in F\left(x\right)$ s.t. for all $y\in A_x$:

$$\mu \left(xy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)$$

$$\nu \left(xy{O}^{\omega }\right)=\nu \left(x{O}^{\omega }\right){\nu }_x\left(y\right)$$

Taking a convex linear combination of these equations, we get

$$\xi \left(xy{O}^{\omega }\right)=p\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)+(1-p)\nu \left(x{O}^{\omega }\right){\nu }_x\left(y\right)$$

$$\xi \left(xy{O}^{\omega }\right)=\xi \left(x{O}^{\omega }\right)\frac{p\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)+(1-p)\nu \left(x{O}^{\omega }\right){\nu }_x\left(y\right)}{\xi \left(x{O}^{\omega }\right)}$$

Define ${\xi }_x\in P\left(O^{+}\right)$ by

$${\xi }_x:=p\frac{\mu \left(x{O}^{\omega }\right)}{\xi \left(x{O}^{\omega }\right)}{\mu }_x+(1-p)\frac{\nu \left(x{O}^{\omega }\right)}{\xi \left(x{O}^{\omega }\right)}{\nu }_x$$

${\xi }_x$ is a convex linear combination of ${\mu }_x$ and ${\nu }_x$, therefore ${\xi }_x\in F\left(x\right)$. We get

$$\xi \left(xy{O}^{\omega }\right)=\xi \left(x{O}^{\omega }\right){\xi }_x\left(y\right)$$

Therefore, $\xi \in {\Phi }_F$.

#Proposition A.2

In the setting of the Construction, ${\Phi }_F$ is closed.

#Proof of Proposition A.2

Consider any sequence ${\{{\mu }_n\in {\Phi }_F\}}_{n\in N}$ and s.t. ${\mu }_n\to \mu$ for some $\mu \in P\left(O^{\omega }\right)$. Consider some $x\in X_F$, and let $A_x\subseteq O^{+}$ be as in the Construction. By Proposition A.0, for any $n\in N$, there is ${\mu }_{nx}\in F\left(x\right)$ s.t. for any $y\in A_x$:

$${\mu }_n\left(xy{O}^{\omega }\right)={\mu }_n\left(x{O}^{\omega }\right){\mu }_{nx}\left(y\right)$$

Note that $P\left(O^{+}\right)$ is not compact but is still Polish (since $O^{+}$ is such), and therefore $F\left(x\right)$ is compact and Polish. Let $\{n_k\in N{\}}_{k\in N}$ be an increasing sequence s.t. ${\mu }_{n_{k}x}\to {\mu }_x$ for some ${\mu }_x\in F\left(x\right)$. For any $z\in O^{\ast }$, ${\chi }_{z{O}^{\omega }}:O^{\omega }\to \{0,1\}$ is a continuous function, and therefore ${\mu }_n\left(z{O}^{\ast }\right)\to \mu \left(z{O}^{\ast }\right)$. For any $y\in O^{+}$, ${\chi }_{\left\{y\right\}}:O^{+}\to \{0,1\}$ is also continuous, and therefore ${\mu }_{n_{k}x}\left(y\right)\to {\mu }_x\left(y\right)$. Putting these together, we get

$$\mu \left(xy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right){\mu }_x\left(y\right)$$

Therefore $\mu \in {\Phi }_F$.

#Proposition A.3

In the setting of the Construction, consider any $x,z\in X_F$, $\mu \in F\left(z\right)$ and $y\in O^{+}$ s.t. $\mu \left(y\right)>0$. Assume that $x⊏zy$. Then, $x⊑z$.

#Proof of Proposition A.3

We prove by induction on $\left|x\right|$. If $\left|x\right|=0$, then obviously $x⊑z$. If $\left|x\right|>0$, then, by definition of $X_F$, there is $x^{\prime }\in X_F$, $y^{\prime }\in O^{+}$ and $\nu \in F\left(x^{\prime }\right)$ s.t. $\nu \left(y^{\prime }\right)>0$ and $x=x^{\prime }{y}^{\prime }$. $x^{\prime }⊏x⊏zy$, therefore, by the induction hypothesis, $x^{\prime }⊑z$. Assume to the contrary that $x⋢z$. Then, since $x⊏zy$, $z⊏x=x^{\prime }{y}^{\prime }$. By the induction hypothesis, this implies $z⊑x^{\prime }$. We got $z=x^{\prime }$. It follows that $z{y}^{\prime }=x⊏zy$, and therefore $y^{\prime }⊏y$. However, $y,y^{\prime }\in A_z$ and $A_z$ is prefix-free, which is a contradiction.

#Proposition A.4

In the setting of the Construction, ${\Phi }_F$ is non-empty.

#Proof of Proposition A.4

Choose ${\mu }_x\in F\left(x\right)$ for each $x\in X_F$. Given any $z\in O^{+}$, define $p\left(z\right)\in O^{\ast }$ as the longest proper prefix of $z$ s.t. $p\left(z\right)\in X_F$. Define $\theta :O^{\ast }\to [0,1]$ recursively by

$$\theta \left({\lambda }_O\right):=1$$

$$\forall z\in O^{+}:\theta \left(z\right):=\theta \left(p\right(z\left)\right){\mathrm{Pr}}_{y\sim {\mu }_{p\left(z\right)}}[z⊑p(z\left)y\right]$$

Consider any $z\notin X_F$. For any $o\in O$, $p\left(zo\right)=p\left(z\right)$, therefore:

$$\theta \left(zo\right)=\theta \left(p\right(z\left)\right){\mathrm{Pr}}_{y\sim {\mu }_{p\left(z\right)}}[zo⊑p(z\left)y\right]$$

$$\sum _{o\in O}\theta \left(zo\right)=\theta \left(p\right(z\left)\right)\sum _{o\in O}{\mathrm{Pr}}_{y\sim {\mu }_{p\left(z\right)}}[zo⊑p(z\left)y\right]$$

$$\sum _{o\in O}\theta \left(zo\right)=\theta \left(p\right(z\left)\right){\mathrm{Pr}}_{y\sim {\mu }_{p\left(z\right)}}[z⊏p(z\left)y\right]$$

For any $y$ s.t. ${\mu }_{p\left(z\right)}\left(y\right)>0$, $p\left(z\right)y\in X_F$ and therefore $z\ne p\left(z\right)y$. It follows that $z⊏p\left(z\right)y$ iff $z⊑p\left(z\right)y$, and we get

$$\sum _{o\in O}\theta \left(zo\right)=\theta \left(z\right)$$

Now, consider $z\in X_F$. For any $o\in O$, $p\left(zo\right)=z$, therefore:

$$\theta \left(zo\right)=\theta \left(z\right){\mathrm{Pr}}_{y\sim {\mu }_z}[zo⊑zy]$$

$$\sum _{o\in O}\theta \left(zo\right)=\theta \left(z\right)\sum _{o\in O}{\mathrm{Pr}}_{y\sim {\mu }_z}[zo⊑zy]$$

Again we get

$$\sum _{o\in O}\theta \left(zo\right)=\theta \left(z\right)$$

It follows that there is $\mu \in P\left(O^{\omega }\right)$ s.t. for any $z\in O^{\ast }$, $\mu \left(z{O}^{\omega }\right)=\theta \left(z\right)$.

Consider any $x\in X_F$ and $y_0\in O^{+}$ s.t. ${\mu }_x\left(y_0\right)>0$. $p\left(x{y}_0\right)⊏x{y}_0$ and by Proposition\ A.13, this implies $p\left(x{y}_0\right)⊑x$. By definition of $p$, it follows that $p\left(x{y}_0\right)=x$. We get

$$\theta \left(x{y}_0\right)=\theta \left(p\right(x{y}_0\left)\right){\mathrm{Pr}}_{y\sim {\mu }_{p\left(x{y}_0\right)}}[x{y}_0⊑p(x{y}_0\left)y\right]$$

$$\theta \left(x{y}_0\right)=\theta \left(x\right){\mathrm{Pr}}_{y\sim {\mu }_x}[x{y}_0⊑xy]$$

$$\theta \left(x{y}_0\right)=\theta \left(x\right){\mathrm{Pr}}_{y\sim {\mu }_x}[y_0⊑y]$$

$y_0\in A_x$ and any $y\in O^{+}$ s.t. ${\mu }_x\left(y\right)>0$ is also in $A_x$. $A_x$ is prefix-free, so $y_0⊑y$ iff $y_0=y$. We get

$$\theta \left(x{y}_0\right)=\theta \left(x\right){\mu }_x\left(y_0\right)$$

$$\mu \left(x{y}_0{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right){\mu }_x\left(y_0\right)$$

Therefore, $\mu \in {\Phi }_F$.

#Proposition A.5

Consider $x\in O^{\ast }$ and let $f^x:O^{\omega }\times O^{\omega }\to O^{\omega }$ be defined as in Definition 1. Then, for any $y\in O^{\ast }$:

$$\left(f^x{)}^{-1}\right(xy{O}^{\omega })=x{O}^{\omega }\times y{O}^{\omega }$$

#Proof of Proposition A.5

Given any $e_1,e_2\in O^{\omega }$, $f^x(x{e}_1,y{e}_2)=xy{e}_2$. On the other hand, if $e_1,e_2,e_3\in O^{\omega }$ are s.t. $f^x(e_1,e_2)=xy{e}_3$ then $x⊏e_1$ and $e_2=y{e}_3$.

#Proposition A.6

Consider $x\in O^{\ast }$ and let $f^x:O^{\omega }\times O^{\omega }\to O^{\omega }$ be defined as in Definition 1. Then, for any $z\in O^{\ast }$, if $x⊏/z$, then:

$$\left(f^x{)}^{-1}\right(z{O}^{\omega })=z{O}^{\omega }\times O^{\omega }$$

#Proof of Proposition A.6

Assume $x=zw$ for some $w\in O^{\ast }$. For any $e_1,e_2\in O^{\omega }$, $f^x(z{e}_1,e_2)$ is either $z{e}_1$ (if $w⊏/e_1$) or $x{e}_2=zw{e}_2$ (if $w⊏e_1$). Either way, $z⊏f^x(z{e}_1,e_2)$. On the other hand, if $e_1,e_2,e_3\in O^{\omega }$ are s.t. $f^x(e_1,e_2)=z{e}_3$ then either $x⊏/e_1$ and $e_1=z{e}_3$ or $zw=x⊏e_1$. Either way, $z⊏e_1$.

Now, assume $x⋣z$. For any $e_1,e_2\in O^{\omega }$, $f^x(z{e}_1,e_2)=z{e}_1$ (since $x⊏/z{e}_1$). On the other hand, if $e_1,e_2,e_3\in O^{\omega }$ are s.t. $f^x(e_1,e_2)=z{e}_3$ then $e_1=z{e}_3$ (since $x⊏/z{e}_3$).

#Proposition A.7

In the setting of the Construction, consider some $x\in X_F$ and define $G:O^{\ast }\to P_C\left(O^{+}\right)$ by $G\left(z\right):=F\left(xz\right)$. Assume that $w\in O^{\ast }$ is s.t. $xw\in X_F$. Then, $w\in X_G$.

#Proof of Proposition A.7

We prove by induction on $\left|w\right|$. For $\left|w\right|=0$, the proposition is obvious. Assume $\left|w\right|>0$. $xw\in X_F$, therefore $xw=x^{\prime }y$ for some $x^{\prime }\in X_F$, $\mu \in F\left(x^{\prime }\right)$ and $y\in O^{+}$ s.t. $\mu \left(y\right)>0$. $x⊏x^{\prime }y$, therefore, by Proposition A.3, $x⊑x^{\prime }$. Let $z\in O^{\ast }$ be s.t. $x^{\prime }=xz$. $xw=x^{\prime }y=xzy$, therefore $w=zy$ and we can use the induction hypothesis to show that $z\in X_G$. $\mu \in F\left(x^{\prime }\right)=F\left(xz\right)=G\left(z\right)$, implying that $w\in X_G$.

#Proposition A.8

In the setting of the Construction, consider some $x\in X_F$ and define $G:O^{\ast }\to P_C\left(O^{+}\right)$ by $G\left(z\right):=F\left(xz\right)$. Consider any $w\in X_G$. Then, $xw\in X_F$.

#Proof of Proposition A.8

We prove by induction on $\left|w\right|$. For $\left|w\right|=0$, the proposition is obvious. Assume that $\left|w\right|>0$. Then, there is some $w^{\prime }\in X_G$, $\mu \in G\left(w^{\prime }\right)=F\left(x{w}^{\prime }\right)$ and $y\in O^{+}$ s.t. $\mu \left(y\right)>0$ and $w=w^{\prime }y$. By the induction hypothesis, $x{w}^{\prime }\in X_F$. Therefore, $xw=x{w}^{\prime }y$ is also in $X_F$.

#Proposition A.9

In the setting of the Construction, ${\Phi }_F$ factorizes at $x$ for any $x\in X_F$.

#Proof of Proposition A.9

Fix $x\in X_F$. Let $f^x$ be as in Definition 1. Define $G:O^{\ast }\to P_C\left(O^{+}\right)$ by $G\left(z\right):=F\left(xz\right)$. We claim that ${\Phi }_F=f_{\ast }^x({\Phi }_F\times {\Phi }_G)$.

Consider any $\mu \in {\Phi }_F$, $\nu \in {\Phi }_G$ and denote $\xi :=f_{\ast }^x(\mu \times \nu )$. Consider some $z\in X_F$ and $A_z\subseteq O^{+}$ corresponding.

Assume $z=xw$ for some $w\in O^{\ast }$. By Proposition A.7, $w\in X_G$. Note that for any ${\nu }_0\in G\left(w\right)=F\left(z\right)$, ${\nu }_0\left(y\right)>0$ implies $y\in A_z$. Let ${\nu }_w\in P\left(O^{+}\right)$ be as in Proposition A.0. For any $y\in A_z$, we have

$$\nu \left(wy{O}^{\omega }\right)=\nu \left(w{O}^{\omega }\right){\nu }_w\left(y\right)$$

Multiplying both sides by $\mu \left(x{O}^{\omega }\right)$:

$$\mu \left(x{O}^{\omega }\right)\nu \left(wy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right)\nu \left(w{O}^{\omega }\right){\nu }_w\left(y\right)$$

Using the definition of $\xi$ and Proposition A.5, we get

$$\xi \left(z{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right)\nu \left(w{O}^{\omega }\right)$$

$$\xi \left(zy{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right)\nu \left(wy{O}^{\omega }\right)$$

Combining, we get

$$\xi \left(zy{O}^{\omega }\right)=\xi \left(z{O}^{\omega }\right){\nu }_w\left(y\right)$$

Now, assume $x⋢z$. Let ${\mu }_z\in P\left(O^{+}\right)$ be as in Proposition A.0. For any $y\in O^{+}$ s.t. ${\mu }_z\left(y\right)>0$, we have

$$\mu \left(zy{O}^{\omega }\right)=\mu \left(z{O}^{\omega }\right){\mu }_z\left(y\right)$$

Using the definition of $\xi$ and Proposition A.6, we get

$$\xi \left(z{O}^{\omega }\right)=\mu \left(z{O}^{\omega }\right)$$

By Proposition A.3, $x⊏/zy$. Therefore, we can use Proposition A.6 again to conclude

$$\xi \left(zy{O}^{\omega }\right)=\mu \left(zy{O}^{\omega }\right)$$

Combining, we get

$$\xi \left(zy{O}^{\omega }\right)=\xi \left(z{O}^{\omega }\right){\mu }_z\left(y\right)$$

We proved that $\xi \in {\Phi }_F$. It remains to show that, conversely, $\mu \in f_{\ast }^x({\Phi }_F\times {\Phi }_G)$.

Define ${\mu }^x\in P\left(O^{\omega }\right)$ as follows. If $\mu \left(x{O}^{\omega }\right)=0$, choose arbitrary ${\mu }^x\in {\Phi }_G$. If $\mu \left(x{O}^{\omega }\right)>0$, define ${\mu }^x$ by

$${\mu }^x\left(z{O}^{\omega }\right):=\frac{\mu \left(xz{O}^{\omega }\right)}{\mu \left(x{O}^{\omega }\right)}$$

Consider any $w\in X_G$. By Proposition A.8, $xw\in X_F$. By Proposition A.0, there is ${\mu }_{xw}\in F\left(xw\right)$ s.t. for any $y\in A_{xw}$:

$$\mu \left(xwy{O}^{\omega }\right)=\mu \left(xw{O}^{\omega }\right){\mu }_{xw}\left(y\right)$$

If $\mu \left(x{O}^{\omega }\right)>0$, we can divide both sides by $\mu \left(x{O}^{\omega }\right)$ and get

$${\mu }^x\left(wy{O}^{\omega }\right)={\mu }^x\left(w{O}^{\omega }\right){\mu }_{xw}\left(y\right)$$

It follows that, in either case, ${\mu }^x\in {\Phi }_G$ and

$$\mu \left(x{O}^{\omega }\right){\mu }^x\left(z{O}^{\omega }\right)=\mu \left(xz{O}^{\omega }\right)$$

Denote $\xi :=f_{\ast }^x(\mu \times {\mu }^x)$. Consider any $z\in O^{\ast }$.

Assume $z=xw$ for some $w\in O^{\ast }$. By Proposition A.5

$$\xi \left(z{O}^{\omega }\right)=\mu \left(x{O}^{\omega }\right){\mu }^x\left(w{O}^{\omega }\right)=\mu \left(z{O}^{\omega }\right)$$

Now, assume $x⋢z$. By Proposition A.6

$$\xi \left(z{O}^{\omega }\right)=\mu \left(z{O}^{\omega }\right)$$

We conclude that $\mu =\xi$.

#Proposition A.10

In the setting of the construction, consider any $\mu \in {\Phi }_F$ and $e\in O^{\omega }$ s.t. for any $n\in N$, $\mu \left(e_{<n}{O}^{\omega }\right)>0$. Then, there are infinitely many $x\in X_F$ s.t. $x⊏e$.

#Proof of Proposition A.10

We prove by induction on $n$ that there are at least $n$ prefixes of $e$ in $X_F$. For $n=0$ the claim is vacuously true. Consider any $n>0$. By the induction hypothesis, there are $x_0⊏x_1⊏\dots ⊏x_{n-1}⊏e$ s.t. $x_k\in X_F$ for all $k<n$. Without loss of generality, we can assume $A_{x_{n-1}}$ is s.t.

$$\bigcup _{y\in A_{x_{n-1}}}y{O}^{\omega }=O^{\omega }$$

Indeed, if this condition is false we can make it true by adding more elements to $A_{x_{n-1}}$. By Proposition A.0, there is $\nu \in F\left(x_{n-1}\right)$ s.t. for any $y\in A_{x_{n-1}}$

$$\mu \left(x_{n-1}y{O}^{\omega }\right)=\mu \left(x_{n-1}{O}^{\omega }\right)\nu \left(y\right)$$

By the assumption on $A_{x_{n-1}}$, there is $y_0\in A_{x_{n-1}}$ s.t. $x_{n-1}{y}_0⊏e$. Denote $x_n:=x_{n-1}{y}_0$. We get

$$\mu \left(x_n{O}^{\omega }\right)=\mu \left(x_{n-1}{O}^{\omega }\right)\nu \left(y_0\right)$$

The left hand side is positive since $x_n⊏e$, therefore $\nu \left(y_0\right)>0$.\ It follows that $x_n\in X_F$.

#Proof of Proposition 2

By Propositions A.1, A.2 and A.4, ${\Phi }_F\in P_C\left(O^{\omega }\right)$. It remains to show that ${\Phi }_F$ factorizes everywhere.

Consider any $\mu \in {\Phi }_F$. Denote

$$N:=\{e\in O^{\omega }\mid \exists n\in N:\mu (e_{<n}{O}^{\omega })=0\}$$

We have

$$N=\bigcup _{\begin{array}{c}x\in O^{\ast }\\ \mu \left(x{O}^{\omega }\right)=0\end{array}}x{O}^{\omega }$$

Therefore, $\mu \left(N\right)=0$ and $\mu (O^{\omega }\setminus N)=1$. By Proposition A.10, for any $e\notin N$, there are infinitely many $x⊏e$ s.t. $x\in X_F$. By Proposition A.9, it follows that ${\Phi }_F$ factorizes over $e$. We get

$${\mathrm{Pr}}_{e\sim \mu }\left[{\Phi }_F\text{factorizes over}e\right]\ge {\mathrm{Pr}}_{e\sim \mu }[e\notin N]=1$$

0 comments

Comments sorted by top scores.