3
$\begingroup$

There is a sequence of numbers $a_0, a_1, a_2, \ldots$ which I would like to approach zero as fast as possible. This sequence evolves according to the recursion

$ a_{t+1} = (1-0.001 b_t)a_t + 50 b_t^2,$

where $b_t$ is a sequence I have control over. Specifically, I need to pick a nonnegative sequence $b_0, b_1, b_2, \ldots$ so that $a_t$ goes to zero as fast as possible. Moreover, I need to pick all the $b_t$ ``ahead of time,'' that is, without any knowledge of what $a_0, a_1, \ldots$ might be. The only thing I do know is that $a_0$ is positive. My question is: what is the best choice of $b_t$?

Its clear to me that I can send $a_t$ to $0$ by picking $b_t$ which goes to zero slowly enough (e.g. $b_t=1/t$ works). But I'm having trouble working out what gives the best possible convergence rate.

More generally, I'd be interested in how to pick $b_t$ to get optimize the rate at which $ a_{t+1} = (1-c b_t) a_t + d b_t^2$ approaches zero, where $c,d>0$ and, if it makes a difference, $c$ is a number which is really, really close to zero.

  • 0
    `without any knowledge of what a0,a1,… might be` uh? If we give a sequence b0 b1... , the sequence a1 a2... is determined, the only degree of indeterminancy is the starting value (say, a_0)2011-05-11

2 Answers 2

1

What about $b_t=\frac{ca_t}{2d}$ found by taking the derivative of $a_{t+1}$ with respect to $b_t$ and setting to zero? The second derivative test says this minimizes $a_{t+1}$. For small $c$ and large $d$ it still doesn't fall very fast, $\frac{c^2}{4d}$ per step for $a_t \approx 1$, but I don't see how you will do better.

  • 0
    Unfortunately, I need to pick the entire sequence $b_t$ ahead of time, without knowledge of $a_0, a_1, \ldots$. I'll edit the question to clarify this.2011-05-11
1

We have $a_t = M_t a_0 + A_t$ where $M_t = \prod_{j=0}^{t-1} (1 - c b_j)$. You could take $b_0 = 1/c$ which makes $M_t = 0$ for all $t$, and $a_1 = A_1 = d/c^2$. Then to minimize $A_{t+1}$ given $A_t$, take $b_t = c A_t/(2 d)$, resulting in $A_{t+1} = A_t (1 - \frac{c^2}{4d} A_t)$. Then $A_t = \frac{4d}{c^2} y_t$ where $y_1 = 1/4$ and $y_{t+1} = y_t (1 - y_t)$. This sequence will go to 0 with, I think, $y_t \approx 1/(t + \ln(t))$ as $t \to \infty$.