Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Have you tried $b_t=t^{-n}$ for $n > 1$ and $b_t-\alpha^t$ for $0 < \alpha < 1$ as the usual suspects? –  J. M. May 10 '11 at 19:26
    
@J.M. - unless I am mistaken, neither of the two possibilities you suggest result in $a_t$ approaching zero. A necessary condition for a nonnegative $b_t$ to result in $a_t \rightarrow 0$ is that $\sum_t b_t = +\infty$. –  robinson May 10 '11 at 19:28
    
(I am assuming your second suggestion was $b_t=\alpha^t$) –  robinson May 10 '11 at 19:29
    
It is important to keep $b_t d < a_t c$ in order for $a_t$ to approach 0. As you don't know $a_t$ how can you say that J.M.'s series don't approach 0? –  Fabian May 10 '11 at 19:31
    
@Fabian: because the sequence defined by $a_{t+1} = (1-0.001 \alpha^t) a_t$ does not approach zero for any $\alpha \in (0,1)$. So certainly neither does the sequence defined by $a_{t+1} = (1-0.001 \alpha^t) a_t + 50 \alpha^{2t}$. –  robinson May 10 '11 at 19:32

2 Answers 2

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.

share|improve this answer
    
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. –  robinson May 11 '11 at 18:41

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$.

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.