I'm stuck trying to prove a statement that seems very reasonable based on computer experiments. For an integer $N$ and any $\epsilon \in (0,1)$, I define a sequence $u_0 = N$ and for all $k\geq 1$: $$u_k = u_{k-1} - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1) + \frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2)$$ The claim is that $$ \sum_{k\geq 0} (u_k - 1) \leq C N \log N$$ for some $0 < C < \infty$ independent of $N$. I don't need $C$ to be explicit, just independent of $N$.

By defining the function $g$ such that $u_k = g(u_{k-1})$, and looking at $g$, I can say that $g$ is increasing, concave, $\lambda$-contracting with $\lambda \leq 1 - \epsilon^2/N = \sup_{u\in[1,N]} \vert g'(u)\vert = \vert g'(1)\vert$, which is not good enough when I compute the sum; I get a bound in $N^2$ instead of the desired $N \log N$.

I've tried looking at $u_{k+1}/u_k$, $u_{k+1} - u_k$, tried to bound $g$ in various ways but couldn't conclude... any help would be hugely appreciated!

  • $\begingroup$ If it helps, I now have that $$ \sum_{k=0}^\tau (u_k-1) \leq C N \log N$$ where $\tau = \inf\{k: u_k \leq 2\}$. This can be proven by looking at the number of iterations $k$ required to go from any $M$ to $\alpha M$ for any $\alpha \in (0,1)$, that is, $k$ such that $u_{n} = M$ implies $u_{n+k} \leq \alpha M$. So I now want to prove the same claim as in my original question, but starting from $u_0 = 2$. Don't know if it's much easier since the problem is mostly "near $1$". $\endgroup$ – Pierrot Jun 19 '13 at 11:54
  • $\begingroup$ Note that if $u_0\in(1,2)$, then $1<u_k<2$ for all $k$ (induction) and $u_k-1\le (1-\frac{\varepsilon^2}{2N})(u_{k-1}-1)$. To sum a geometric progression shouldn't be a big headache. $\endgroup$ – fedja Jun 19 '13 at 16:38
  • $\begingroup$ Aaaah of course! If doing this reasoning from $u_0 = N$ it yields a bound in $N^2$ but from $u_0 = 2$ it yields a bound in $N$, indeed! Thanks fedja, that was a big help. I'll write the full answer for the record. $\endgroup$ – Pierrot Jun 20 '13 at 0:42

Here is the full answer in case you are interested. Let $N\in \mathbb{N}$ and $\epsilon \in (0,1)$, and define $(u_k)_{k\geq 0}$ by $u_0 = N$ and $$u_k = g_{N,\epsilon}(u_{k-1}) = u_{k-1} - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1) + \frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2).$$

Note first that $g_{N,\epsilon}$ is contracting and is such that $g_{N,\epsilon}(1) = 1$, so that $u_k$ goes to $1$ using Banach fixed-point theorem. The contraction coefficient of $g_{N,\epsilon}$ can be bounded by \begin{align*} \sup_{x} \lvert g_{N,\epsilon}'(x) \rvert &\leq g_{N,\epsilon}'(1) = 1 - \frac{\epsilon^2}{2N} < 1, \end{align*} however this contraction coefficient depends on $N$ and a direct use of it yields a bound on $\sum_{k\geq 0} (u_k - 1)$ that is not in $N \log N$.

Note also that even though $u_k$ goes to $1$, we can focus on the partial sum $\sum_{k=0}^{\sigma_2}(u_k-1)$ where $\sigma_2 = \inf\{k : u_k \leq 2\}$, because $\sum_{k=\sigma_2}^\infty (u_k - 1)$ is essentially bounded by $N$. Indeed note that for $u_k\leq 2$ we have $$\frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2)\leq 0$$ so that \begin{align*} u_k - 1 &\leq u_{k-1} - 1 - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1)\\ & \leq (u_{k-1} - 1 )(1 - \frac{\epsilon^2}{2N}) \mbox{ since }u_{k-1}\geq 1 \end{align*} Hence we have \begin{align*} \sum_{k\geq \sigma_2} (u_k-1) &\leq 2 \frac{1}{1 - (1 - \frac{\epsilon^2}{2N})} = \frac{4N}{\epsilon^2} \end{align*} Therefore we can focus on bounding $\sum_{k=0}^{\sigma_2}(u_k - 1)$ by $N\log N$. Let us split this sum into partial sums, where the first partial sum is over indices $k$ such that $N/2 \leq u_k \leq N$, the second is over indices $k$ such that $N/4 \leq u_k \leq N/2$, etc. More formally, we introduce $(k_j)_{j = 0}^J$ such that $k_0 = 0$, $k_1 = \inf\{k: u_k \leq N/2\}$, ..., $k_j = \inf\{k: u_k \leq N/2^j\}$, up to $k_J = \inf\{k: u_k \leq N/2^J\}$ where $J$ is such that $N/2^J \leq 2$, or equivalently \begin{align*} &\log N - J \log 2 \leq \log 2 \\ \Leftrightarrow &\log N / \log 2 - 1 \leq J. \end{align*} For instance we take $J = \lceil \log N / \log 2\rceil$. Thus we have split $\sum_{k=0}^{\sigma_2}(u_k - 1)$ into $J$ partial sums of the form $$ \sum_{k=k_j}^{k_{j+1}} (u_k - 1) $$ and we are now going to bound each of these partial sum by the same quantity $C(\epsilon) N$ for some $C(\epsilon)$ that depends only on $\epsilon$.

