When are all average trajectories of $w_{k+1}=Aw_k+b$ bounded?

39 Views Asked by At

Suppose observation $x$ is drawn from some distribution $\mathcal{D}$, $w_0\in \mathbb{R}^d$, and my update has the following form (cross-posted on MO)

$$w_{k+1}=(I-xx')w_k+b$$

When are average trajectories $u_k=E[w_k]$ bounded? Expectation is taken over all sequences of IID observations $x_1,\ldots,x_k$. Motivation for this recurrence is here.

In particular I'm wondering the following -- if $u_k$ are bounded for $b=0$, are they also bounded for some other value of $b$?

The cases of increasing difficulty are

  1. $b=0$
  2. $b=(1,1,1,\ldots$
  3. $b=Bx$ for some matrix $B$
  4. $b$ is drawn from some distribution $\mathcal{D}_2$ independent of $x$
  5. $b,x$ are drawn jointly from some distribution $\mathcal{D}_3$

For the case of $b=0$, there's a simple necessary and sufficient condition for all trajectories $u_k$ to converge to 0 regardless of starting point -- the following must hold for all symmetric matrices $A$

$$E[(x'Ax)^2]<2 E[x'A^2 x]$$