a unique solution ? iteration involving conditional distributions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:53:20Z http://mathoverflow.net/feeds/question/18477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18477/a-unique-solution-iteration-involving-conditional-distributions a unique solution ? iteration involving conditional distributions rubin 2010-03-17T10:46:46Z 2011-04-04T02:22:13Z <p>consider the following mappings, G and T,</p> <p>$y(s) = [Gx](s)=\exp\left[\sum_{s'}p(s'|s)\log x(s') \right]$</p> <p>$z(s) = [Ty](s)=\sum_{s'}q(s'|s)y(s')e^{-r(s')}$</p> <p>where $0&lt; x(s)\leq 1$ ,$r(s)&lt;0$ , $s,s'\in \{1,2,...,N\}$, and $p(s'|s)$ and $q(s'|s)$ are normalized conditional distributions.</p> <p>(the first mapping is a generalized geometric mean, and the second is an arithmetic mean with some discount)</p> <p>my question is - does iterating these mappings, i.e., $x_{t+1} = T[G(x_t)]$, converges to a unique solution ?</p> http://mathoverflow.net/questions/18477/a-unique-solution-iteration-involving-conditional-distributions/51586#51586 Answer by Didier Piau for a unique solution ? iteration involving conditional distributions Didier Piau 2011-01-09T21:01:26Z 2011-01-09T21:01:26Z <p>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$. </p> <p>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$.</p> <p>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$. </p> <p>If $r(s)>0$ for every $s$ (and I believe this is what the OP wanted to write), then $u(a)&lt;1$ hence $L^tx$ converges geometrically to $0$. If $r(s)&lt;0$ for every $s$ (and this is what the OP actually wrote), then $\ell(a)>1$ hence $L^tx$ diverges geometrically to $+\infty$.</p> <p>For $(x_t)$ to converge to a nondegenerate limit, one should assume that $r$ has positive <strong>and</strong> negative coordinates.</p>