To do so, we consider the time needed by $(u_k)_{k\geq 0}$ to from a value $N/m_j$ to a value $N/m_{j+1}$, with $m_{j+1} > m_j$; we will later take $m_j = 2^j$ and $m_{j+1} = 2^{j+1}$. Note that for any $m$ we have \begin{align*} g_{N, \epsilon}\left(\frac{N}{m}\right) &= \frac{N}{m}\left(1 - \frac{\epsilon^2}{2N}(\frac{N}{m}-1) + \frac{\epsilon^3}{6N^2} (\frac{N}{m}-1) (\frac{N}{m}-2)\right)\\ &= \frac{N}{m}\left(1 - \frac{1}{m}\left[\frac{\epsilon^2}{2} - \frac{m \epsilon^2}{2N} - \frac{\epsilon^3}{6m} + \frac{\epsilon^3}{2N} - \frac{m\epsilon^3}{3N^2}\right]\right). \end{align*} Define $$\beta(N,m,\epsilon) = \frac{\epsilon^2}{2} - \frac{m \epsilon^2}{2N} - \frac{\epsilon^3}{6m} + \frac{\epsilon^3}{2N} - \frac{m\epsilon^3}{3N^2}$$ and note that for any $N$ and $m\leq N/2$ we have $$\underline{\beta}(\epsilon) := \frac{\epsilon^2}{4} \leq \beta(N,m,\epsilon),$$ which is clear upon noticing that $\beta(N,m,\epsilon)\geq \beta(N,N/2,\epsilon) = \epsilon^2/4$. For any $x > N/m_{j+1}$ we can check that $$g_{N,\epsilon}(x) \leq \frac{g_{N,\epsilon}(N/m_{j+1})}{N/m_{j+1}} \times x$$ by noticing that $x\mapsto g_{N,\epsilon}(x)/x$ is decreasing. Hence for $k\geq 0$ such that $u_{k-1}\geq N/m_{j+1}$, we have $$u_{k} \leq \left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right) u_{k-1}.$$ Now suppose that for some $k_j\geq 0$ we have $u_{k_j}\leq N/m_j$. Then let us find $K$ such that $u_{k_j+K} \leq N/m_{j+1}$. It is sufficient to find $K$ such that \begin{align*} &\left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right)^{K} \frac{N}{m_j} \leq \frac{N}{m_{j+1}}\\ &\Leftrightarrow K\log \left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right) \leq \log \frac{m_j}{m_{j+1}}\\ &\Leftrightarrow K \geq \log \frac{m_{j+1}}{m_j} \left(-\log\left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right)\right)^{-1} \end{align*} Finally we conclude that $K$ defined as follows $$ K= \left\lceil \left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)}\right\rceil $$ guarantees the inequality $u_{k_j+K} \leq N/m_{j+1}$. In other words $(u_k)_{k\geq 0}$ needs less than $K$ steps to decrease from $N/m_j$ to $N/m_{j+1}$. Summing the terms between $k_j$ and $k_j + K$, we obtain \begin{align*} \sum_{k = k_j}^{k_j+K} u_k &\leq K \frac{N}{m_j}\leq \left\lceil \left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)}\right\rceil \frac{N}{m_j}\\ &\leq \left[\left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)} + 1\right]\frac{N}{m_j}. \end{align*} Taking $m_j = 2^j$ and $m_{j+1} = 2^{j+1}$, we have $k_{j+1}\leq k_j + K$ and thus obtain \begin{align*} \sum_{k = k_j}^{k_{j+1}} u_k \leq \sum_{k = k_j}^{k_j+K} u_k &\leq \left[\left(\log 2\right) \frac{2^{j+1}}{\underline\beta(\epsilon)} + 1\right]\frac{N}{2^j}\\ &\leq \left[\left(\log 2\right) \frac{2}{\underline\beta(\epsilon)} + \frac{1}{2^j}\right]N\\ &\leq C(\epsilon) N \end{align*} with $C(\epsilon) = \left(\log 2\right) \frac{2}{\underline\beta(\epsilon)} + \frac{1}{2}$. To summarize the full sum can be bounded as follows \begin{align*} \sum_{k\geq 0} (u_k - 1) &\leq \sum_{k=0}^{\sigma_2} (u_k - 1) + \sum_{k\geq \sigma_2} (u_k - 1)\\ &\leq \sum_{j=1}^J \sum_{k=k_{j-1}}^{k_j} u_k + \frac{4N}{\epsilon^2} \\ &\leq \left\lceil \frac{\log N}{\log 2} \right\rceil C(\epsilon)N + \frac{4N}{\epsilon^2} \\ &\leq D(\epsilon) N \log N \end{align*} for some $D(\epsilon)$ that depends only on $\epsilon$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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