a unique solution ? iteration involving conditional distributions

2010-03-17T10:46:46Z

consider the following mappings, G and T,

$y(s) = [Gx](s)=\exp\left[\sum_{s'}p(s'|s)\log x(s') \right]$

$z(s) = [Ty](s)=\sum_{s'}q(s'|s)y(s')e^{-r(s')}$

where $0< x(s)\leq 1$ ,$r(s)<0$ , $s,s'\in \{1,2,...,N\}$, and $p(s'|s)$ and $q(s'|s)$ are normalized conditional distributions.

(the first mapping is a generalized geometric mean, and the second is an arithmetic mean with some discount)

my question is - does iterating these mappings, i.e., $x_{t+1} = T[G(x_t)]$, converges to a unique solution ?

Answer by Didier Piau for a unique solution ? iteration involving conditional distributions

2011-01-09T21:01:26Z

The transformation $L=TG$ is defined on vectors $x$ with positive coordinates by $$ [Lx](s)=\sum_uq(u|s)\mathrm{e}^{-r(u)}[Mx](u),\quad\mbox{where}\ [Mx](s)=\prod_ux(u)^{p(u|s)}. $$ Thus $M$ and $L$ are homogenous and nondecreasing on the positive orthant. This means that one considers vectors $x$ such that $x(s)>0$ for every $s$, that $M(\lambda x)=\lambda Mx$ and $L(\lambda x)=\lambda L(x)$ for every positive scalar $\lambda$, and that $Mx\le M\tilde x$ and $Lx\le L\tilde x$ if $x\le\tilde x$ in the sense that $x(s)\le\tilde x(s)$ for every $s$.

For every vector $x$ with positive coordinates, let $u(x)$ and $\ell(x)$ denote the supremum and the infimum of its coordinates $x(s)$, hence $\ell(x)\le x(s)\le u(x)$ for every $s$.

Since $p$ is a transition kernel, $\displaystyle\sum_up(u|s)=1$ for every $s$ hence $\ell(x)\le[Mx](s)\le u(x)$ for every $s$ and $\ell(x)a(s)\le[Lx](s)\le u(x)a(s)$ with $$ a(s)=\sum_uq(u|s)\mathrm{e}^{-r(u)}. $$ More generally, for every positive $t$, $$ \ell(x)\ell(a)^{t-1}a(s)\le [L^tx](s)\le u(x)u(a)^{t-1}a(s), $$ hence $$ \ell(x)\ell(a)^{t}\le \ell(L^tx)\le u(L^tx)\le u(x)u(a)^{t}. $$ Furthermore, $u(a)\le u(\mathrm{e}^{-r})$ and $\ell(a)\ge\ell(\mathrm{e}^{-r})$. Now everything depends on the hypothesis made on $r$.

If $r(s)>0$ for every $s$ (and I believe this is what the OP wanted to write), then $u(a)<1$ hence $L^tx$ converges geometrically to $0$. If $r(s)<0$ for every $s$ (and this is what the OP actually wrote), then $\ell(a)>1$ hence $L^tx$ diverges geometrically to $+\infty$.

For $(x_t)$ to converge to a nondegenerate limit, one should assume that $r$ has positive and negative coordinates.

a unique solution ? iteration involving conditional distributions - MathOverflow

a unique solution ? iteration involving conditional distributions

Answer by Didier Piau for a unique solution ? iteration involving conditional distributions