Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.