Monotonically increasing intervals

Problem  A real sequence \{T_n\}_{n\ge1} satisfies T_{n+1}+T_{n}=2n^\alpha for all n\ge1, where 1<\alpha<2. Let \Delta_{n}:=T_{n+1}-T_n be the length of the nth interval. Show that there exists a unique T_1 such that \Delta_{n+1}>\Delta_n for all n\ge1.

Fig. 1. Nonlinearly mapped intervals (pdf version)

Remark  This is a problem that arises from nonlinear quantization in AAC. There, MDCT coefficient x is power-compressed to y=x^{3/4} before linear quantization. Then we face the problem of choosing boundaries T_n, T_{n+1} for the nth quantization interval where all x\in [T_n, T_{n+1}] are quantized to n and de-quantized to \bar{x}=n^{4/3}, such that the de-quantization noise \bar{x}-x is minimized statistically. Of course, the solution to this problem depends on the underlying probability distribution of x. In case of uniform distribution, the de-quantized value n^{4/3} should be at the center of the nth interval, or T_n + T_{n+1} = 2n^{4/3}. With this restriction, all the boundaries \{T_n\}_{n>1} are uniquely determined by T_1. But the length of the interval \Delta_n=T_{n+1}-T_n, as revealed by numerical experiments, almost always undulates and at the same time, asymptotically increases to \infty as n\to\infty (\sim \tfrac43n^{1/3} ), for a randomly chosen T_1. Then, is there a T_1 to make the length of the interval monotonically increase? The answer is yes, and this T_1 is uniquely determined by \alpha, as shown in the following.

Proof  Let us denote the difference of nth and (n+1)th intervals’ lengths by \Gamma_n:=\Delta_{n+1}-\Delta_n. We claim that \Gamma_n>\Gamma_{n+2} for all n\ge1. If so, to ensure \Gamma_n>0 for all n\ge1, then we need to show that there exists a unique T_1 such that both \lim_{n\to\infty}\Gamma_{2n} and \lim_{n\to\infty}\Gamma_{2n+1} exist and are non-negative. First, by the relation T_n+T_{n+1}=2n^\alpha, we have \Gamma_n=2(n+1)^\alpha+2n^\alpha-4T_{n+1}. Furthermore, let f(x):=(x+1)^\alpha-x^\alpha, then

\begin{array}{rcl} \Gamma_{n+2}-\Gamma_n  & = & 2(n+3)^\alpha+2(n+2)^\alpha-2(n+1)^\alpha-2n^\alpha-4T_{n+3}+4T_{n+1} \\  & = & 2(n+3)^\alpha-6(n+2)^\alpha+6(n+1)^\alpha-2n^\alpha \\  & = & 2(f(n+2)-2f(n+1)+f(n)) \\  & = & 2f''(\eta_n), \end{array}

where \eta_n\in(n,n+2) and the last equation is due to recursive application of Rolle’s theorem (first about f(x+1)-f(x), then about about f(x)).  Since f''(x)=\alpha(\alpha-1)[(x+1)^{\alpha-2}-x^{\alpha-2}]<0 for x>0 when 1<\alpha<2, we have f''(\eta_n)<0 thus \Gamma_{n+2}-\Gamma_n<0. Next, consider the limit of \Gamma_{2n}+\Gamma_{2n+1}:

\begin{array}{rcl} \Gamma_{2n}+\Gamma_{2n+1}  & = & \Delta_{n+2}-\Delta_n \\  & = & T_{n+3}-T_{n+2}-T_{n+1}+T_n \\  & = & T_{n+3}+T_{n+2}-2T_{n+2}-2T_{n+1}+T_{n+1}+T_n \\  & = & 2[f(n+1)-f(n)] \\  & \xrightarrow{n\to\infty} & 0, \end{array}

where the last equation is due to \lim_{x\to\infty}f'(x)=0 for 1<\alpha<2. Thus, the desired T_1, if it ever exits, must ensure \lim_{n\to\infty}\Gamma_{2n}=0. Conversely, if with some T_1, \lim_{n\to\infty}\Gamma_{2n}=0, then \Gamma_n>0 for all n\ge1.

Now, if suffices to show there exists a unique T_1 such that \lim_{n\to\infty}\Gamma_{2n}=0. Let S_n:=(n-1)^\alpha-(n-2)^\alpha+\cdots+(-1)^n, then T_n=2S_n-(-1)^nT_1. We claim that \xi_n:=(2n+\tfrac12)^\alpha-2S_{2n+1} converges as n\to\infty. In that case, we shall have

\begin{array}{rcl} \Gamma_{2n}  & = & 2(2n+1)^\alpha+2(2n)^\alpha-4T_{2n+1} \\  & = & 2(2n+1)^\alpha+2(2n)^\alpha-8S_{2n+1}-4T_1 \\  & = & 2(2n+1)^\alpha+2(2n)^\alpha-4(2n+\tfrac12)^\alpha+4\xi_n-4T_1 \\  & = & 2[g(2n+\tfrac12)-g(2n)]+4\xi_n-4T_1 \\  &\xrightarrow{n\to\infty} & 4\xi_n-4T_1, \end{array}

where g(x):=(x+\tfrac12)^\alpha-x^\alpha and the last equation above follows from \lim_{x\to\infty}g'(x)=0 when 1<\alpha<2. Therefore, the unique T_1 will be \lim_{n\to\infty}\xi_n. It remains to show that \{\xi_n\}_{n\ge1} does converge.

Let us investigate the difference between \xi_n and \xi_{n+1}:

\begin{array}{rcl} \xi_{n+1}-\xi_n  & = & (2n+\tfrac52)^\alpha-(2n+1)^\alpha-2[(2n+2)^\alpha-(2n+1)^\alpha] \\  & = & f(2n+\tfrac32)+f(2n+\tfrac12)-2f(2n+1) \\  & = & \tfrac14\alpha(\alpha-1)(\alpha-2)\theta_n^{\alpha-3}, \end{array}

where \theta_n\in(2n+\tfrac12,2n+\tfrac52) and the last equation is also due to recursive application of Rolle’s theorem. (First about f(x+\tfrac12)-f(x), then about f(x), and finally about x^\alpha.) Therefore, we have \xi_{n+1}-\xi_n=\mathcal{O}(n^{\alpha-3}), which implies that \xi_n converges.

This completes the proof.                                                                                                        \square

Advertisements

About Shuhua Zhang

Born in Anhui, China. Awarded a doctor's degree in electronic engineering from Tsinghua University. Now a postdoc researcher working on audio and speech signal processing, especially source separation, in gipsa-lab, Grenoble-INP, France.
This entry was posted in Analysis, mathematics, signal processing. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s