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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .