0
$\begingroup$

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} = TG(x_t)$, converges to a unique solution?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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