Figure <ref> shows the $s$-stage MIMO state-amplification problem. As we discussed before, the first controller $C_1$ is the transmitter, and the second controller $C_2$ is the receiver. The transmitter knows the state $x[0]$ at the initial time and learns the channel noise $v_2[n]$ by causal feedback. The goal of communication is minimizing the estimation error of the state $x[0]$ at the receiver.

Let's formally state the $s$-stage MIMO state-amplification with feedback problem.
[$s$-stage MIMO state-amplification with feedback]
Let the underlying random variables $x[0] \sim \mathcal{N}(0,\sigma_0^2)$ and $v_2[n] \sim \mathcal{N}(0,\sigma_{v}^2)$ be all independent.  These are the source and observation noise respectively. The transmitter's input $u_1[n]$ is a function on $x[0]$ and $v_2[1], \cdots,v_2[n-1]$, i.e.

\begin{align}
\end{align}

The receiver's observations $y_2[n]$ are given as follows.

\begin{align}
&y_2[k-1]=a^{k-1}x[0]+a^{k-2}u_1[0]+\cdots +u_1[k-2]+v_2[k-1]
\end{align}

The receiver generates an estimate $\widehat{x[0]}$ of the state $x[0]$ based on its received signal $y_2[1:k-1]$, i.e. $\widehat{x[0]}=g(y_2[1:k-1])$. The objective of the system is minimizing the quadratic estimation error, $\mathbb{E}[(x[0]-\widehat{x[0]})^2]$.

This problem can be more compactly represented as Figure <ref> by thinking of the MIMO channel as a channel with memory. As shown in <cit.>, feedback only increases the capacity at most a half bit per time step. However, in this problem we are using the channels for $k$ time steps, so we still have to justify that the feedback does not increase the capacity too much. The following lemma explicitly computes an information-theoretic cutset bound for this communication problem and gives a reasonable bound on the rate-distortion tradeoff.

Let's consider the problem of Figure <ref>.

(i) Let $x[0] \sim \mathcal{N}(0,\sigma_0^2)$ and $v_2[n] \sim \mathcal{N}(0,\sigma_{v}^2)$.
Let $w \in \mathbb{R}$ satisfy $|\frac{1}{a^2 w}|<1$ and the input power constraint is

\begin{align}
(1-w)\mathbb{E}[u_1^2[0]]+ (1-w)w\mathbb{E}[u_1^2[1]]+ \cdots + (1-w)w^{k-2}\mathbb{E}[u_1^2[k-2]] \leq P
\end{align}

Then, the estimation error of $x[0]$ based on $y_2[0:k-1]$ is lower bounded by

\begin{align}
\mathbb{E}[(x[0]-\widehat{x[0]})^2] \geq \frac{\sigma_0^2}{2^{2I_k}}
\end{align}

\begin{align}
I_k = \frac{k}{2} \log( 1 + \frac{1}{k\sigma_v^2}(\frac{2a^{2(k-1)} \sigma_0^2 }{1-a^{-2}}  + \frac{2 a^{k-2} }{1-a^{-2}} \frac{P}{(1-\frac{1}{ a^2 w})(1-w)})).
\end{align}

(ii) Consider the same problem as (i) except that $v_2[k-1] \sim \mathcal{N}(0,\sigma_v'^2)$, i.e. only the last observation noise variance is different. Then, the estimation error based on $y_2[0:k-1]$ is lower bounded by

\begin{align}
\mathbb{E}[(x[0]-\widehat{x[0]})^2] \geq \frac{\sigma_0^2}{2^{2I_k'}}
\end{align}

\begin{align}
+\frac{1}{2}\log(1 + \frac{1}{\sigma_{v}'^2}(
2 a^{2(k-1)} \sigma_0^2 + 2\frac{a^{2(k-2)}}{1-\frac{1}{a^2 w}} \frac{P}{1-w})).
\end{align}

(iii) Consider the same problem as (ii) except that $v_2[k-1] \sim Unif[-\sigma_{v}',\sigma_{v}']$, i.e. the last observation is a uniform random variable. Then, the estimation error based on $y_2[0:k-1]$ is lower bounded by

\begin{align}
\mathbb{E}[(x[0]-\widehat{x[0]})^2] \geq \frac{\sigma_0^2}{2^{2I_k''}}
\end{align}

\begin{align}
I_k''=I_k'+\frac{1}{2}\log(\frac{\pi e }{2}).
\end{align}

(i) First, we can lower bound the estimation error as follows:

\begin{align}
&\frac{1}{2}\log( 2 \pi e \mathbb{E}[(x[0] - \widehat{x[0]})^2])\\
&\geq h(x[0]-\widehat{x[0]}| y_2[0:k-1])\\
&=h(x[0]| y_2[0:k-1])\\
&=h(x[0])- I(x[0]; y_2[0:k-1]) \\
&\geq \frac{1}{2}\log(2 \pi e \sigma_0^2) - I(x[0]; y_2[0:k-1]). \label{eqn:reduced1}
%&=h(a^k x[0])- h(y_2[0:k-1]) + h(y_2[0:k-1]|a^k x[0])
\end{align}

We will upper bound the mutual information. Let's first upper bound the received signal power. Since $u_1[n]$ is a strictly causal function of $v_2[n]$,

\begin{align}
&\mathbb{E}[y_2^2[n]] \leq 2 \mathbb{E}[(a^n x[0])^2] + 2 \mathbb{E}[(a^{k-2}u_1[0]+u_1[n-1])^2] + \mathbb{E}[v_2^2[n]].\\
\end{align}

By Lemma <ref>, we have

\begin{align}
&\leq \frac{a^{2(n-1)}}{1 - \frac{1}{a^2 w}} \frac{P}{1-w}.
\end{align}

Therefore, the received signal power is upper bounded as

\begin{align}
&\mathbb{E}[y_2^2[n]] \leq 2 a^{2n} \sigma_0^2 + 2 \frac{a^{2(n-1)}}{1 - \frac{1}{a^2 w}} \frac{P}{1-w} + \mathbb{E}[v_2^2[n]].
\end{align}

Thus, we can conclude

\begin{align}
&\sum_{0 \leq n \leq k-1} \mathbb{E}[y_2^2[n]] \\
&\leq \sum_{0 \leq n \leq k-1} 2a^{2n} \sigma_0^2 + 2 \frac{a^{2(n-1)}}{1 - \frac{1}{a^2 w}} \frac{P}{1-w} + \sigma_v^2\\
&= 2( 1+ \cdots +a^{2(k-1)}) \sigma_0^2 + \sum_{0 \leq n \leq k-1}2 \frac{a^{2(n-1)}}{1 - \frac{1}{a^2 w}} \frac{P}{1-w} + k\sigma_v^2\\
&= 2a^{2(k-1)} \frac{1-a^{-2k}}{1-a^{-2}} \sigma_0^2 + 2 a^{k-2} \frac{1-a^{-2k}}{1-a^{-2}} \frac{P}{(1-\frac{1}{a^2 w})(1-w)} + k\sigma_v^2\\
&\leq   \frac{2a^{2(k-1)} \sigma_0^2 }{1-a^{-2}}  + \frac{2 a^{k-2} }{1-a^{-2}} \frac{P}{(1-\frac{1}{a^2 w})(1-w)} + k\sigma_v^2.
\end{align}

Using this, we can upper bound the mutual information.

\begin{align}
&I(x[0]; y_2[0:k-1]) \\
&\leq h(y_2[0:k-1]) - h(y_2[0:k-1]| x[0]) \\
&\leq \sum_{0 \leq n \leq k-1} h(y_2[n]) - \sum_{0 \leq n \leq k-1} h(v_2[n])\\
&\leq \sum_{0 \leq n \leq k-1} \frac{1}{2}\log( 2 \pi e \mathbb{E}[y_2[n]^2]) - \frac{k-1}{2} \log(2 \pi e \sigma_v^2) \\
&=\frac{1}{2} \log( \prod_{0 \leq n \leq k-1} \frac{\mathbb{E}[y_2[n]^2]}{\sigma_v^2})\\
&\leq \frac{1}{2} \log\left( ( \frac{1}{k} \sum_{0 \leq n \leq k-1} \frac{\mathbb{E}[y_2[n]^2]}{\sigma_v^2})^{k-1}\right) \\
&(\because \mbox{geometric mean and arithmetic mean})\\
&\leq \frac{1}{2} \log\left(( 1 + \frac{1}{k\sigma_v^2}(\frac{2a^{2(k-1)} \sigma_0^2 }{1-a^{-2}}  + \frac{2 a^{k-2} }{1-a^{-2}} \frac{P}{(1-\frac{1}{a^2 w})(1-w)}))^{k}\right) \label{eqn:reduced2}
\end{align}

The last term is $I_k$. By plugging (<ref>) into (<ref>), we get

\begin{align}
\mathbb{E}[(x[0] - \widehat{x[0]})^2] \geq \frac{\sigma_0^2}{2^{2I_k}}
\end{align}

which finishes the proof.

(ii) We have

\begin{align}
&I( x[0]; y_2[0:k-1]) \\
&\leq h(y_2[0:k-1]) - h(y_2[0:k-1]| x[0]) \\
&\leq \sum_{0 \leq n \leq k-1} h(y_2[n]) - \sum_{0 \leq n \leq k-1} h(v_2[n])\\
&\leq \sum_{0 \leq n \leq k-1} \frac{1}{2}\log( 2 \pi e \mathbb{E}[y_2[n]^2]) - \frac{k-1}{2} \log(2 \pi e \sigma_v^2)
- \frac{1}{2} \log(2 \pi e \sigma_v'^2) \\
&=\frac{1}{2} \log( \prod_{0 \leq n \leq k-2} \frac{\mathbb{E}[y_2[n]^2]}{\sigma_v^2}) + \frac{1}{2}\log( \frac{\mathbb{E}[y_2[k-1]^2]}{\sigma_v'^2})\\
&\leq \frac{1}{2} \log( \frac{1}{k-1} \sum_{0 \leq n \leq k-2} \frac{\mathbb{E}[y_2[n]^2]}{\sigma_v^2})^{k-1} + \frac{1}{2}\log( \frac{\mathbb{E}[y_2[k-1]^2]}{\sigma_v'^2})\\
&(\because \mbox{geometric mean and arithmetic mean})\\
&\leq \frac{1}{2} \log( 1 + \frac{1}{(k-1)\sigma_v^2}(\frac{2a^{2(k-2)} \sigma_0^2 }{1-a^{-2}}  + \frac{2 a^{k-3} }{1-a^{-2}} \frac{P}{(1-\frac{1}{a^2 w})(1-w)}))^{k-1} \\
&+\frac{1}{2}\log(1 + \frac{1}{\sigma_{v}'^2}(
2 a^{2(k-1)} \sigma_0^2 + 2\frac{a^{2(k-2)}}{1-\frac{1}{a^2 w}} \frac{P}{1-w}
)). \label{eqn:reduced3}
\end{align}

The last term is $I_k'$. By plugging (<ref>) into (<ref>), we get

\begin{align}
\mathbb{E}[(x[0] - \widehat{x[0]})^2] \geq \frac{\sigma_0^2}{2^{2I_k'}}
\end{align}

which finishes the proof.

(iii) We can repeat the proof of (ii) replacing the distribution of $v_2[k-1]$ by uniform.

In this lemma, the bound of (ii) is tighter than that of (i) since it excludes the last observation in the arithmetic-geometric inequality, but it is harder to compute. We also allow the variance of the last observation noise to be different from the other ones, since we will replace it with another distribution to adapt large deviation ideas.[Even though large deviation ideas usually introduce a sequence of atypical noise, here the SNR of the last observation dominates the SNR of all the other observations. Thus, it is enough to introduce atypically large noise only to the last observation.]

§.§ Lower bound on the optimal cost based on Witsenhausen's counterexample

Now, we can combine the previous results to derive a lower bound that will approximately match with $s$-stage signaling strategies. We will derive a lower bound on the weighted average cost of Problem <ref>, i.e. we will find functions $D_{L,i}(\widetilde{P_1},\widetilde{P_2})$ such that

\begin{align}
\inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]] \geq \min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_{L,i}(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}.\end{align}

Here, the lower bounds $D_{L,i}(\widetilde{P_1},\widetilde{P_2})$ can be thought as a lower bound on $D(P_1,P_2)$, the power-disturbance tradeoff, of Problem <ref>. The first bound $D_{L,1}$ is given in the following lemma, and the rest will be given in Lemma <ref> of page cov:lemma2.

Define $S_{L,1}$ as the set of $(k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma)$ such that

\begin{align}
&k_1,k_2,k \in \mathbb{N}, \sigma_{v2}',\alpha,\Sigma \in \mathbb{R}_+, \\
&k_1 \geq 1, k_2 - k_1 -1 \geq 0, k \geq k_2,\\
&\sigma_{v2}' \geq 0, 0 \leq \alpha \leq 1,\\
&0 \leq \Sigma \leq
\left\{\begin{array}{ll}
1 &\mbox{when }k_1 =1\\
\frac{a^{2(k_1-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2} & \mbox{when } k_1 \geq 2
\end{array}
\right.
\end{align}

We also define $D_{L,1}(\widetilde{P_1},\widetilde{P_2};k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma )$ as follows:

\begin{align}
&D_{L,1}(\widetilde{P_1},\widetilde{P_2};k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma) \\
\alpha (\sqrt{c \frac{a^{2(k-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}}
- \sqrt{ c \frac{a^{2(k-k_1-1)}(1-(2.5a^{-2})^{k_2-k_1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}} } \\
&- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{ 2.5^{k_2-k_1} \widetilde{P_1}}{1-2.5^{-1}} }
- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}} })_+^2 \label{eqn:witsenlower1} \\
&+(1-\alpha) ( \sqrt{\frac{a^{2(k-k_1-1)}\Sigma}{2^{2I''(\widetilde{P_1})}}}
-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{2.5 \widetilde{P_1}}{1-2.5^{-1}}}\label{eqn:witsenlower2} \\
&-\sqrt{\frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}}} )_+^2
+1 \label{eqn:witsenlower3}
\end{align}

\begin{align}
&I''(\widetilde{P_1})= \left \{
\begin{array}{ll}
\frac{{k_2-k_1-1}}{2} \log(1+\frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(\frac{2a^{2(k_2-2-k_1)}}{1-a^{-2}}\Sigma + \frac{2a^{2(k_2-3-k_1)} }{1-a^{-2}} \frac{2.5\widetilde{P_1}}{(1-2.5a^{-2})(1-2.5^{-1})}))  & \mbox{if } k_2-k_1-1>0\\
0 & \mbox{if } k_2-k_1-1=0
\end{array} \right.
\\
&I'(\widetilde{P_1})= I''(\widetilde{P_1})+\frac{1}{2} \log(1+ \frac{1}{\sigma_{v2}'^2}(2a^{2(k_2-1-k_1)}\Sigma + 2 \frac{a^{2(k_2-2-k_1)}\widetilde{P_1}}{(1-2.5a^{-2})(1-2.5^{-1})})) + \frac{1}{2} \log( \frac{2 \pi e}{4} ) \mathbf{1}(\sigma_{v2} \neq \sigma_{v2}')\\
\begin{array}{ll}
\frac{2\sigma_{v2}'}{\sqrt{2\pi}\sigma_{v2}}\exp(-\frac{\sigma_{v2}'^2}{2 \sigma_{v2}^2}) & \mbox{if }\sigma_{v2} \neq \sigma_{v2}' \\
1 & \mbox{if } \sigma_{v2}= \sigma_{v2}'\\
\end{array}
\right.
\end{align}

Let $|a| \geq 2.5$. Then, for all $q, r_1, r_2 \geq 0$, the minimum cost (<ref>) of Problem <ref> is lower bounded as follows:

\begin{align}
&\inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]\\
& \geq \sup_{(k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma) \in S_{L,1}}\min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_{L,1}(\widetilde{P_1},\widetilde{P_2};k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}.
\end{align}

For simplicity, we assume $a\geq 2.5$, $k_1 \geq 2$, $k_2-k_1-1 > 0$, $k > k_2$, $\sigma_{v2} \neq \sigma_{v2}'$. The remaining cases when $a \leq -2.5$ or $k_1 = 1$ or $k_2 -k_1 -1 =0$ or $k=k_2$ or $\sigma_{v2} = \sigma_{v2}'$ easily follow with minor modifications.

$\bullet$ Geometric Slicing: We first apply the geometric slicing idea of Section <ref> to get a finite-horizon problem. By setting $\alpha=2.5^{-1}$ in Lemma <ref>, the average cost is lower bounded by

\begin{align}
&\inf_{u_1, u_2}(
q \mathbb{E}[x^2[k]] \\
&+r_1 \underbrace{((1-2.5^{-1}) \mathbb{E}[u_1^2[k_1]] + (1-2.5^{-1})2.5^{-1}\mathbb{E}[u_1^2[k_1+1]]+ \cdots+(1-2.5^{-1}) 2.5^{-k+1+k_1} \mathbb{E}[u_1^2[k-1]] )}_{:=\widetilde{P_1}}\\
&+r_2 \underbrace{((1-2.5^{-1}) \mathbb{E}[u_2^2[k_2]] + (1-2.5^{-1})2.5^{-1}\mathbb{E}[u_2^2[k_2+1]]+ \cdots+(1-2.5^{-1}) 2.5^{-k+1+k_2} \mathbb{E}[u_2^2[k-1]] )}_{:=\widetilde{P_2}})
\end{align}

Here, we denote the second and the third terms as $\widetilde{P_1}$ and $\widetilde{P_2}$ respectively. As we mentioned in Figure <ref>, <ref> and <ref>, we will relax the problem in two different ways — one with state disturbance $w[0]$ and the other one with $w[1]$. Let's start with the former.

$\bullet$ Large deviation idea: As mentioned in Section <ref>, we will apply large deviation ideas[As mentioned before, large deviation theory replaces whole noise sequence as atypical one. However, for the simplicity of computation, we will only replace the last observation noise. Precisely, the Gaussian observation noise $v_2[k_2-1]$ will behave like a uniform observation noise with larger variance with a certain probability. Thus, we can replace $v_2[k_2-1]$ with a uniform random variable with larger variance by multiplying by the corresponding probability. See <cit.> for the details of the idea.] to $v_2[k_2-1]$. For this, we write $v_2[k_2-1]$ as a mixture of two independent random variables:

\begin{align}
v_2[k_2-1]=C \cdot v_2'[k_2-1] + (1-C) v_2''[k_2-1]
\end{align}

where $C, v_2'[k_2-1], v_2''[k_2-1]$ are independent random variables whose distributions are given as follows:

\begin{align}
&v_2'[k_2-1] \sim Unif[-\sigma_{v2}',\sigma_{v2}']\\
&f_{v_2''[k_2-1]}(v) = \left \{ \begin{array}{ll}
\frac{1}{1-c} \frac{1}{\sqrt{2\pi} \sigma_{v2}} \exp(- \frac{v^2}{2 \sigma_{v2}^2}) & \mbox{for }|v| > \sigma_{v2}' \\
\frac{1}{1-c} \frac{1}{\sqrt{2\pi} \sigma_{v2}} (\exp(- \frac{v^2}{2 \sigma_{v2}^2})-\exp(- \frac{\sigma_{v2}'^2}{2 \sigma_{v2}^2}) ) &\mbox{for }|v| \leq \sigma_{v2}'
\end{array} \right. \\
\left \{ \begin{array}{ll}
1 &\mbox{w.p. } c \\
0 &\mbox{w.p. } 1-c
\end{array} \right.
\end{align}

where $c = \frac{2\sigma_{v2}'}{\sqrt{2 \pi} \sigma_{v2}} \exp(- \frac{\sigma_{v2}'^2}{2 \sigma_{v2}^2})$.

$\bullet$ Three stage division: As mentioned in Section <ref>, we will divide the finite-horizon problem into three time intervals.
The following definitions of  $U_{ij}$ correspond to the first and second controller's input in these three intervals shown in Figure <ref>, where the index $i$ and $j$ represent the controllers and time intervals respectively.

\begin{align}
&W:=aw[k-2]+\cdots + a^{k-1}w[0]\\
&U_{11}:=a^{k-2} u_1[1] + \cdots + a^{k-k_1} u_1[k_1-1]\\
&U_{12}:=a^{k-k_1-1} u_1[k_1]+ \cdots + a^{k-k_2} u_1[k_2-1]\\
&U_{13} := a^{k-k_2-1} u_1[k_2]+ \cdots + u_1[k-1] \\
&U_{21}:=a^{k-2} u_2[1] + \cdots + a^{k-k_1} u_2[k_1-1]\\
&U_{22}:=a^{k-k_1-1} u_2[k_1]+ \cdots + a^{k-k_2} u_2[k_2-1]\\
&U_{23} := a^{k-k_2-1} u_2[k_2]+ \cdots + u_2[k-1] \\
&\overline{W} := (w[k-1],w[k-2],\cdots,w[1])
\end{align}

The goal in this proof is grouping control inputs into $U_{ij}$, where each $U_{ij}$ can be thought as either power-limited or information-limited inputs. By expanding $x[n]$, we reveal the effects of the controller inputs on the state, and then isolate (and bound) their effects according to their characteristics.

$\bullet$ Power-Limited Interval: Let's first handle the third power-limited interval using Cauchy-Schwarz inequalities.
Notice that

\begin{align}
&+ u_1[k-1]+a u_1[k-2] + \cdots + a^{k-2}u_1[1] \\
&+ u_2[k-1]+a u_2[k-2] + \cdots + a^{k-2}u_2[1]
\end{align}

Therefore, by Lemma <ref>

\begin{align}
&\geq (\sqrt{\mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2]}-\sqrt{\mathbb{E}[U_{13}^2]}-\sqrt{\mathbb{E}[U_{23}^2]})^2_+ +1
\label{eqn:ageq412}
\end{align}

Here, we can notice that $\mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2]$ is not affected by the controllers' inputs of the third interval.

$\bullet$ First controller's input in Witsenhausen's interval: We will also separate out the effect of the power-limited (first controller's) input in the second interval, $U_{12}$, and introduce large deviation ideas.

\begin{align}
&=\mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2|C=1]\mathbb{P}(C=1)+ \mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2|C=0]\mathbb{P}(C=0)\\
&\geq \mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2|C=1]\mathbb{P}(C=1) \\
&= c  \cdot \mathbb{E}[(W+U_{11}+U_{12}+U_{21}+U_{22})^2|C=1]\\
&\geq c ( \sqrt{\mathbb{E}[(W+U_{11}+U_{21}+U_{22})^2|C=1]} - \sqrt{\mathbb{E}[U_{12}^2|C=1]})_+^2 \label{eqn:ageq422}
\end{align}

Here, we can notice that by the causality of the system, $C$ only affects the inputs from $u_2[k_2-1]$ and $u_1[k_2]$. Thus, $u_2[1:k_2-2]$ and $u_1[1:k_2-1]$ are independent of $C$. We can also notice $\mathbb{E}[(W+U_{11}+U_{21}+U_{22})^2|C=1]$ has only information-limited inputs.

$\bullet$ Information-Limited Interval: Using Lemma <ref>, we will bound the remaining uncertainty of the state after the information-limited interval. Since we will grant all disturbances except $w[0]$ as side-information, we denote the relevant observations as $y_1'[n]$ and $y_2'[n]$. Formally, let $y_1'[n]$, $y_2'[n]$, $W'$, $W''$, $U_{22}'$, $U_{22}''$ be as follows:

\begin{align}
&W' := W - \mathbb{E}[W |y_1'[1:k_1-1],y_2'[1:k_1-1], \overline{W}, C=1 ] \\
&W'' := \mathbb{E}[W |y_1'[1:k_1-1],y_2'[1:k_1-1], \overline{W}, C=1 ]\\
&U_{22}' := U_{22} - \mathbb{E}[U_{22}| y_1'[1:k_1-1],y_2'[1:k_1-1], \overline{W}, C=1]\\
&U_{22}'' := \mathbb{E}[U_{22}| y_1'[1:k_1-1],y_2'[1:k_1-1], \overline{W}, C=1]
\end{align}

Here we can notice $W, y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$ are independent of $C$ and

\begin{align}
W'=a^{k-1}w[0] - \mathbb{E}[a^{k-1}w[0] |y_1'[1:k_1-1],y_2'[1:k_1-1] ].
\end{align}

Since $w[0], y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$ are jointly Gaussian, $W'$ is independent from $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$.
By Lemma <ref> we have

\begin{align}
&=\mathbb{E}[(a^{k-1}w[0] - \mathbb{E}[a^{k-1}w[0] |y_1'[1:k_1-1],y_2'[1:k_1-1] ])^2]\\
&= \frac{a^{2(k-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2} \label{eqn:ageq423}
\end{align}

This lower bounds the uncertainty in the state due to $w[0]$ after the state has been observed through $y_1'[1:k_1-1]$ and $y_2'[1:k_1-1]$.

Note that $y_1[1:k_1-1],y_2[1:k_1-1],\overline{W}$  are functions of $y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}$. Therefore, $U_{11}$ and $U_{21}$ are also functions of $y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}$.
Since $(W',U_{22}')$ are orthogonal to all functions of $(y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W})$, $(W',U_{22}')$ are also orthogonal to $(W'', U_{11}, U_{21}, U_{22}'')$. Moreover, since $\mathbb{E}[W'+U_{22}']=0$ and the conditioning on $C=1$ can be ignored due to causality, we can conclude

\begin{align}
&=\mathbb{E}[(W'+W''+U_{11}+U_{21}+U_{22}'+U_{22}'')^2 | C=1]\\
&=\mathbb{E}[(W' + U_{22}')^2| C=1] + \mathbb{E}[(W''+U_{11}+U_{21}+U_{22}'')^2 | C=1] \\
&\geq \mathbb{E}[(W' + U_{22}')^2| C=1].
\end{align}

In the last term, the effect of the information-limited interval inputs is separated out.

$\bullet$ Second controller's input in Witsenhausen's interval: We will bound the remaining uncertainty of the state   after it has been estimated by the second controller in the second time interval. For this, we will reduce the problem to the state amplification problem of Section <ref>, and apply Lemma <ref>.

$U_{22}'$ is a function of $y_2[1:k_2-1], y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$. Here, $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$  are independent from $W'$ and $y_2[1:k_1-1]$ is a function of $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$. Therefore, only $y_2[k_1:k_2-1]$ are dependent on $W'$. Moreover, $y_1[1:k_1-1]$ —and therefore, $u_1[1:k_1-1]$— is a function of $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$, so they are also independent from $W'$.

Now, we can subtract the independent part from $W'$ from the observation $y_2[k_1,k_2-1]$ without losing information about the state. First, consider $y_2[k_1]$.

\begin{align}
&-(u_1[k_1-1]+au_1[k_1-2]+ \cdots + a^{k_1-2}u_1[1])\\
&-(u_1[k_1-1]+au_1[k_1-2]+ \cdots + a^{k_1-2}u_1[1])\\
&=a^{k_1-1}w[0]-\mathbb{E}[a^{k_1-1}w[0]|y_1'[1:k_1-1], y_2'[1:k_1-1]]+v_2[k_1] \\
&=a^{k_1-k}W' +  v_2[k_1]
\end{align}

Likewise, we can subtract the independent (from $W'$) part from $y_2[k_1+1]$. Furthermore, $u_2[k_1]$ can also be subtracted from $y_2[k_1+1]$ without losing information since the second controller already knows about $u_2[k_1]$. Thus, the information about $W'$ in $y_2[k_1+1]$ is

\begin{align}
&a^{k_1}w[0]-\mathbb{E}[a^{k_1}w[0]|y_1'[1:k_1-1], y_2'[1:k_1-1]]+u_1[k_1] + v_2[k_1+1]\\
&=a^{k_1-k+1}W' + u_1[k_1] + v_2[k_1+1].
\end{align}

In the same way, we can extract the relevant information about $W'$  from the observations $y_2[n]$.
It is worth to mention that conditioned on $C=1$, $v_2[k_2-1]$ is replaced by $v_2'[k_2-1]$, and thus the information about $W'$ in $y_2[k_2-1]$ is

\begin{align}
&a^{k_2-2}w[0]-\mathbb{E}[a^{k_2-2}w[0]|y_1'[1:k_1-1],y_2'[1:k_1-1]]+u_1[k_2-1]+ au_1[k_2-2]+ \cdots +a^{k_2-k_1-1}u_1[k_1]+v_2'[k_2-1]\\
&=a^{k_2-k-1}W' + u_1[k_2-1]+ au_1[k_2-2]+ \cdots +a^{k_2-k_1-1}u_1[k_1]+v_2'[k_2-1].
\end{align}

Moreover, as we mentioned, the conditioning $C=1$ does not affect $u_1[k_1:k_2-1]$ by causality. We have

\begin{align}
\mathbb{E}[(1-2.5^{-1})u_1^2[k_1]+(1-2.5^{-1})2.5^{-1}u_1^2[k_1+1]+\cdots+(1-2.5^{-1})2.5^{-k_2+k_1+1}u_1^2[k_2-1]|C=1] \leq \widetilde{P_1} \leq 2.5 \widetilde{P_1}.
\end{align}

Therefore, we can see that after removing the independent (from $W'$) part from $y_2[k_1:k_2-1]$ the problem reduces to the state amplification problem of Section <ref>. By plugging $x[0]=a^{k_1-1}w[0]$, $\sigma_v=\sigma_{v2}$, $\sigma_{v}'=\sigma_{v2}'$, $k=k_2-k_1$, $w=2.5^{-1}$, $P=2.5 \widetilde{P_1}$ and $\sigma_0^2 =\Sigma$ (which comes from (<ref>)) in Lemma <ref> (iii), we have[Here, we have to use (iii) of Lemma <ref> instead of (i) since in the last observation the SNR (Signal-to-Noise ratio) is too big to apply an arithmetic-geometric inequality together with the previous observations.]

\begin{align}
\mathbb{E}[(W' + U_{22}')^2| C=1] \geq \frac{a^{2(k-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}. \label{eqn:ageq414}
\end{align}

$\bullet$ Power-Limited Inputs: As mentioned before, causality implies $C$ is independent from $y_1[1:k_2-1]$ and thus $U_{12}$. Then, we can upper bound the power of the power-limited inputs.

\begin{align}
&\mathbb{E}[U_{12}^2|C=1]=\mathbb{E}[U_{12}^2] \\
&= \mathbb{E}[(a^{k-k_1-1}u_1[k_1]+\cdots + a^{k-k_2}u_1[k_2-1])^2]\\
&= a^{2(k-k_2)}\mathbb{E}[(a^{k_2-k_1-1}u_1[k_1]+\cdots + u_1[k_2-1])^2]\\
&\leq \frac{a^{2(k-k_1-1)}(1-(2.5a^{-2})^{k_2-k_1})}{1-2.5a^{-2}} (\mathbb{E}[u_1^2[k_1]]+\cdots+2.5^{-(k-k_1-1)}\mathbb{E}[u_1^2[k_2-1]])\\
&\leq \frac{a^{2(k-k_1-1)}(1-(2.5a^{-2})^{k_2-k_1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}}  \label{eqn:ageq421}
\end{align}

where the first inequality comes from Lemma <ref> with parameters $a=a$ and $b=2.5^{-1}$. Likewise, by applying Lemma <ref> with paramters $a=a$ and $b=2.5^{-1}$, we have

\begin{align}
&\leq \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} (\mathbb{E}[u_1^2[k_2]]+ \cdots + 2.5^{-(k-k_2-1)}\mathbb{E}[u_1^2[k-1]])\\
&\leq \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{ 2.5^{k_2-k_1} \widetilde{P_1}}{1-2.5^{-1}} \label{eqn:ageq415}
\end{align}

\begin{align}
&\leq \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} (\mathbb{E}[u_2^2[k_2]]+\cdots+2.5^{-(k-k_2-1)}\mathbb{E}[u_2^2[k-1]])\\
&\leq \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}}. \label{eqn:ageq416}
\end{align}

$\bullet$ Lower bound from $w[0]$: Finally, by plugging (<ref>), (<ref>), (<ref>), (<ref>), (<ref>) into (<ref>)

\begin{align}
\mathbb{E}[x^2[k]]& \geq (\sqrt{c \frac{a^{2(k-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}}
- \sqrt{ c \frac{a^{2(k-k_1-1)}(1-(2.5a^{-2})^{k_2-k_1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}} } \\
&- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{ 2.5^{k_2-k_1} \widetilde{P_1}}{1-2.5^{-1}} }
- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}} })_+^2 +1 \label{eqn:ageq417}
\end{align}

$\bullet$ Lower bound from $w[1]$: As we mentioned in Figure <ref>, <ref> and <ref>, we will repeat the above derivation for $w[1]$ instead of $w[0]$.

Let's denote

\begin{align}
&\widetilde{U}_{11} := a^{k-2}u_1[1]+\cdots+a^{k-k_1-1}u_1[k_1]\\
&\widetilde{U}_{12} := a^{k-k_1-2}u_1[k_1+1]+\cdots+u_1[k-1]\\
&\widetilde{U}_{21} := a^{k-2}u_2[1]+\cdots+a^{k-k_1-1}u_2[k_1]\\
&\widetilde{U}_{22} := a^{k-k_1-2}u_2[k_1+1]+\cdots+a^{k-k_2}u_2[k_2-1] \\
&\widetilde{W} := (w[k-1], w[k-2], \cdots, w[2], w[0])
\end{align}

Compared with the previous case, $\widetilde{U}_{11}$ and $\widetilde{U}_{21}$ include extra input signals $u_1[k_1]$ and $u_2[k_1]$ since $w[1]$ is generated one time-step later than $w[0]$. $\widetilde{U}_{12}$ includes all power-limited inputs of the first controller.

Like before, $\widetilde{U}_{ij}$ groups the controller inputs into either information-limited or power-limited ones. Then, we will isolate the effect of the inputs $\widetilde{U}_{ij}$ to the state $x[n]$ according to their categories.

$\bullet$ Power-Limited Inputs: Like the previous case, we first isolate the power-limited inputs. However, unlike the previous case, we do not need to introduce any large deviation ideas. By Lemma <ref>,

\begin{align}
\mathbb{E}[x^2[k]]&=\mathbb{E}[(W+\widetilde{U}_{11}+\widetilde{U}_{12}+\widetilde{U}_{21}+\widetilde{U}_{22}+U_{23})^2]+1 \\
&\geq (\sqrt{\mathbb{E}[(W+\widetilde{U}_{11}+\widetilde{U}_{21}+\widetilde{U}_{22})^2]} - \sqrt{\mathbb{E}[\widetilde{U}_{12}^2]} - \sqrt{\mathbb{E}[U_{23}^2]})_+^2 + 1  \label{eqn:ageq420}
\end{align}

Now, the resulting $\mathbb{E}[(W+\widetilde{U}_{11}+\widetilde{U}_{21}+\widetilde{U}_{22})^2]$ has only information-limited inputs.

$\bullet$ Information-Limited Interval: Like before, we will bound the remaining uncertainty of the state after the information-limited interval using Lemma <ref>. Denote $\widetilde{y}_1[n]$ and $\widetilde{y}_2[n]$ as follows:

\begin{align}
&\widetilde{y}_1[1] := v_1[1]\\
&\widetilde{y}_2[1] := v_2[1]\\
&\mbox{For }n \geq 2 \\
&\widetilde{y}_1[n] := a^{n-2}w[1]+v_1[n]\\
&\widetilde{y}_2[n] := a^{n-2}w[1]+v_2[n]\\
&W_1' := W - \mathbb{E}[W|\widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1],\widetilde{W}]\\
&W_1'' := \mathbb{E}[W|\widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1],\widetilde{W}]\\
&\widetilde{U}_{22}' = \widetilde{U} - \mathbb{E}[\widetilde{U}_{22}| \widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1],\widetilde{W}]\\
&\widetilde{U}_{22}'' =  \mathbb{E}[\widetilde{U}_{22}| \widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1],\widetilde{W}]
\end{align}

Here we can notice

\begin{align}
W_1'= a^{k-2}w[1] - \mathbb{E}[a^{k-2}w[1]|\widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1]]
\end{align}

Since $w[1], \widetilde{y}_1[1:k_1], \widetilde{y}_2'[1:k_1],\widetilde{W}$ are jointly Gaussian, $W_1'$ is independent from $\widetilde{y}_1[1:k_1], \widetilde{y}_2'[1:k_1],\widetilde{W}$. By Lemma <ref> we have

\begin{align}
&= \mathbb{E}[(a^{k-2}w[1] - \mathbb{E}[a^{k-2}w[1]|\widetilde{y}_1[1:k_1],\widetilde{y}_2[1:k_1]])^2]\\
&= \frac{a^{2(k-2)} \sigma_{v2}^2}
{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2} \label{eqn:ageq424}
\end{align}

This lower bounds the remaining state disturbance due to $w[1]$ after it is observed by $\widetilde{y}_1[1:k_1]$ and $\widetilde{y}_2[1:k_1]$.

Note that $y_1[1:k_1], y_2[1:k_1], \widetilde{W}$ are functions of $\widetilde{y}_1[1:k_1], \widetilde{y}_2[1:k_1], \widetilde{W}$. Therefore, $\widetilde{U}_{11}$ and $\widetilde{U}_{21}$ are also functions of $\widetilde{y}_1[1:k_1], \widetilde{y}_2[1:k_1], \widetilde{W}$. By repeating the previous argument, we can conclude

\begin{align}
&=\mathbb{E}[(W_1'+W_1''+ \widetilde{U}_{11}+\widetilde{U}_{21}+\widetilde{U}_{22}'+\widetilde{U}_{22}'' )^2]\\
&=\mathbb{E}[(W_1'+\widetilde{U}_{22}')^2] + \mathbb{E}[(W_1''+ \widetilde{U}_{11}+\widetilde{U}_{21} + \widetilde{U}_{22}'')^2]\\
&\geq \mathbb{E}[(W_1'+\widetilde{U}_{22}')^2].
\end{align}

In the last term, the effect of the information-limited inputs is separated out.

$\bullet$ Second controller's input in Witsenhausen's interval: Like before, we will reduce the problem to the state amplification problem of Section <ref>, and apply Lemma <ref>. Only the observations $y_2[k_1+1:k_2-1]$ are relevant to $W_1'$. Here, we also have the power constraint on $u_1$

\begin{align}
\mathbb{E}[(1-2.5^{-1})u_1^2[k_1+1]+ \cdots + 2.5^{-k_2+k_1+2}u_1^2[k_2-1] ] \leq 2.5 \widetilde{P_1}
\end{align}

Like before, after removing the independent (from $W_1'$) part from the observations $y_2[k_1+1:k_2-1]$, the problem reduces to the state amplification problem of Section <ref>. By plugging $x[0]=a^{k_1-1}w[1], \sigma_v=\sigma_{v2}, k=k_2-k_1-1, w=2.5^{-1}, P= 2.5 \widetilde{P_1}$ and $\sigma_0^2 = \Sigma$ (which comes from (<ref>)) to Lemma <ref> (i), we have[Unlike the previous part, we apply (i) of Lemma <ref> instead of (iii) since SNR is small enough for all observations.]

\begin{align}
\mathbb{E}[(W_1'+\widetilde{U}_{22}')^2] \geq \frac{a^{2(k-k_1-1)}\Sigma}{2^{2I''(\widetilde{P_1})}}. \label{eqn:ageq410}
\end{align}

$\bullet$ Lower bound from $w[1]$: By applying Lemma <ref> with the parameters $a=a$ and $b=2.5^{-1}$, we can upper bound the power of the power-limited inputs.

\begin{align}
&\mathbb{E}[\widetilde{U}_{12}^2]= \mathbb{E}[(a^{k-k_1-2}u_1[k_1+1]+\cdots+u_1[k-1])^2] \\
&\leq \frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{2.5 \widetilde{P_1}}{1-2.5^{-1}} \label{eqn:ageq419}
\end{align}

Therefore, by plugging (<ref>), (<ref>), (<ref>) into (<ref>) we get

\begin{align}
\mathbb{E}[x^2[k]] &\geq ( \sqrt{\frac{a^{2(k-k_1-1)}\Sigma}{2^{2I''(\widetilde{P_1})}}}
-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{2.5 \widetilde{P_1}}{1-2.5^{-1}}}\\
&-\sqrt{\frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}}} )_+^2 +1 \label{eqn:ageq418}
\end{align}

$\bullet$ Final Lower bound: By (<ref>) and (<ref>), for all $0 \leq \alpha \leq 1$

\begin{align}
&\mathbb{E}[x^2[k]] \\
\alpha (\sqrt{c \frac{a^{2(k-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}}
- \sqrt{ c \frac{a^{2(k-k_1-1)}(1-(2.5a^{-2})^{k_2-k_1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}} } \\
&- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{ 2.5^{k_2-k_1} \widetilde{P_1}}{1-2.5^{-1}} }
- \sqrt{ \frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}} })_+^2\\
&+(1-\alpha) ( \sqrt{\frac{a^{2(k-k_1-1)}\Sigma}{2^{2I''(\widetilde{P_1})}}}
-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{2.5 \widetilde{P_1}}{1-2.5^{-1}}}\\
&-\sqrt{\frac{a^{2(k-k_2-1)}(1-(2.5a^{-2})^{k-k_2})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{1-2.5^{-1}}} )_+^2
\end{align}

In this lemma, the time-interval from $0$ to $k_1-1$ corresponds to the information-limited interval in Figure <ref>. The time-interval from $k_1$ to $k_2-1$ corresponds to the Witsenhausen's interval in Figure <ref>. The time-interval from $k_2$ to $k$ corresponds to the power-limited interval in Figure <ref>.

The general finite-horizon problem structure to justify the infeasibility of $0$-stage signaling strategies. Like the one in Figure <ref>, the problem consists of three time intervals. However, unlike Figure <ref>, we can see Radner's problem between the information-limited and power-limited intervals.

§.§ Lower bound on the optimal cost based on Radner's problem

As we discussed in Section <ref>, Radner's problem cannot be understood using the binary deterministic models and thereby is fundamentally different from Witsenhausen's counterexample. Essentially, it says the communication between controllers requires at least one step delay, and for the observations obtained at the same time step, nonlinear strategies do not improve the performance. Therefore, so-called `$0$-stage signaling' is impossible.

Sine Radner's problem is a sub-block of the infinite-horizon problem <ref>, we also need a lower bound based on Radner's problem to bound the infinite-horizon problem within a constant ratio. Figure <ref> shows the general structure of the lower bound for the case. As we discussed in Figure <ref>, the information-limited interval from time step $0$ to $k_1$ is introduced due to the case $\sigma_{v1}^2 > 0$ and the power-limited interval from time step $k_1+1$ to $k$ is introduced due to the case $P_2 < \infty$.

However, between these two time intervals, we can see the difference. Even though the first controller has better observations and the second has worse observations, if this significant unbalance between two controllers lasts for only one time step, the implicit communication between two controllers is nearly impossible and nonlinear strategies cannot help that much. To capture this effect, we replace the MIMO Witsenhausen's problem with Radner's problem.

Like Lemma <ref>, the following lemma gives a lower bound on the weighted average cost of Problem <ref> when Witsenhausen's interval is replaced by Radner's.

Define a set $S_{L,2}$ as a set of $(k_1,k,\Sigma)$ such that

\begin{align}
&k_1, k \in \mathbb{N}, \Sigma \in \mathbb{R},\\
&k_1 \geq 1, k \geq k_1 + 1, \\
&0 \leq \Sigma \leq
\left\{
\begin{array}{ll}
1& k_1 = 1 \\
\frac{a^{2(k_1-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2}
& k_1 \geq 2
\end{array}\right.
\end{align}

We also define $D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma)$ as follows:

\begin{align}
&D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma) \\
&:= \inf_{c_1, c_2 \in \mathbb{R}}(\sqrt{a^{2(k-k_1-1)}((a-c_1-c_2)^2 \Sigma + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2)}\\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}}}-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}}})_+^2 +1 \\
&\mbox{s.t. } (1-2.5^{-1})c_1^2(\Sigma+\sigma_{v1}^2) \leq \widetilde{P_1} \\
&\quad (1-2.5^{-1})c_2^2(\Sigma+\sigma_{v2}^2) \leq \widetilde{P_2}
\end{align}

Let $|a| \geq 2.5$. Then, for all $q, r_1, r_2 \geq 0$, the minimum cost (<ref>) of Problem <ref> is lower bounded as follows:

\begin{align}
&\inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]\\
& \geq \sup_{(k_1,k,\Sigma) \in S_{L,2}}\min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}.
\end{align}

For $k_1, k \in \mathbb{N}$, define $S_{L,3}$, $S_{L,4}$, $D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1)$ and $D_{L,4}(\widetilde{P_1},\widetilde{P_2},k)$ as follows:

\begin{align}
&S_{L,3} := \{k_1 \in \mathbb{N} \}\\
&S_{L,4} := \{k \in \mathbb{N} : k \geq 2 \}\\
&D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1) := \max(\frac{a^{2(k_1-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2},1) \label{eqn:lem:radner1}\\
&D_{L,4}(\widetilde{P_1},\widetilde{P_2};k) := ( \sqrt{a^{2(k-1)}} - \sqrt{\frac{a^{2(k-2)}}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}}} - \sqrt{\frac{a^{2(k-2)}}{1-2.5a^{-2}} \frac{\widetilde{P_2}   }{1-2.5^{-1}}})_+^2. \label{eqn:lem:radner2}
\end{align}

Then, when $|a| \geq 2.5$, for all $q,r_1, r_2 \geq 0$, the minimum cost (<ref>) of Problem <ref> is also lower bounded as follows:

\begin{align}
&\inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]\\
& \geq \sup_{k_1 \in S_{L,3}}\min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}
\end{align}

\begin{align}
&\inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]\\
& \geq \sup_{k \in S_{L,4}}\min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_{L,4}(\widetilde{P_1},\widetilde{P_2};k) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}.
\end{align}

For simplicity, we assume $a \geq 2.5$, $k_1 \geq 2$, $k > k_1 +1$. The remaining cases when $a \leq -2.5$ or $k_1=1$ or $k = k_1 +1$ easily follow with minor modifications.

$\bullet$ Geometric Slicing: We apply the geometric slicing idea of Section <ref> to get a finite-horizon problem. By putting $\alpha=2.5^{-1}$ and $k_2=k_1$ to Lemma <ref>, the average cost is lower bounded by

\begin{align}
&\inf_{u_1, u_2} (q \mathbb{E}[x^2[k]] \\
&+r_1 \underbrace{( (1-2.5^{-1}) \mathbb{E}[u_1^2[k_1]] + (1-2.5^{-1})2.5^{-1}\mathbb{E}[u_1^2[k_1+1]]+ \cdots+(1-2.5^{-1}) 2.5^{-k+1+k_1} \mathbb{E}[u_1^2[k-1]] )}_{:=\widetilde{P_1}}\\
&+r_2 \underbrace{( (1-2.5^{-1}) \mathbb{E}[u_2^2[k_1]] + (1-2.5^{-1})2.5^{-1}\mathbb{E}[u_2^2[k_1+1]]+ \cdots+(1-2.5^{-1}) 2.5^{-k+1+k_1} \mathbb{E}[u_2^2[k-1]] )}_{:=\widetilde{P_2}}
\end{align}

Like the proof of Lemma <ref>, we denote the second and the third terms as $\widetilde{P_1}$ and $\widetilde{P_2}$ respectively.

$\bullet$ Power-Limited Interval: Denote

\begin{align}
&W_2 := a^{k-k_1-2} w[k_1+1]+\cdots+ a w[k-2]\\
&U_{12} := a^{k-k_1-2}u_1[k_1+1]+\cdots+u_1[k-1] \\
&U_{22} := a^{k-k_1-2}u_2[k_1+1]+\cdots+u_2[k-1] \\
%&W:=a^{k-k_1-2} w[k_1+1]+\cdots+ a w[k-2]
\end{align}

Here, $U_{12}$ and $U_{22}$ correspond to the first and second controller's input in the power-limited intervals described in Figure <ref>. We will first handle these power-limited inputs. Notice that

\begin{align}
\end{align}

Since $x[k_1+1]$ and $W_2$ are independent by causality, using Lemma <ref> we can lower bound $\mathbb{E}[x^2[k]]$ as

\begin{align}
&\geq ( \sqrt{\mathbb{E}[(a^{k-k_1-1}x[k_1+1]+W_2)^2]} - \sqrt{\mathbb{E}[U_{12}^2]} - \sqrt{\mathbb{E}[U_{22}^2]} )_+^2 +1\\
&= ( \sqrt{\mathbb{E}[(a^{k-k_1-1}x[k_1+1])^2] + \mathbb{E}[W_2^2]} - \sqrt{\mathbb{E}[U_{12}^2]} - \sqrt{\mathbb{E}[U_{22}^2]} )_+^2 +1\\
&\geq ( \sqrt{a^{2(k-k_1-1)}\mathbb{E}[x[k_1+1]^2]} - \sqrt{\mathbb{E}[U_1^2]} - \sqrt{\mathbb{E}[U_2^2]} )_+^2 +1. \label{eqn:radner1}
\end{align}

Here,  $\mathbb{E}[x[k_1+1]^2]$ is lower bounded as

\begin{align}
&\mathbb{E}[x[k_1+1]^2] = \mathbb{E}[(ax[k_1]+u_1[k_1]+u_2[k_1]+w[k_1])^2] \\
&=\mathbb{E}[(ax[k_1]+u_1[k_1]+u_2[k_1])^2] + \mathbb{E}[w[k_1]^2] \\
&\geq \mathbb{E}[(ax[k_1]+u_1[k_1]+u_2[k_1])^2]. \label{eqn:radner5}
\end{align}

In the last term, the effect of the power-limited inputs is separated out.

$\bullet$ Information-Limited Interval: Using Lemma <ref>, we will bound the remaining uncertainty of the state after the information-limited interval. Since we will give all the disturbances except $w[0]$ as side-information, we denote the relevant observations as $y_1'[n]$ and $y_2'[n]$. Formally, denote

\begin{align}
&W_1 := a^{k_1-1}w[0] + \cdots + w[k_1-1]\\
&U_{11} := a^{k_1-1}u_1[0]+ \cdots + u_1[k_1-1]\\
&U_{21} := a^{k_1-1}u_2[0]+ \cdots + u_2[k_1-1]\\
&\overline{W} := (w[1],\cdots,w[k-1]) \\
&W_1' := W_1 - \mathbb{E}[W_1|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}] \\
&W_1'' := \mathbb{E}[W_1|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}] \\
&u_1'[k_1] := u_1[k_1] - \mathbb{E}[u_1[k_1]|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}]\\
&u_1''[k_1] := \mathbb{E}[u_1[k_1]|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}]\\
&u_2'[k_1] := u_2[k_1] - \mathbb{E}[u_2[k_1]|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}]\\
&u_2''[k_1] := \mathbb{E}[u_2[k_1]|y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}].
\end{align}

Here, we have

\begin{align}
W_1' = a^{k_1-1}w[0]- \mathbb{E}[a^{k_1-1}w[0]|y_1'[1:k_1-1], y_2'[1:k_1-1]]
\end{align}

Since $w[0], y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$ are jointly Gaussian, $W_1'$ is independent from $ y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$. By Lemma <ref> we have

\begin{align}
\mathbb{E}[W_1'^2] = \frac{a^{2(k_1-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}(1-a^{-2(k_1-1)})}{1-a^{-2}})+\sigma_{v1}^2} \label{eqn:radner6}
\end{align}

This lower bounds the state disturbance due to $w[0]$ when it is observed by $y_1'[1:k_1-1]$ and $y_2'[1:k_1-1]$. Note that $y_1[1:k_1-1], y_2[1:k_1-1], \overline{W}$ is a function of $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$. Therefore, $U_{11}$ and $U_{21}$ are also functions of $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$ and (<ref>) can be lower bounded as

\begin{align}
&=\mathbb{E}[(aW_1' + u_1'[k_1] + u_2'[k_1])^2] + \mathbb{E}[(aW_1'' + aU_{11}+aU_{12} + u_1''[k_1] + u_2''[k_1])^2]\\
&\geq \mathbb{E}[(aW_1' + u_1'[k_1] + u_2'[k_1])^2]
\end{align}

In the last term, the effect of the information-limited inputs is separated out.

$\bullet$ Radner's Interval: Now we will reduce the last term to Radner's problem.
$u_1'[k_1]$ and $u_2'[k_1]$ are functions of $y_1[1:k_1],y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}$ and $y_2[1:k_1],y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}$ respectively. Here, $y_1'[1:k_1-1],y_2'[1:k_1-1],\overline{W}$ are independent from $W_1'$ and $y_1[1:k_1-1], y_2[1:k_1-1], \overline{W}$ is a function of $y_1'[1:k_1-1], y_2'[1:k_1-1], \overline{W}$. Therefore, only $y_1[k_1]$ at the first controller and $y_2[k_1]$ at the second controller are relevant to $W_1'$.
Therefore, by removing independent parts from $W_1'$ in $y_1[k_1]$, the sufficient statistic of $y_1[k_1]$ is

\begin{align}
&y_1[k_1]- (w[k_1-1]+aw[k_1-2]+\cdots+a^{k_1-2}w[1]) - \mathbb{E}[a^{k_1-1}w[0]|y_1'[1:k_1-1], y_2'[1:k_1-1]]\\
&-(u_1[k_1-1]+ a u_1[k_1-2]+ \cdots + a^{k_1-2}u_1[1])\\
&-(u_2[k_1-1]+ a u_2[k_1-2]+ \cdots + a^{k_1-2}u_2[1])\\
&=a^{k_1-1}w[0] - \mathbb{E}[a^{k_1-1}w[0]| y_1'[1:k_1-1], y_2'[1:k_1-1]] + v_1[k_1]\\
&= W_1' + v_1[k_1]
\end{align}

Likewise, $y_2[k_1]$ can be reduced to

\begin{align}
W_1' + v_2[k_1]
\end{align}

Therefore, by considering $W_1'$ as an initial state, $v_1[k_1]$ and $v_2[k_1]$ as observation noise of the first and second controller, we can map the problem with Radner's problem.
Here, we have the following power constraints on $u_1[k_1]$ and $u_2[k_1]$.

\begin{align}
&(1-2.5^{-1})\mathbb{E}[u_1^2[k_1]] \leq \widetilde{P_1}\\
&(1-2.5^{-1})\mathbb{E}[u_2^2[k_1]] \leq \widetilde{P_2}
\end{align}

Since a linear strategy is optimal in Radner's problem, by (<ref>) we can conclude

\begin{align}
\mathbb{E}[(aW_1' + u_1'[k_1] + u_2'[k_1])^2] &\geq
\inf_{c_1, c_2 \in \mathbb{R}} (a-c_1-c_2)^2 \Sigma + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2 \label{eqn:radner2}\\
&\mbox{s.t. } (1-2.5^{-1})c_1^2(\Sigma+\sigma_{v1}^2) \leq \widetilde{P_1} \\
&\quad (1-2.5^{-1})c_2^2(\Sigma+\sigma_{v2}^2) \leq \widetilde{P_2}
\end{align}

$\bullet$ Final Lower bound:
Applying Lemma <ref> with paramters $a=a$ and $b=2.5^{-1}$, we can upper bound the power of the power-limited inputs.

\begin{align}
\mathbb{E}[U_1^2] &= \mathbb{E}[(a^{k-k_1-2}u_1[k_1+1]+\cdots + u_1[k-1])^2] \\
&\leq \frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}} \label{eqn:radner3}
\end{align}

and likewise

\begin{align}
\mathbb{E}[U_1^2]
&\leq \frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}} \label{eqn:radner4}
\end{align}

Finally, plugging (<ref>), (<ref>), (<ref>) into (<ref>) gives the first bound based on $D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma)$:

\begin{align}
\mathbb{E}[x^2[n]] &\geq \inf_{c_1, c_2}(\sqrt{a^{2(k-k_1-1)}((a-c_1-c_2)^2 \Sigma + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2)}\\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}}}-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}}})_+^2 +1 \\
&\mbox{s.t. } (1-2.5^{-1})c_1^2(\Sigma+\sigma_{v1}^2) \leq \widetilde{P_1} \\
&\quad (1-2.5^{-1})c_2^2(\Sigma+\sigma_{v2}^2) \leq \widetilde{P_2}
\end{align}

The second bound based on $D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1)$ derived as follows.
Since $\mathbb{E}[x^2[n]] \geq \mathbb{E}[w^2[n-1]]=1$, trivially $D_L(\widetilde{P_1},\widetilde{P_2}) \geq 1$.
Moreover, as justified above, we have

\begin{align}
\mathbb{E}[x^2[k_1]] \geq \mathbb{E}[(a^{k_1-1}w[0]- \mathbb{E}[a^{k_1-1}w[0]| y_1'[1:k_1-1], y_2'[1:k_1-1])^2] = \mathbb{E}[W_1'^2].
\end{align}

Therefore, by setting $k=k_1$ we get the second bound based on $D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1)$.

The last bound based on $D_{L,4}(\widetilde{P_1},\widetilde{P_2};k)$ of the lemma can be derived as follows.

\begin{align}
&\mathbb{E}[x^2[k]] \\
&\geq (\sqrt{\mathbb{E}[(a^{k-1}w[0]+ \cdots + w[k-1])^2]} - \sqrt{\mathbb{E}[(a^{k-1}u_1[0]+ \cdots + u_1[k-1])^2]} -\sqrt{\mathbb{E}[(a^{k-1}u_2[0]+ \cdots + u_2[k-1])^2]})_+^2 \\
&\geq ( \sqrt{a^{2(k-1)}} - \sqrt{\frac{a^{2(k-2)}}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{1-2.5^{-1}}} - \sqrt{\frac{a^{2(k-2)}}{1-2.5a^{-2}} \frac{\widetilde{P_2}   }{1-2.5^{-1}}})_+^2
\end{align}

where the first inequality follows from Lemma <ref> and the second inequality follows from Lemma <ref>.

In this lemma, the time-interval from $0$ to $k_1-1$ corresponds to the information-limited interval in Figure <ref>. The time-interval from $k_1$ to $k_1+1$ corresponds to the Radner's interval in Figure <ref>. The time-interval from $k_1+1$ to $k$ corresponds to the power-limited interval in Figure <ref>.

§ CONSTANT RATIO OPTIMALITY

Now, we have an upper and lower bound on $D(P_1, P_2)$. In this section, we will evaluate the bounds and prove Theorem <ref> which bounds the weighted average cost within a constant ratio. Even though the numerical evaluations are not elegant[The bounds can probably be improved and tightened. However, the main concern of this paper is not quantifying the exact cost, but qualitatively understanding the near-optimal strategies. The constant ratio optimality results are enough to justify our intuition behind the proposed strategies.], these are enough to justify constant ratio optimality.

The upper bounds are written from the power-disturbance tradeoff perspective of Problem <ref> and denoted by $(D_U(P_1,P_2),P_1,P_2)$. The lower bounds in Lemma <ref> and <ref> are given for the original weighted average-cost of Problem <ref>,  which can be written as $(D_{L,i}(\widetilde{P_1},\widetilde{P_2}),\widetilde{P_1},\widetilde{P_2})$ from the power-disturbance perspective. The following lemma tells if these two tradeoff regions are within a constant ratio of each other as regions in $\mathbb{R}^3$, i.e. $\exists c\geq 1$ such that $(D_U(cP_1,cP_2),cP_1,cP_2) \leq c\cdot ( D_{L,i}(P_1,P_2),P_1,P_2)$, then the average cost can be characterized to within a constant ratio.

For two functions $D_L(\widetilde{P_1}, \widetilde{P_2})$ and $D_U(P_1,P_2)$, let there exist $c \geq 1$ such that for all $x_1,x_2 \geq 0$

\begin{align}
D_U(c x_1, c x_2) \leq c \cdot D_L(x_1, x_2).
\end{align}

Then, for all $q, r_1 , r_2 \geq 0$, the following inequality holds.

\begin{align}
\min_{P_1, P_2 \geq 0} q D_U(P_1,P_2)+r_1 P_1 + r_2 P_2 \leq c(\min_{\widetilde{P_1}, \widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2})
\end{align}

Let $P_1^\star$ and $P_2^\star$ achieve the minimum of the right term of the inequality, i.e.

\begin{align}
&\min_{\widetilde{P_1}, \widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2} \\
&= q D_L(P_1^\star,P_2^\star) + r_1 P_1^\star + r_2 P_2^\star.
\end{align}

Then, we have

\begin{align}
&c (\min_{\widetilde{P_1}, \widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2})\\
&=c\cdot(q D_L(P_1^\star,P_2^\star) + r_1 P_1^\star + r_2 P_2^\star) \\
&\geq q D_U(cP_1^\star,cP_2^\star) + r_1 (cP_1^\star)+ r_2 (cP_2^\star)\\
&\geq \min_{P_1,P_2} q D_U(P_1,P_2) + r_1 P_1 + r_2 P_2
\end{align}

where the first inequality comes from the assumption of the lemma. Thus, the lemma is proved.

We will show that the proposed strategies of Defintion <ref> and <ref> solve the weighted average cost problem of Problem <ref> to within a constant ratio.
Let's call the case when $\sigma_{v2}^2 \leq \max(1,a^2 \sigma_{v1}^2)$ the weakly-degraded-observation case since the gap between the two controllers' observation noises is not too huge and the second controller can observe what the first controller observed only after one-time step. Likewise, we will call the case when $\sigma_{v2}^2 > \max(1,a^2 \sigma_{v1}^2)$ the strongly-degraded-observation case since the gap between the observation noises is larger.

The weakly-degraded-observation case will be discussed in Section <ref> and the strongly-degraded-observation case will be covered in Section <ref>.

§.§ Weakly-Degraded-Observation case with $|a| \geq 2.5$

Let's first consider the weakly-degraded case when $\sigma_{v2}^2 \leq \max(1,a^2 \sigma_{v1}^2)$, which  corresponds to the left half plane of Figure <ref> of page fig:region.
In this case, the infeasibility of $0$-stage signaling discussed in Section  <ref> and <ref> shows up and thus linear strategies are enough for constant-ratio optimality.

First, we evaluate the lower bound of Lemma <ref> which involves Radner's problem.

Let $|a| \geq 2.5$ and $\sigma_{v2}^2 \leq \max(1,a^2 \sigma_{v1}^2)$. Then, for all $q, r_1, r_2 \geq 0$, the minimum cost (<ref>) of Problem <ref> is lower bounded as follows:

\begin{align}
\inf_{u_1,u_2} \limsup_{N \rightarrow \infty}\frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]
\geq \min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}
\end{align}

where $D_L(\widetilde{P_1},\widetilde{P_2})$ satisfies the following conditions.

(a) If $\widetilde{P_1} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)$ and $\widetilde{P_2} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v2}^2)$ then $D_L(\widetilde{P_1},\widetilde{P_2}) = \infty$.

(b) If $\widetilde{P_1} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)$, for all $\widetilde{P_2}$, $D_L(\widetilde{P_1},\widetilde{P_2}) \geq  0.176 a^2 \sigma_{v2}^2+1$.

(c) For all $\widetilde{P_1}$ and $\widetilde{P_2}$, $D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.295  \cdot \max(1,a^2 \sigma_{v1}^2)$.

See Appendix <ref>.

(a) and (b) tell what happens if the first controller has little power (i.e. it must follow something close to a zero-input strategy). (a) shows if the second controller does not have enough power, the system becomes unstable. (b) shows even if the second controller has enough power, the state variance is lower bounded by the second controller's observation noise. (c) shows even if the first controller has enough power to apply a zero-forcing strategy, the state variance is lower bounded by the first controller's observation noise.

The following lemma analyzes the achievable disturbance by the simple linear strategy of Definition <ref>.

Consider a single-controller scalar system

\begin{align}
&x[n+1]=ax[n]+u[n]+w[n]   \\
\end{align}

where $w[n]$ is i.i.d. $\mathcal{N}(0,1)$ and $v[n]$  is i.i.d. $\mathcal{N}(0,\sigma_v^2)$. For a given control strategy, let $D(P):=\limsup_{n \rightarrow \infty}\frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[x^2[n]]$ and $P := \limsup_{n \rightarrow \infty} \frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[u^2[n]]$. Then,

\begin{align}
(D(P),P) \leq (a^2 \sigma_v^2 + 1, a^4 \sigma_v^2 + a^2 \sigma_v^2 + a^2)
\end{align}

is achievable by a linear bang-bang controller, $u[n]=-ay[n]$. Therefore, in Problem <ref> the following power-disturbance tradeoffs are achievable.

\begin{align}
&(D(P_1,P_2),P_1, P_2) \leq (a^2 \sigma_{v1}^2 + 1, a^4 \sigma_{v1}^2 + a^2 \sigma_{v1}^2 + a^2,0), \\
&(D(P_1,P_2),P_1, P_2) \leq (a^2 \sigma_{v2}^2 + 1, 0, a^4 \sigma_{v2}^2 + a^2 \sigma_{v2}^2 + a^2).
\end{align}

Put $u[n]=-ay[n]$ into the system equation. Then, we have

\begin{align}
\end{align}

Thus, we conclude for $n \geq 1$

\begin{align}
\mathbb{E}[x^2[n]]=a^2 \sigma_v^2 +1
\end{align}

\begin{align}
\mathbb{E}[u^2[n]]&= a^2 \mathbb{E}[(x[n]+v[n])^2] \\
&=a^2(a^2 \sigma_v^2 + 1 + \sigma_v^2)
\end{align}

Using Lemma <ref>, Corollary <ref> and Lemma <ref>, we can compare the upper and lower bounds to prove linear strategies suffice to achieve constant-ratio optimality in this region of problem parameters.

There exists $c \geq 1200$ such that for all $a, q, r_1, r_2, \sigma_0,\sigma_{v1}, \sigma_{v2}$ satisfying $|a| \geq 2.5$ and $\sigma_{v2}^2 \leq \max(1,a^2 \sigma_{v1}^2)$, the following inequality holds:

\begin{align}
\frac{\inf_{u_1,u_2 \in L_{lin,bb}} \limsup_{N \rightarrow \infty} \frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[q x^2 [n] + r_1 u_1^2[n] + r_2 u_2^2[n]]}{ \inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[q x^2 [n] + r_1 u_1^2[n] + r_2 u_2^2[n]]}  \leq c.
\end{align}

See Appendix <ref>.

§.§ Strongly-Degraded-Observation case with $|a| \geq 2.5$

Let's consider the strongly-degraded-observation case when $\sigma_{v2}^2 > \max(1,a^2 \sigma_{v1}^2)$, which corresponds to the right half-plane of Figure <ref>. Since $|a| \geq 2.5$, we can find $s \in \mathbb{N}$ such that $a^{2(s-1)}\max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s}\max(1,a^2 \sigma_{v1}^2)$. We will show that the $s$-stage signaling strategy is required for constant-ratio optimality.

Since we need a matching lower bound to $s$-stage signaling strategies, we evaluate Lemma <ref> which has a generalized Witsenhausen's counterexample in it.

Let $|a| \geq 2.5$ and for some $s \in \mathbb{N}$, suppose

\begin{align}
a^{2(s-1)} \max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s} \max(1,a^2 \sigma_{v1}^2).
\end{align}

Then, for all $q, r_1, r_2 \geq 0$, the minimum cost (<ref>) of Problem <ref> is lower bounded as follows:

\begin{align}
\inf_{u_1,u_2} \limsup_{N \rightarrow \infty}\frac{1}{N}
\sum_{0 \leq n < N} q \mathbb{E}[x^2[n]] + r_1 \mathbb{E}[u_1^2[n]] + r_2 \mathbb{E}[u_2^2[n]]
\geq \min_{\widetilde{P_1},\widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}.
\end{align}

where $D_L(\widetilde{P_1},\widetilde{P_2})$ satisfies the following conditions.

(a) When $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$, then
$D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.008 a^2 \sigma_{v2}^2 + 1$.

(b) When $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$ and $\widetilde{P_2} \leq \frac{a^4 \sigma_{v2}^2}{28000}$, then $D_L(\widetilde{P_1},\widetilde{P_2})=\infty$.

(c) When $\frac{\sigma_{v2}^2}{70a^{2(s-1)}} \leq \widetilde{P_1} \leq \frac{1}{20000}\max(a^2,a^4 \sigma_{v1}^2)$,

then $D_L(\widetilde{P_1},\widetilde{P_2}) \geq  0.2541 a^{2s}\widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2})+0.066 a^{2s}\max(1,a^2\sigma_{v1}^2) + 1$.

(d) When $\frac{\sigma_{v2}^2}{70a^{2(s-1)}} \leq \widetilde{P_1} \leq \frac{1}{20000}\max(a^2,a^4 \sigma_{v1}^2)$ and
$\widetilde{P_2} \leq 0.0457a^{2(s+1)}\widetilde{P_1} \exp(-\frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 0.0113 a^{2(s+1)} \max(1,a^2\sigma_{v1}^2) $,
then $D_L(\widetilde{P_1},\widetilde{P_2})=\infty$.

(e) For all $\widetilde{P_1}$ and $\widetilde{P_2}$, $D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.295 \cdot \max(1,a^2 \sigma_{v1}^2)$.

See Appendix <ref>.

(a) and (b) tell what happens if the first controller has little power and thus is forced to be close to a zero-input strategy. Even if the second controller has enough power, the state variance is lower bounded by the second controller's observation noise. If the second controller does not have enough power to stabilize the system, the state diverges to infinity. (e) shows the opposite case when the first controller has enough power to apply zero-forcing strategy. However, even in this case, the state variance is lower bounded by the first controller's observation noise. (c) and (d) cover the case between these two extreme cases. (c) gives the lower bound that matches to the $s$-stage signaling strategy when the second controller has enough power. (d) shows that since the first controller does not stabilize the system with its signaling alone, the second controller's input power has to be large enough to stabilize the system.

Now, we evaluate the performance of the $s$-stage signaling analyzed in Lemma <ref> of page ach:lemma9.

Consider Problem <ref> of page prob:power, and let $|a| \geq 2.5$ and suppose  $a^{2(s-1)} \max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s}\max(1,a^2 \sigma_{v1}^2)$ for some $s \in \mathbb{N}$. Then, there exists an upper bound $D_U(P_1,P_2)$ on $D(P_1,P_2)$ i.e. $D(P_1,P_2) \leq D_U(P_1,P_2)$ for all $P_1, P_2 \geq 0$ satisfying the following:

\begin{align}
(D_U(P_1,P_2),P_1,P_2) \leq &( 832 a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2})+63a^{2s} \max(1,a^2 \sigma_{v1}^2), \\
& 80000P, 6656 a^{2(s+1)}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2})+564 a^{2(s+1)} \max(1,a^2 \sigma_{v1}^2))
\end{align}

for $\frac{\sigma_{v2}^2}{70a^{2(s-1)}} \leq P \leq \frac{1}{20000}\max(a^2, a^4 \sigma_{v1}^2)$.

See Appendix <ref>

Here we can notice that the performance is matching that of Corollary <ref> (c), (d) in that the bounds on the state disturbance take the same form of a function on $P_1$ and system parameters.

Now, we can compare these two bounds to prove constant-ratio optimality.

There exists $c \leq 1.5 \times 10^5$ such that for all $a, q, r_1, r_2, \sigma_0,\sigma_{v1}, \sigma_{v2}$ satisfying $|a| \geq 2.5$ and

\begin{align}
a^{2(s-1)} \max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s} \max(1,a^2 \sigma_{v1}^2).
\end{align}

for some $s \in \mathbb{N}$, the following inequality holds:

\begin{align}
\frac{\inf_{u_1,u_2 \in L_{lin,bb} \cup L_{sig,s}} \limsup_{N \rightarrow \infty} \frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[q x^2 [n] + r_1 u_1^2[n] + r_2 u_2^2[n]]}{ \inf_{u_1,u_2} \limsup_{N \rightarrow \infty} \frac{1}{N}\sum_{0 \leq n < N} \mathbb{E}[q x^2 [n] + r_1 u_1^2[n] + r_2 u_2^2[n]]}  \leq c.
\end{align}

See Appendix <ref>

Now, Theorem <ref> immediately follows from Propositions <ref> and <ref>.

Propostion <ref> covers the case when $\sigma_{v2}^2 \leq \max(1,a^2\sigma_{v1}^2)$.
Propostion <ref> covers the case when $\sigma_{v2}^2 > \max(1,a^2\sigma_{v1}^2)$, since in this case there exists $s \in \mathbb{N}$ such that $a^{2(s-1)} \max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s} \max(1,a^2 \sigma_{v1}^2)$.

§ CONNECTION TO WIRELESS COMMUNICATION THEORY

By transmitting different signals across the antennas, we can achieve `d.o.f. gain'. Generally, this scheme performs well in high-SNR.

By transmitting the same signal across the antennas, we can achieve `power gain'. Generally, this scheme performs well in low-SNR.

MIMO Wireless Communication Problem

Throughout the discussion, we have observed a lot of similarity between wireless communication and the decentralized LQG control problems considered in this paper. In this section, we will explore this point in more detail. At first glance, decentralized LQG control and wireless communication seem pretty distinct from each other. But the main result in this paper is actually a manifestation of a deeper connection.

The essence of wireless communication problems <cit.> can be summarized as follows: First, unlike wired communication, wireless communication systems share a common channel and as a result the signals from different transmitting antennas can interact with each other. Second, wireless communication systems involve uncertainties or randomness that come from channel fading or thermal noise in circuits. Third, to extend battery life and minimize interference to other transceivers, each transmitting antenna has a power constraint.

The way that wireless communication theory models capture this nature is very similar to stochastic control theory. First, the interaction between the signals is modeled by linear operations. Second, the uncertainty in the system is modeled by Gaussian random variables. Third, the power of the transmitting antennas is measured by a quadratic cost. If we remember that wireless communication systems are by nature distributed, wireless communication problems are essentially a special case of decentralized LQG control problems, except that wireless communication problems have the special objective of communication.

Like decentralized LQG problems, wireless network communication problems are still open <cit.> or nonconvex <cit.>. However, wireless communication theorists found that it is helpful to divide cases  according to the SNR(Signal-to-Noise Ratio).  For a given communication scheme, the capacity of a channel is usually given as $\log(1+c_1 SNR+ \cdots + c_k SNR^{k})$. Therefore, when SNR is large (high-SNR case), the capacity is approximately $k \log SNR$ (where $k$ turns out to be the `d.o.f. gain' of the scheme). When SNR is small (low-SNR case), the capacity is approximately $c_1 SNR$ (where $c_1$ turns out to be the `power gain' of the scheme). Therefore, depending on the SNR the capacity of communication schemes are very different. Thus, wireless communication theory usually divides into two cases: (1) high-SNR (2) low-SNR.

Let's consider a $2 \times 2$ MIMO communication problem of Figure <ref>. We can think of two basic ways of exploiting these two antennas. The first way is transmitting different signals across different antennas. As we can see in Fig. <ref>, in this case the receiver will have two variables and two (noisy) equations, and we can expect `MIMO gain' by solving for multiple variables. In wireless communication theory, this gain is called the `d.o.f.(degree-of-freedom) gain' and the scheme of Figure <ref> succeeds in increasing $k$ in the capacity formula.

As we mentioned in Section <ref>, this concept can be extended to generalized d.o.f. by allowing the transmitting powers of different antennas to scale differently <cit.>. When the transmitting powers of different antennas scale differently, we can further divide a single receiving antenna according to “signal levels". For the small signal level, all tranmitting antennas can affect it, but for the large signal level, only the few transmitting antennas with large power can affect it. In <cit.>, binary deterministic models were proposed to capture this phenomenon by conceptualizing different bit-levels like different antennas, which we used in Section <ref>.

The second way of using two antennas is transmitting the same signal across different antennas as shown in Fig. <ref>. In this scheme, the receiver will have only one variable and we cannot expect the d.o.f. gain of solving for multiple variables. However, there is a gain to be had from aligning the signals. Let's assume all random variables, $A, B, n_1, n_2$, are Gaussian random variables with zero mean and unit variance, and compute the signal-to-noise ratio at the receiving antennas. The SNR of the first receive antenna in Fig. <ref> is $\frac{\mathbb{E}[(A+B)^2]}{\mathbb{E}[n_1^2]}=2$. On the other hand, the SNR of the first antenna in Fig. <ref> is $\frac{\mathbb{E}[(2A)^2]}{\mathbb{E}[n_1^2]}=4$. Therefore, by transmitting the same signal over different antennas we can increase SNR of the received signals. This gain is known as `power gain' in wireless communication theory and the proposed scheme is good for increasing $c_1$ in the capacity formula. To exploit the power gain, the receiver has to introduce maximum-ratio combining <cit.>.

As indicated by the blue circles, in the fast dynamics case the proposed scheme exploits  “information flow" from both controllers but ignores all past observations. By contrast, as indicated by the red circle, in the slow dynamics case the proposed scheme exploits the information of only one controller but takes into account all past observations.

How is this relevant for scalar decentralized LQG control problems? To control a plant we first have to gain information about its state. The quantitative behavior of this information flow (from a plant to controllers and finally back to the plant <cit.>) is very similar to that in wireless communication systems. More precisely, according to the eigenvalue of the system, the information flow in the system shows a very different behavior. The system is deemed to be fast-dynamics when the eigenvalue is large ($|a| \geq 2.5$) and slow-dynamics when the eigenvalue is small ($|a| < 2.5$).

The main reason for this division is the relationship between the eigenvalue of the system and the SNR of the information flow for control. The discussion of Section <ref> reveals that the SNR of implicit communication between two controllers will be bounded[Since the second controller can cancel all bits above its noise level at the next time step, the new information of the state cannot be amplified more than $|a|^2$ above the second controller's noise level. Thus, the SNR measured at the second controller is always bounded by $|a|^2$.] by the eigenvalue squared ($|a|^2$).
Therefore, when the eigenvalue is large, the SNR for implicit communication is also large. Therefore, from wireless communication theory we can expect that the (generalized) d.o.f. gain of the implicit communication is crucial. Likewise, when the eigenvalue is small, the SNR for implicit communication is also small and the power gain of the implicit communication is crucial. This is the slow dynamics case. To harness the power gain, we have to use Kalman filtering which corresponds to maximum-ratio combining in wireless communication <cit.>.

In short, even if the system is the simplest scalar system, we can think of two ways of sending information. One way is across different bit-levels and the other way is across different time-slots. Moreover, these multiple bit-levels and multiple time-slots can be deemed as MIMO antennas in wireless communication theory. In fast-dynamics, the MIMO antenna gain of multiple bit-levels dominates that of multiple time-slots. The proposed signaling strategies exploit the d.o.f. gain of the MIMO antennas over multiple bit-levels.

On the other hand, in slow-dynamics, the MIMO antenna gain of multiple time-slots is much more crucial. In <cit.>, Kalman filtering is used to exploit the power gain of the MIMO antennas over multiple time-slots.

Figure <ref> visualizes the discussion so far. In fast-dynamics, the state is quickly changing and the SNR of implicit communication is high. Thus, the information from previous time steps is much less important than that of the current time step. However, to fully exploit the MIMO antenna gain of different bit-levels, the observations from both controllers has to be used.[Even though the strategy in Definition <ref> relies on the past controller inputs (therefore, the past observations), the role of the past inputs in the strategy is just to cancel their influence on the current time step, not providing information about the state.] On the other hand, in slow-dynamics, the state changes slowly and the SNR of implicit communication is low. Therefore, there is no huge incentive for implicit communication between controllers, and a strategy which fully exploits the observations of either one controller is enough to achieve constant-ratio optimality. However, the power gain from the past observations cannot be ignored and so Kalman filtering has to be used <cit.>.

It is worth mentioning that this fundamental difference between fast and slow dynamics was conjectured as early as the 1970s <cit.> but it remains vague: “The
development of systematic procedures for appropriately
modeling large scale systems with slow and fast dynamics
has not received the attention it deserves. $\cdots$ one should look for
time scale separation (fast and slow dynamics)." This paper is the first that has used this quantitatively.

The division of fast and slow dynamics base on $2.5$ is somewhat surprising if we remind that Witsenhausen's counterexample corresponds to $a=1$ case in the infinite horizon problem.
In <cit.> it was shown that we need nonlinear strategy to achieve a constant ratio optimality in Witsenhasuen's counterexample, while in <cit.> it is shown that in the slow dynamics case including $a=1$ linear strategies are enough for a constant ratio optimality. The main reason for this is that the infinite horizon problem is a sequential problem. Since the problem is sequential, we can think the infinite-horizon problem as an interlocking of a series of Witsenhausen's counterexamples. When $a=1$, the interference from the previous Witsenhausen's problem is too strong and we do not have to solve the current Witsenhausen's problem optimally.

§ DISCUSSION AND FURTHER RESEARCH

Communication-Estimation-Control Separation Controllers

Communication-Estimation-Control separation controller interpretation of $L_{sig,s}$ (Here,
$\bar{x}[n]=Q_{a^s d}(y_2[n]-R_{a^s d}(\sum_{1 \leq i \leq s} a^{i-1}u_2[n-i]))+R_{a^s d}(\sum_{1 \leq i \leq s} a^{i-1}u_2[n-i])$)

In the beginning of the paper, we summarized the two main contributions of the classical centralized LQG result. The first was linear controller optimality which narrows the search for the optimal strategy from the infinite-dimensional strategy space to the finite-dimensional linear strategy space. In Theorem <ref>, we gave the corresponding result for scalar decentralized LQG problems in an approximation sense by proposing a finite-dimensional strategy space.

The second contribution was more philosophical. Centralized LQG gave us the
separation principle for estimation and control. Therefore, a natural question is whether we can interpret the result of Theorem <ref> in terms of estimation-control separation, or if there is a conceptual missing block. The authors believe there is a missing fundamental design block, the “communication" block.

Figure <ref> shows the proposed
communication-estimation-control separation controller, which we
believe, is approximately optimal. First, the controller
observes $y[n]$. Unlike the centralized case, $y[n]$ may contain
transmitted “signals" from the other controllers. The decoder block
extracts such information and generates a new observation
$y_d[n]$. Based on both $y[n]$ and $y_d[n]$, the estimator block tries
to estimate the states. After the estimation, the controller can
either control the states[Even a single scalar state can be viewed
as a collection of bits-positions.] by itself, or relay information
to the other controllers and let them control. $\hat{x}_a[n]$ is the
states that the controller wants to control by itself. Based on
$\hat{x}_a[n]$, the actuator generates the control action
$u_a[n]$. $\hat{x}_e[n]$ is the state that the controller wants to
encode for the other controllers. Based on $\hat{x}_e[n]$, the encoder generates the encoded signal $u_e[n]$. Finally, the control output is the superposition of $u_a[n]$ and $u_e[n]$.

Figure <ref> interprets the strategy $L_{sig,s}$ based on the proposed controller structure. The strategy exploits the fact that the controller $1$ has a better observation than the controller $2$. Since the controller $1$'s control signal is expensive, it “relays" its observation through the encoder rather than trying to control the state by itself. Then, the controller $2$ extracts the relayed information in the decoder block, and takes action based on it. We can notice that only encoders and decoders are nonlinear, while estimators and actuators are linear. Therefore, this structure fits the intuition that the essential nonlinearity comes from communication.

An extensive relationship between the implicit information flow for control and wireless information flow was discussed in Section <ref>. Some unique features of information flows for control was also noticed. We also found the counterpart of the classical notion of information theoretic cutset bounds <cit.> in dynamic programming context. The geometric slicing idea discussed in Figure <ref> can be thought as a cutset bound in a sense that it finds the informational bottleneck of the system. However, unlike traditional information theoretic cutsets, the geometric slicing idea divides the nodes by a weighted cut rather than a simple partitioning.

Even if this paper focused on the simplest toy scalar LQG problem with two controllers, the essential difficulty of decentralized problems — nonconvex optimization over infinite-dimensional space — was still there and we could finesse this difficulty by taking an approximation approach.
We believe the approaches and techniques developed in this paper will also be useful in more
general problems with vector states and multiple controllers.
Moreover, in the process of such generalization, we will find more close relationship and parallelism between wireless information flows and control information flows. For example, the notion of the computation over communication channels <cit.> or interference alignment <cit.> has to be properly understood in control contexts. Above all, by solving the problems only approximately, we “may” be able to make a breakthrough in this long-standing open problem, the decentralized LQG problem.

§ ACKNOWLEDGEMENTS

The first author thanks Samsung Scholarship for the generous support during his graduate study. The authors would like to thank the CDC reviewers for their comments and NSF for grants NSF-07291222, NSF-0917212, and NSF-0932410.

§.§ Proof of Corollary <ref> of Page rat:lemma2

Proof of (c):

Let's first consider when $\max(1,a^2 \sigma_{v1}^2)=a^2 \sigma_{v1}^2$. Since $a^2 \sigma_{v1}^2 \geq 1$, there exists $k_1 \geq 2$ such that

\begin{align}
a^{2(k_1-2)} \leq a^2 \sigma_{v1}^2 < a^{2(k_1-1)},
\end{align}

and we choose such a $k_1$ as $k_1$ in Lemma <ref>. Then, by (<ref>) of Lemma <ref> we have

\begin{align}
&D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1) \\
&\geq \frac{a^{2(k_1-1)}\sigma_{v1}^2}{(1+\frac{\sigma_{v1}^2}{\sigma_{v2}^2})(\frac{a^{2(k_1-2)}}{1-a^{-2}})+\sigma_{v1}^2}\\
&\overset{(A)}{\geq} \frac{a^{2(k_1-1)}\sigma_{v1}^2}{\frac{2}{1-2.5^{-2}}a^{2(k_1-2)}+\sigma_{v1}^2}\\
&= \frac{a^2 \sigma_{v1}^2}{\frac{2}{1-2.5^{-2}}+\frac{\sigma_{v1}^2}{a^{2(k_1-2)}}}\\
&\overset{(B)}{\geq} \frac{a^2 \sigma_{v1}^2}{\frac{2}{1-2.5^{-2}}+1} \\
&\geq 0.295775... a^2 \sigma_{v1}^2 \\
&\geq 0.295 a^2 \sigma_{v1}^2. \label{eqn:ratio1}
\end{align}

(A): $\sigma_{v1}^2 \leq \sigma_{v2}^2$ and $|a| \geq 2.5$.

(B): $a^2 \sigma_{v1}^2 < a^{2(k_1-1)}$.

When $\max(1,a^2 \sigma_{v1}^2)=1$, by (<ref>) of Lemma <ref> we have $D_{L,3}(\widetilde{P_1},\widetilde{P_2};k_1) \geq 1 \geq 0.295$.

Proof of (b):

In Lemma <ref>, choose $k_1$ in the same way as (c) and let $k=k_1 + 1$. Inspired by the proof of (c), we can safely choose $\Sigma = 0.295 \max(1,a^2 \sigma_{v1}^2)$. Then, by Lemma <ref>, we notice that since $k-k_1-1=0$, the second and third square-root terms in $D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma)$ goes away and the bound reduces to

\begin{align}
D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma) &\geq \inf_{c_1, c_2} ( \sqrt{(a-c_1 -c_2)^2 \Sigma + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2})_+^2  + 1\\
&\mbox{s.t. }  (1-2.5^{-1}) c_1^2 (\Sigma+ \sigma_{v1}^2) \leq \widetilde{P_1}
\end{align}

where $c_2$ can be chosen arbitrarily.

Here, since we assumed $\widetilde{P_1} \leq \frac{1}{400} a^2 \max(1,a^2 \sigma_{v1})$, we have

\begin{align}
&(1-2.5^{-1})c_1^2 (\Sigma + \sigma_{v1}^2) \leq \widetilde{P_1} \leq \frac{1}{400}a^2 \max(1, a^2\sigma_{v1}^2)\\
&(\Rightarrow) c_1^2(0.295 \max(1,a^2 \sigma_{v1}^2) + \sigma_{v1}^2) \leq  \frac{1}{400(1-2.5^{-1})} a^2 \max(1, a^2\sigma_{v1}^2) \\
&(\Rightarrow) c_1^2 \leq \frac{a^2 \max(1,a^2 \sigma_{v1}^2)}{400(1-2.5^{-1})(0.295 \max(1,a^2\sigma_{v1}^2) + \sigma_{v1}^2)} \leq \frac{a^2}{400 (1-2.5^{-1}) \cdot 0.295} \\
&(\Rightarrow) |c_1| \leq  0.118846...|a| \leq 0.119 |a|.
\end{align}

\begin{align}
D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma)& \geq \inf_{c_1, c_2} ( \sqrt{(a-c_1 -c_2)^2 0.295 \max(1,a^2 \sigma_{v1}^2) + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2})_+^2  + 1\\
&\mbox{s.t. }  |c_1| \leq 0.119 |a| \\
&\geq \inf_{c_2} (a-0.119a -c_2)^2 0.295 \max(1,a^2 \sigma_{v1}^2) + c_2^2 \sigma_{v2}^2 + 1 \\
&\overset{(A)}{\geq} \inf_{c_2} (a-0.119a -c_2)^2 0.295  \sigma_{v2}^2 + c_2^2 \sigma_{v2}^2 + 1 \\
&= \inf_{\widetilde{c_2}} ( \sqrt{ (1-0.119-\widetilde{c_2})^2  0.295 + \widetilde{c_2}^2})^2 a^2 \sigma_{v2}^2 +1\\
&\overset{(B)}{=} 0.176808... a^2 \sigma_{v2}^2 + 1 \\
&\geq 0.176 a^2 \sigma_{v2}^2 +1.
\end{align}

(A): By the assumption $\max(1,a^2 \sigma_{v1}^2) \geq \sigma_{v2}^2$.

(B): By the numerical optimization of the quadratic function.

Proof of (a):

(i) When $\max(1,a^2\sigma_{v2}^2)=a^2 \sigma_{v2}^2$

In Lemma <ref>, we will choose $k_1$ in the same way as (c) and $k$ arbitrarily large. As above, we can safely choose $\Sigma = 0.295 a^2 \sigma_{v1}^2$. Applying the same arguments as (b), (c) to Lemma <ref> gives

\begin{align}
D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma) &\geq \inf_{c_1, c_2}(\sqrt{a^{2(k-k_1-1)}((a-c_1-c_2)^2 \Sigma + c_1^2 \sigma_{v1}^2 + c_2^2 \sigma_{v2}^2)}\\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}}} \\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}}  \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}}})_+^2 +1 \\
&\mbox{s.t. } (1-2.5^{-1})c_1^2(\Sigma+\sigma_{v1}^2) \leq \widetilde{P_1} \\
&\quad (1-2.5^{-1})c_2^2(\Sigma+\sigma_{v2}^2) \leq \widetilde{P_2} \\
(\sqrt{a^{2(k-k_1-1)} 0.176 a^2 \sigma_{v2}^2 }\\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}}} \\
&-\sqrt{\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}}  \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}}})_+^2 +1.
\label{eqn:cor2:1}
\end{align}

Moreover, we have

\begin{align}
&\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}}\\
&\overset{(A)}{\leq} \frac{a^{2(k-k_1-2)}}{1-2.5^{-1}} \frac{\widetilde{P_1}}{(1-2.5^{-1})2.5^{-1}} \\
&\overset{(B)}{\leq} \frac{a^{2(k-k_1-2)}}{(1-2.5^{-1})^2 2.5^{-1}} \frac{1}{400} a^2 \max(1,a^2 \sigma_{v1}^2) \\
&\leq 0.01736111... a^{2(k-k_1)} \sigma_{v2}^2 \\
&\leq 0.0174 a^{2(k-k_1)} \sigma_{v2}^2. \label{eqn:cor2:2}
\end{align}

(A): $|a| \geq 2.5$.

(B): We assumed $\widetilde{P_1} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)=\frac{1}{400} a^4 \sigma_{v1}^2 \leq a^2 \sigma_{v2}^2$.

Likewise, we also have

\begin{align}
&\frac{a^{2(k-k_1-2)}(1-(2.5a^{-2})^{k-k_1-1})}{1-2.5a^{-2}} \frac{\widetilde{P_2}}{(1-2.5^{-1})2.5^{-1}}\\
&\leq 0.0174 a^{2(k-k_1)} \sigma_{v2}^2. \label{eqn:cor2:3}
\end{align}

Therefore, by plugging (<ref>) and (<ref>) into (<ref>), we get

\begin{align}
D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma) &\geq (\sqrt{0.176}-\sqrt{0.0174}-\sqrt{0.0174})_+^2 a^{2(k-k_1)} \sigma_{v2}^2 +1\\
&\geq 0.02 a^{2(k-k_1)} \sigma_{v2}^2 + 1.
\end{align}

Since $k$ can be chosen arbitrarily large and $|a| > 1$, $\lim_{k \rightarrow \infty} D_{L,2}(\widetilde{P_1},\widetilde{P_2};k_1,k,\Sigma)=\infty$.

(ii) When $\max(1,a^2\sigma_{v2}^2)=1$

We will choose $k$ arbitrarily large in (<ref>) of Lemma <ref>.
Here the assumptions $\widetilde{P_1} \leq \frac{1}{400} a^2 \max(1,a^2 \sigma_{v1}^2)$ and $\widetilde{P_2} \leq \frac{1}{400} a^2 \max(1,a^2 \sigma_{v2}^2)$ reduce to $\widetilde{P_1} \leq \frac{a^2}{400}$ and $\widetilde{P_2} \leq \frac{a^2}{400}$.

Therefore, by (<ref>) of Lemma <ref> and $|a| \geq 2.5$, for all $k$ we have

\begin{align}
D_{L,4}(\widetilde{P_1},\widetilde{P_2};k) &\geq (\sqrt{a^{2(k-1)}} - \sqrt{ \frac{a^{2(k-2)}}{(1-2.5^{-1})^2} \frac{a^2}{400}} - \sqrt{\frac{a^{2(k-2)}}{(1-2.5^{-1})^2} \frac{a^2}{400}} )_+^2\\
& =(1 - \sqrt{\frac{1}{400(1-2.5^{-1})^2}} - \sqrt{\frac{1}{400(1-2.5^{-1})^2}})_+^2 a^{2(k-1)}\\
& \geq 0.6 a^{2(k-1)}
\end{align}

Since $k$ can be chosen arbitrarily large, $\lim_{k \rightarrow \infty} D_{L,4}(\widetilde{P_1},\widetilde{P_2};k)=\infty$.

§.§ Proof of Proposition <ref>

By Lemma <ref>, if there exists $c \geq 1$ such that for all $\widetilde{P_1}, \widetilde{P_2} \geq 0$, $D_U(c \widetilde{P_1}, c\widetilde{P_2}) \leq c \cdot D_L(\widetilde{P_1},\widetilde{P_2})$, then for all $q, r_1, r_2 \geq 0$ we have

\begin{align}
\frac{\min_{P_1, P_2 \geq 0} q D_U(P_1,P_2)+r_1 P_1 + r_2 P_2}{\min_{\widetilde{P_1}, \widetilde{P_2} \geq 0} q D_L(\widetilde{P_1},\widetilde{P_2}) + r_1 \widetilde{P_1} + r_2 \widetilde{P_2}} \leq c
\end{align}

which finishes the proof. Therefore, we will only prove that such $c$ exists.

(i) When $\widetilde{P_1} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)$ and $\widetilde{P_2} \leq \frac{1}{400}a^2\max(1,a^2 \sigma_{v2}^2)$

Lower bound: By Corollary <ref> (a),

\begin{align}
D_L( \widetilde{P_1},\widetilde{P_2}) = \infty
\end{align}

Therefore, we do not need the corresponding upper bound.

(ii) When $\widetilde{P_1} \leq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)$ and $\widetilde{P_2} \geq \frac{1}{400}a^2 \max(1, a^2 \sigma_{v2}^2)$

Lower bound: By Corollary <ref> (b),

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.176 a^2 \sigma_{v2}^2+1.
\end{align}

Upper bound: By Lemma <ref>,

\begin{align}
(D_U(P_1,P_2),P_1,P_2) &\leq (a^2 \sigma_{v2}^2 +1,0, a^4\sigma_{v2}^2+ a^2 \sigma_{v2}^2 + a^2)\\
&\leq (a^2 \sigma_{v2}^2+1, 0, 3 a^2 \max(1,a^2 \sigma_{v2}^2)).
%&\leq (a^2 \sigma_{v2}^2 +1,0, a^4\sigma_{v2}^2+ a^2 \sigma_{v2}^2 + a^2 \sigma_{v2}^2)\\
%&\leq (a^2 \sigma_{v2}^2 +1,0, (1+\frac{2}{2.5^2})a^4\sigma_{v2}^2)\\
%&\leq (a^2 \sigma_{v2}^2 +1,0, 1.32 a^4\sigma_{v2}^2)
\end{align}

Ratio: Thus, $c$ is upper bounded by

\begin{align}
c \leq \max( \frac{1}{0.176}, \frac{3}{\frac{1}{400}})=1200.
\end{align}

(iii) When $\widetilde{P_1} \geq \frac{1}{400}a^2 \max(1,a^2 \sigma_{v1}^2)$

Lower bound: By Corollary <ref> (c),

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.295 \max(1,a^2 \sigma_{v1}^2)
\end{align}

Upper bound: By Lemma <ref>,

\begin{align}
(D_U(P_1,P_2),P_1,P_2) &\leq (a^2 \sigma_{v1}^2 +1, a^4\sigma_{v1}^2+ a^2 \sigma_{v1}^2 + a^2, 0) \\
&\leq (2 \max(1, a^2 \sigma_{v1}^2), 3a^2 \max(1,a^2 \sigma_{v1}^2) , 0)
\end{align}

Ratio: $c$ is upper bounded by

\begin{align}
c \leq \max( \frac{2}{0.295}, \frac{3}{\frac{1}{400}})=1200.
\end{align}

Therefore, by (i), (ii), (iii), the lemma is true and $c \leq 1200$.

§.§ Proof of Corollary <ref>

For simplicity, we will only prove for the case when $\max(1,a^2 \sigma_{v1}^2)=a^2 \sigma_{v1}^2$. To prove the case when $\max(1,a^2 \sigma_{v1}^2)=1$, we can simply repeat the following proofs with parameters $k_1=1$ and $\Sigma=0.295$. We will also abbreviate $D_{L,1}(\widetilde{P_1},\widetilde{P_2};k_1,k_2,k,\sigma_{v2}',\alpha,\Sigma)$ to $D_{L,1}(\widetilde{P_1},\widetilde{P_2})$.

Proof of (a):

Since $a^2 \sigma_{v1}^2 \geq 1$, there exists $k_1 \geq 2$ such that

\begin{align}
a^{2(k_1-2)} \leq a^2 \sigma_{v1}^2 < a^{2(k_1-1)},
\end{align}

and we will use such a $k_1$ in Lemma <ref>.

Since the selection of $k_1$ is the same as in the proof of Corollary <ref> (c), by (<ref>) we can select $\Sigma = 0.295 a^2 \sigma_{v1}^2$ in Lemma <ref>.

Let's further choose $k_2=k=k_1+s+1$, $\alpha=1$ and $\sigma_{v2}=\sigma_{v2}'$ in Lemma <ref>. Then, since (<ref>), (<ref>), (<ref>) disappear, $D_{L,1}$ in Lemma <ref> reduces to

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) \geq ( \sqrt{ \frac{a^{2(k_2-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}} } - \sqrt{ \frac{a^{2(k_2-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2} } )_+^2 +1. \label{eqn:lemma3:1}
\end{align}

We can bound $I''(\widetilde{P_1})$ as

\begin{align}
&I''(\widetilde{P_1}) \overset{(A)}{\leq}
\frac{1}{2} \log(1+ \frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(
\frac{2a^{2(k_2-2-k_1)}}{1-2.5^{-2}} 0.295a^2 \sigma_{v1}^2
\frac{2a^{2(k_2-3-k_1)}}{1-2.5^{-2}} \frac{2.5\frac{1}{70}\frac{\sigma_{v2}^2}{a^{2(s-1)}}}{(1-2.5^{-1})^2}
))^{k_2-k_1-1}  \\
&=\frac{1}{2} \log(1+ \frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(
\frac{2}{1-2.5^{-2}} 0.295a^{2s} \sigma_{v1}^2
\frac{2}{1-2.5^{-2}} \frac{2.5 \frac{1}{70}}{(1-2.5^{-1})^2} a^{-2} \sigma_{v2}^2 ))^{k_2-k_1-1}\\
\frac{1}{2}\log(1+\frac{1}{k_2-k_1-1}(\frac{2}{1-2.5^{-2}}0.295+\frac{2}{1-2.5^{-2}}\frac{\frac{1}{70}\frac{1}{2.5}}{(1-2.5^{-1})^{2}}))^{k_2-k_1-1} \\
\frac{1}{2}\log(1+\frac{0.7401738...}{k_2-k_1-1})^{k_2-k_1-1} \\
\frac{1}{2}\log(1+\frac{0.7402}{k_2-k_1-1})^{k_2-k_1-1} \\
\frac{1}{2}\log(e^{0.7402}).
\end{align}

(A): Assumptions $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$ and $|a| \geq 2.5$.

(B): Assumptions $a^{2s}\sigma_{v1}^2 \leq \sigma_{v2}^2$ and $|a| \geq 2.5$.

Likewise, $I'(\widetilde{P_1})$ is upper bounded as

\begin{align}
&I'(\widetilde{P_1}) \leq \frac{1}{2}\log(e^{0.7402}) +
\frac{1}{2} \log(1+\frac{1}{\sigma_{v2}^2}(2a^{2(k_2-1-k_1)}\Sigma+2\frac{a^{2(k_2-2-k_1)}\widetilde{P_1}}{(1-2.5a^{-2})(1-2.5^{-1})})) \\
&\overset{(A)}{\leq}  \frac{1}{2}\log(e^{0.7402}) +  \frac{1}{2} \log(1+\frac{1}{\sigma_{v2}^2}(2a^{2s}0.295a^2 \sigma_{v1}^2+2 \frac{a^{2(s-1)}\frac{1}{70}\frac{\sigma_{v2}^2}{a^{2(s-1)}}}{(1-2.5^{-1})^2})) \\
&=  \frac{1}{2}\log(e^{0.7402}) + \frac{1}{2} \log( \frac{1}{\sigma_{v2}^2}( \sigma_{v2}^2 + 2 \times 0.295 a^{2(s+1)}\sigma_{v1}^2  + \frac{1}{35(1-2.5^{-1})^2}\sigma_{v2}^2) )\\
&\overset{(B)}{\leq}  \frac{1}{2}\log(e^{0.7402}) + \frac{1}{2} \log( \frac{1}{\sigma_{v2}^2}( a^{2(s+1)}\sigma_{v1}^2 + 2 \times 0.295 a^{2(s+1)}\sigma_{v1}^2  + \frac{1}{35(1-2.5^{-1})^2}a^{2(s+1)}\sigma_{v1}^2) ) \\
&= \frac{1}{2}\log(e^{0.7402}) +
\frac{1}{2} \log( \frac{a^{2(s+1)}\sigma_{v1}^2}{\sigma_{v2}^2}( 1 + 2 \times 0.295   + \frac{1}{35(1-2.5^{-1})^2}) ) \\
&= \frac{1}{2}\log(e^{0.7402}) +
\frac{1}{2} \log( \frac{a^{2(s+1)}\sigma_{v1}^2}{\sigma_{v2}^2} 1.669365...)\\
&\leq \frac{1}{2}\log(e^{0.7402}) +
\frac{1}{2} \log( \frac{a^{2(s+1)}\sigma_{v1}^2}{\sigma_{v2}^2} 1.6694). \label{eqn:lemma3:2}
\end{align}

(A): Assumptions $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$ and $|a| \geq 2.5$.

(B): Assumption $\sigma_{v2}^2 \leq a^{2(s+1)} \sigma_{v1}^2$.

Moreover, since $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$, we have

\begin{align}
\frac{a^{2(k_2-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2} \leq \frac{a^{2s}}{(1-2.5^{-1})^2} \frac{\sigma_{v2}^2}{70 a^{2(s-1)}} \leq \frac{a^2 \sigma_{v2}^2}{(1-2.5^{-1})^2 70}.\label{eqn:lemma3:3}
\end{align}

Therefore, by plugging (<ref>) and (<ref>) into (<ref>), we have

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) &\geq ( \sqrt{\frac{a^{2(s+1)}0.295 a^2 \sigma_{v1}^2 }{e^{0.7402} \frac{a^{2(s+1)}\sigma_{v1}^2}{\sigma_{v2}^2} 1.6694}} - \sqrt{\frac{a^2 \sigma_{v2}^2}{(1-2.5^{-1})^270}} )_+^2 +1 \\
&\geq 0.008 a^2 \sigma_{v2}^2 +1.
\end{align}

Proof of (b):

We choose $k_1, \Sigma, k_2, \alpha, \sigma_{v2}$ of Lemma <ref> in the same way as the proof of (a) except $k$. Then, we will increase $k$ arbitrarily large. Then, Lemma <ref> reduces to

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) \geq (\sqrt{\frac{a^{2(k-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}} - \sqrt{\frac{a^{2(k-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2}}
- \sqrt{\frac{a^{2(k-k_2-1)} 2.5^{k_2-k_1} \widetilde{P_1}}{(1-2.5^{-1})^2}}
- \sqrt{\frac{a^{2(k-k_2-1)} \widetilde{P_2}}{(1-2.5^{-1})^2}})_+^2 + 1. \label{eqn:lemma3:6}
\end{align}

Since the relevant parameters are the same, (<ref>) and (<ref>) in the proof of (a) still hold. Since $|a| \geq 2.5$ and $\widetilde{P_2} \leq \frac{a^4 \sigma_{v2}^2}{28000}$, we also have

\begin{align}
&= (\frac{2.5}{a^2})^{k_2-k_1} \frac{a^{2(k-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2}\\
&\leq (\frac{1}{2.5})^2 \frac{a^{2(k-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2} \label{eqn:lemma3:4}
\end{align}

\begin{align}
\frac{a^{2(k-k_2-1)} \widetilde{P_2}}{(1-2.5^{-1})^2} \leq \frac{a^{2(k-k_2-1)}}{(1-2.5^{-1})^2} \frac{a^4 \sigma_{v2}^2}{28000}. \label{eqn:lemma3:5}
\end{align}

Therefore, by plugging (<ref>), (<ref>), (<ref>), (<ref>) into (<ref>), we have

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) & \geq ( \sqrt{\frac{a^{2(s+1)}0.295 a^2 \sigma_{v1}^2 }{e^{0.7402} \frac{a^{2(s+1)}\sigma_{v1}^2}{\sigma_{v2}^2} 1.6694}} - (1+ \frac{1}{2.5})\sqrt{\frac{a^2 \sigma_{v2}^2}{(1-2.5^{-1})^270}} - \sqrt{\frac{a^2 \sigma_{v2}^2}{(1-2.5^{-1})^2 28000}} )_+^2 a^{2(k-k_2)} + 1\\
& \geq 10^{-6} a^{2(k-k_2+1)} \sigma_{v2}^2 +1.
\end{align}

Since $k$ can be chosen arbitrarily large, $\lim_{k \rightarrow \infty}D_{L,1}(\widetilde{P_1},\widetilde{P_2}) = \infty$.

Proof of (c):

We choose $k$, $k_1$, $k_2$, $\Sigma$ of Lemma <ref> in the same way as the proof of (a), i.e. $\Sigma=0.295a^2 \sigma_{v1}^2$ and $k_2=k=k_1+s+1$. We put the remaining parameters $\alpha$ and $\sigma_{v2}'$ as $\alpha=\frac{1}{2}$, $\sigma_{v2}'^2=100a^{2(s-1)}\widetilde{P_1}$.

Then, Lemma <ref> reduces to

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) \geq  \frac{1}{2}D'+\frac{1}{2}D''+1
\end{align}

\begin{align}
&D'=( \sqrt{c \frac{a^{2(k_2-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}} - \sqrt{c \frac{a^{2(k_2-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2}} )_+^2  \label{eqn:lemma3:10} \\
&D''=( \sqrt{\frac{a^{2(k_2-k_1-1)} \Sigma}{2^{2I''(\widetilde{P_1})}}} - \sqrt{\frac{ a^{2(k_2-k_1-2)} 2.5  \widetilde{P_1} }{(1-2.5^{-1})^2}})_+^2. \label{eqn:lemma3:11}
\end{align}

Here, $I''(\widetilde{P_1})$ is upper bounded as:

\begin{align}
&I''(\widetilde{P_1}) =\frac{1}{2} \log(1+\frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(\frac{2a^{2(k_2-2-k_1)}}{1-a^{-2}}\Sigma + \frac{2a^{2(k_2-3-k_1)} }{1-a^{-2}} \frac{2.5\widetilde{P_1}}{(1-2.5a^{-2})(1-2.5^{-1})}))^{k_2-k_1-1}\\
&\overset{(A)}{\leq} \frac{1}{2} \log(1+ \frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(
\frac{2a^{2(k_2-2-k_1)}}{1-2.5^{-2}}0.295 a^2 \sigma_{v1}^2 + \frac{2a^{2(k_2-3-k_1)}}{1-2.5^{-2}}
\frac{2.5\frac{1}{20000}a^4 \sigma_{v1}^2}{(1-2.5^{-1})^2}
))^{k_2-k_1-1} \\
&= \frac{1}{2} \log(1+ \frac{1}{(k_2-k_1-1)\sigma_{v2}^2}(
\frac{2}{1-2.5^{-2}}0.295  + \frac{2}{1-2.5^{-2}}
\frac{2.5\frac{1}{20000}}{(1-2.5^{-1})^2}
)a^{2s}\sigma_{v1}^2)^{k_2-k_1-1} \\
&\overset{(B)}{\leq} \frac{1}{2} \log(1+ \frac{1}{k_2-k_1-1}(
\frac{2}{1-2.5^{-2}}0.295  + \frac{2}{1-2.5^{-2}}
\frac{2.5\frac{1}{20000}}{(1-2.5^{-1})^2}
))^{k_2-k_1-1} \\
&= \frac{1}{2} \log(1 + \frac{1}{k_2-k_1-1} 0.703207...)^{k_2-k_1-1} \\
&\leq  \frac{1}{2} \log(1 + \frac{1}{k_2-k_1-1}0.7033)^{k_2-k_1-1} \\
&\leq \frac{1}{2} \log(e^{0.7033}). \label{eqn:lemma3:12}
\end{align}

(A): $\widetilde{P_1} \leq \frac{1}{20000}a^4 \sigma_{v1}^2$ and $|a| \geq 2.5$.

(B): $a^{2s}\sigma_{v1}^2 \leq \sigma_{v2}^2$.

Likewise, $I'(\widetilde{P_1})$ is upper bounded as:

\begin{align}
&I'(\widetilde{P_1}) \leq  \frac{1}{2} \log(1+ \frac{1}{\sigma_{v2}'^2}(2a^{2(k_2-1-k_1)}\Sigma + 2 \frac{a^{2(k_2-2-k_1)}\widetilde{P_1}}{(1-2.5a^{-2})(1-2.5^{-1})})) + \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4})\\
&\leq \frac{1}{2} \log(1+ \frac{1}{\sigma_{v2}'^2}(2a^{2s}\Sigma+ 2 \frac{a^{2(s-1)}\widetilde{P_1}}{(1-2.5^{-1})^2}))+ \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4}) \\
&= \frac{1}{2} \log(1+ \frac{1}{\sigma_{v2}'^2}(2a^{2s}(0.295a^2\sigma_{v1}^2)+ 2 \frac{a^{2(s-1)}\widetilde{P_1}}{(1-2.5^{-1})^2})) + \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4})\\
&= \frac{1}{2} \log(\frac{1}{100a^{2(s-1)}\widetilde{P_1}}(100a^{2(s-1)}\widetilde{P_1}+2\cdot 0.295 a^{2(s+1)}\sigma_{v1}^2+ 2 \frac{a^{2(s-1)}\widetilde{P_1}}{(1-2.5^{-1})^2})) + \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4})\\
&\overset{(A)}{\leq} \frac{1}{2} \log(\frac{1}{100a^{2(s-1)}\widetilde{P_1}}(\frac{100a^{2(s+1)}\sigma_{v1}^2}{20000}+2\cdot 0.295 a^{2(s+1)}\sigma_{v1}^2+ 2 \frac{a^{2(s+1)}\sigma_{v1}^2}{20000(1-2.5^{-1})^2 })) + \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4})\\
&= \frac{1}{2}\log(\frac{1}{100}(0.595277...)\frac{a^{2(s+1)}\sigma_{v1}^2}{a^{2(s-1)}\widetilde{P_1}})+ \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4})\\
&\leq \frac{1}{2}\log(\frac{1}{100}(0.5953)\frac{a^{2(s+1)}\sigma_{v1}^2}{a^{2(s-1)}\widetilde{P_1}})+ \frac{1}{2} \log(e^{0.7033})+ \frac{1}{2} \log(\frac{2 \pi e}{4}). \label{eqn:lemma3:13}
\end{align}

(A): Assumption $\widetilde{P_1} \leq \frac{a^4 \sigma_{v1}^2}{20000}$.

Therefore, by plugging (<ref>) into (<ref>), we get the following lower bound on $D'$:

\begin{align}
D' & \geq c(
\sqrt{\frac{0.295a^{2(s+2)}\sigma_{v1}^2}{e^{0.7033} \frac{2 \pi e}{4} \frac{1}{100} 0.5953 \frac{a^{2(s+1)}\sigma_{v1}^2}{a^{2(s-1)}\widetilde{P_1}} }}
- \sqrt{\frac{a^{2s}\widetilde{P_1}}{(1-2.5^{-1})^2}})_+^2\\
& = c(\sqrt{
\frac{0.295}{e^{0.7033}\frac{2 \pi e}{4} \frac{1}{100} 0.5953}
} -
\sqrt{\frac{1}{(1-2.5^{-1})^2}})_+^2 a^{2s} \widetilde{P_1}  \\
& = 0.532969... c a^{2s} \widetilde{P_1}\\
& \geq 0.5329 c a^{2s} \widetilde{P_1} \\
& = 0.5329 \frac{2 \cdot 10 a^{s-1}\sqrt{\widetilde{P_1}}}{\sqrt{2\pi}\sigma_{v2}} \exp(- \frac{100 a^{2(s-1)}\widetilde{P_1}}{2\sigma_{v2}^2}) a^{2s} \widetilde{P_1} \\
& \overset{(A)}{\geq}  0.5329 \frac{2 \cdot 10 }{\sqrt{2\pi}\sqrt{70}} \exp(- \frac{100 a^{2(s-1)}\widetilde{P_1}}{2\sigma_{v2}^2}) a^{2s} \widetilde{P_1}\\
& = 0.508202... a^{2s}\widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) \\
& \geq 0.5082a^{2s}\widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}).
\end{align}

(A): Assumption $\widetilde{P_1} \geq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$.

Since $\widetilde{P_1} \leq \frac{a^4 \sigma_{v1}^2}{20000}$, we also have

\begin{align}
&\frac{a^{2(k_2-k_1-2)}2.5 \widetilde{P_1}}{(1-2.5^{-1})^2}  \\
&\leq \frac{a^{2(s-1)}2.5 \frac{a^4 \sigma_{v1}^2}{20000}}{(1-2.5^{-1})^2} \\
&= \frac{2.5a^{2(s+1)} \sigma_{v1}^2}{20000(1-2.5^{-1})^2} \label{eqn:lemma3:14}
\end{align}

Therefore, by plugging (<ref>) and (<ref>) into (<ref>), $D''$ is lower bounded as:

\begin{align}
D'' &\geq ( \sqrt{ \frac{0.295a^{2(s+1)} \sigma_{v1}^2}{e^{0.7033}}} - \sqrt{ \frac{2.5 a^{2(s+1)}\sigma_{v1}^2}{20000(1-2.5^{-1})^2} })_+^2 \\
&= 0.132117... a^{2(s+1)} \sigma_{v1}^2\\
&\geq 0.1321 a^{2(s+1)} \sigma_{v1}^2
\end{align}

Finally, $D_{L,1}(\widetilde{P_1},\widetilde{P_2})$ is lower bounded as:

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) \geq 0.2541 a^{2s}\widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 0.066 a^{2(s+1)}\sigma_{v1}^2 + 1
\end{align}

Proof of (d):

We choose $k_1, k_2, \Sigma, \alpha, \sigma_{v2}'$ of Lemma <ref> in the same way as the proof of (c) except $k$. $k$ will be chosen arbitrarily large. Lemma <ref> reduces to

\begin{align}
D_{L,1}(\widetilde{P_1},\widetilde{P_2}) \geq \frac{1}{2}a^{2(k-k_2)}D' + \frac{1}{2}a^{2(k-k_2)}D'' +1 \label{eqn:lemma3:44}
\end{align}

\begin{align}
D'&= (\sqrt{c \frac{a^{2(k_2-k_1)}\Sigma}{2^{2I'(\widetilde{P_1})}}} - \sqrt{ c \frac{a^{2(k_2-k_1-1)}\widetilde{P_1}}{(1-2.5^{-1})^2}}
- \sqrt{\frac{a^{-2}2.5^{k_2-k_1}\widetilde{P_1}}{(1-2.5^{-1})^2}}
- \sqrt{\frac{a^{-2}\widetilde{P_2}}{(1-2.5^{-1})^2}})_+^2 \\
D''&=( \sqrt{\frac{a^{2(k_2-k_1-1)} \Sigma}{2^{2I''(\widetilde{P_1})}}} - \sqrt{\frac{ a^{2(k_2-k_1-2)} 2.5  \widetilde{P_1} }{(1-2.5^{-1})^2}} - \sqrt{\frac{a^{-2}\widetilde{P_2}}{(1-2.5^{-1})^2}} )_+^2.
\end{align}

Denote $P':=\sqrt{\frac{a^{-2}2.5^{k_2-k_1}\widetilde{P_1}}{(1-2.5^{-1})^2}} +  \sqrt{\frac{a^{-2}\widetilde{P_2}}{(1-2.5^{-1})^2}}$.
Then, following the same steps of the proof of (c), we can lower bound $D'$ and $D''$ as follows:

\begin{align}
D' &\geq (
\sqrt{0.5082a^{2s}\widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) }
- \sqrt{P'}
)_+^2 \label{eqn:lemma3:40}\\
D'' &\geq (
\sqrt{0.1321 a^{2(s+1)} \sigma_{v1}^2}
)_+^2 \\
&\geq ( \sqrt{0.1321 a^{2(s+1)} \sigma_{v1}^2} - \sqrt{P'})_+^2 \label{eqn:lemma3:41}
\end{align}

Here, we have

\begin{align}
&\leq \frac{a^{-2}|a|^{s+1}\widetilde{P_1}}{(1-2.5^{-1})^2} \  (\because |a| \geq 2.5) \\
&\leq \frac{a^{-2}a^{2s}\widetilde{P_1}}{(1-2.5^{-1})^2} \  (\because s \geq 1) \\
&\leq \frac{a^{2s}\max(1,a^2\sigma_{v1}^2)}{20000(1-2.5^{-1})^2} \  (\because \widetilde{P_1} \leq \frac{\max(a^2,a^4 \sigma_{v1}^2)}{20000})
\end{align}

\begin{align}
P'&\overset{(A)}{\leq} \sqrt{2(\frac{a^{-2}2.5^{k_2-k_1}\widetilde{P_1}}{(1-2.5^{-1})^2} + \frac{a^{-2}\widetilde{P_2}}{(1-2.5^{-1})^2})}\\
&\overset{(B)}{\leq} \sqrt{ \frac{a^{2s}\max(1,a^2\sigma_{v1}^2)}{10000(1-2.5^{-1})^2} + \frac{2}{(1-2.5^{-1})^2}(0.0457a^{2s}\widetilde{P_1} \exp(-\frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 0.0113 a^{2s} \max(1,a^2\sigma_{v1}^2) ) }\\
&\leq \sqrt{ 0.253889a^{2s}\widetilde{P_1} \exp(-\frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2})+ 0.0625 a^{2s} \max(1,a^2\sigma_{v1}^2)} \label{eqn:lemma3:42}
\end{align}

(A): Cauchy-Schwarz inequaility

(B): Assumptions on $\widetilde{P_1}$ and $\widetilde{P_2}$

By comparing (<ref>) with (<ref>) and (<ref>), we can conclude that either $D'$ or $D''$ has to be greater than $0$. Moreover, since we can choose $k$ arbitrarily large in (<ref>), $\lim_{k \rightarrow \infty} D_{L,1}(\widetilde{P_1},\widetilde{P_2})=\infty$.

Proof of (e):

The same as (a) of Corollary <ref>.

§.§ Proof of Corollary <ref>

For simplicity, we will only prove the case when $a \geq 2.5$. The proof for $a \leq -2.5$ easily follows by replacing $a$ with $|a|$.

We will evaluate Lemma <ref> with the parameters $w_1 = \frac{a^s d}{6}$ and $d = \sqrt{\frac{320000P}{a^2}}$. Then, we can easily see that $(d,w_1) \in S_{U,1}$. Furthermore, $\frac{a^s d}{\sigma_{v2}}\geq 13$ since

\begin{align}
&\frac{a^s d}{ \sigma_{v2}} =\frac{a^{s-1}\sqrt{320000 P}}{\sigma_{v2}} \\
&\geq \frac{a^{s-1}}{\sigma_{v2}} \sqrt{4 \cdot 80000 \frac{\sigma_{v2}^2}{70a^{2(s-1)}}} \ (\because P \geq \frac{\sigma_{v2}^2}{70a^{2(s-1)}})\\
&= \sqrt{\frac{4 \cdot 80000}{70}} \geq 13.
\end{align}

Then, we will upper bound $D_{U,1}(d,w_1)$. First, let's bound the second term of $D_{U,1}(d,w_1)$ in (<ref>). The second term is upper bounded as

\begin{align}
&\sum_{1 \leq i \leq \infty} 4 a^2 ( i a^s d + \frac{a^{s-1}d \frac{a}{a-1}+w_1}{2})^2 Q(\frac{(2i-1)a^s d - (a^{s-1}d \frac{a}{a-1}+w_1)}{2\sigma_{v2}})\\
&=4a^2 (a^s d + \frac{a^{s-1}d \frac{a}{a-1}+w_1}{2})^2 Q(\frac{a^s d - (a^{s-1}d \frac{a}{a-1}+w_1)}{2\sigma_{v2}})\\
&+4a^2 (2 a^s d + \frac{a^{s-1}d \frac{a}{a-1}+w_1}{2})^2 Q(\frac{3 a^s d - (a^{s-1}d \frac{a}{a-1}+w_1)}{2\sigma_{v2}}) + \cdots \\
4a^2 (a^s d + \frac{a^{s-1}d \frac{a}{a-1}+\frac{a^s d}{6}}{2})^2 Q(\frac{a^s d - (a^{s-1}d \frac{a}{a-1}+\frac{a^s d}{6})}{2\sigma_{v2}}) \\
&+ 4a^2 (2 a^s d + \frac{a^{s-1}d \frac{a}{a-1}+\frac{a^s d}{6}}{2})^2 Q(\frac{3 a^s d - (a^{s-1}d \frac{a}{a-1}+\frac{a^s d}{6})}{2\sigma_{v2}}) + \cdots \\
4a^2 (a^s d + \frac{1}{2(2.5-1)}a^s d + \frac{1}{12}a^s d )^2 Q(\frac{1}{2\sigma_{v2}}(1-\frac{1}{2.5-1}-\frac{1}{6})a^s d) \\
4a^2 (2 a^s d + \frac{1}{2(2.5-1)}a^s d + \frac{1}{12}a^s d )^2 Q(\frac{1}{2\sigma_{v2}}(3-\frac{1}{2.5-1}-\frac{1}{6})a^s d)+ \cdots \\
4a^2 (a^s d)^2 (1+\frac{5}{12})^2 Q(\frac{1}{2\sigma_{v2}}(1-\frac{5}{6})a^s d) \\
&+4a^2 (a^s d)^2 (2+\frac{5}{12})^2 Q(\frac{1}{2\sigma_{v2}}(3-\frac{5}{6})a^s d) + \cdots  \label{eqn:ageq44}
\end{align}

Denote $k:=\frac{a^s d}{\sigma_{v2}}$. Since we already know $k \geq 13$, for all $n \geq 1$ we have

\begin{align}
&\frac{(n+\frac{5}{12})^2 Q(\frac{1}{2 \sigma_{v2}}(2n-1-\frac{5}{6})a^s d) }{(n+1+\frac{5}{12})^2 Q(\frac{1}{2 \sigma_{v2}}(2n+1-\frac{5}{6})a^s d)} \\
\frac{(n+\frac{5}{12})^2 ( \frac{1}{\frac{1}{2 \sigma_{v2}}(2n-1-\frac{5}{6})a^s d} - \frac{1}{(\frac{1}{2 \sigma_{v2}}(2n-1-\frac{5}{6})a^s d)^3} ) \exp(-\frac{(\frac{1}{2 \sigma_{v2}}(2n-1-\frac{5}{6})a^s d)^2}{2})}{(n+1+\frac{5}{12})^2 (\frac{1}{\frac{1}{2 \sigma_{v2}}(2n+1-\frac{5}{6})a^s d}) \exp(-\frac{(\frac{1}{2 \sigma_{v2}}(2n+1-\frac{5}{6})a^s d)^2}{2})} \ (\because Lemma~\ref{ach:lemma4})\\
\frac{(n+\frac{5}{12})^2 ( \frac{1}{\frac{1}{2}(2n-1-\frac{5}{6}) k} - \frac{1}{(\frac{1}{2}(2n-1-\frac{5}{6})k)^3} ) \exp(-\frac{(\frac{1}{2}(2n-1-\frac{5}{6}) k)^2}{2})}{(n+1+\frac{5}{12})^2 (\frac{1}{\frac{1}{2}(2n+1-\frac{5}{6})k}) \exp(-\frac{(\frac{1}{2}(2n+1-\frac{5}{6})k)^2}{2})}\\
\frac{( \frac{1}{\frac{1}{2}(2n-1-\frac{5}{6}) k} - \frac{1}{(\frac{1}{2}(2n-1-\frac{5}{6})k)^3} ) }
\frac{\exp(-\frac{( \frac{1}{12}k)^2}{2})}{\exp(-\frac{(\frac{13}{12}k)^2}{2})} \ (\because n \geq 1)\\
\exp(\frac{7}{12}k^2)
(\frac{\frac{1}{2}(2n+1-\frac{5}{6})}{\frac{1}{2}(2n-1-\frac{5}{6})}- \frac{\frac{1}{2}(2n+1-\frac{5}{6})}{(\frac{1}{2}(2n-1-\frac{5}{6}))^3 13^2}) \ (\because k \geq 13)\\
&\overset{(A)}{\geq} (\frac{1+\frac{5}{12}}{2+\frac{5}{12}})^2 \exp(\frac{7}{12}k^2) 0.99\\
&\geq 10^{42}\ (\because k \geq 13)
\end{align}

(A): When $n=1$, we can check the inequality by computation. When $n \geq 2$, we have

\begin{align}
&\frac{\frac{1}{2}(2n+1-\frac{5}{6})}{\frac{1}{2}(2n-1-\frac{5}{6})}- \frac{\frac{1}{2}(2n+1-\frac{5}{6})}{(\frac{1}{2}(2n-1-\frac{5}{6}))^3 13^2}\\
&\geq 1 - \frac{\frac{1}{2}(4+1-\frac{5}{6})}{(\frac{1}{2}(4-1-\frac{5}{6}))^3 13^2} \geq 0.99.
\end{align}

Thus, the terms in (<ref>) decrease faster than a geometric sequence with ratio $10^{-42}$ and thus can be upper bounded as

\begin{align}
\eqref{eqn:ageq44} \leq 4 a^2 (a^s d)^2 (1+\frac{5}{12})^2  Q(\frac{1}{2\sigma_{v2}}(1-\frac{5}{6})a^s d) \frac{1}{1-10^{-42}}. \label{eqn:ach:geo1}
\end{align}

The third term of $D_{U,1}(d,w_1)$ in (<ref>) can also be bounded similarly. We have

\begin{align}
&\frac{(a^s d + \frac{a^s d}{2})^2 \frac{1}{2}}{(2 a^s d  + \frac{a^s d}{2})^2  Q(\frac{a^s d}{\sigma_{v2}})}
\geq \frac{(1+\frac{1}{2})^2}{(2+\frac{1}{2})^2 2 Q(13)}\ (\because \frac{a^s d}{\sigma_{v2}}\geq 13)\\
&\geq 10^{37}
\end{align}

and for $n \geq 2$

\begin{align}
&\frac{(n+\frac{1}{2})^2 Q(\frac{(n-1)ad}{\sigma_{v2}})}{((n+1)+\frac{1}{2})^2 Q(\frac{nad}{\sigma_{v2}})}\\
&\geq \frac{(n+\frac{1}{2})^2 ( \frac{1}{\frac{(n-1)ad}{\sigma_{v2}}} - \frac{1}{(\frac{(n-1)ad}{\sigma_{v2}})^3} )\exp(- \frac{(\frac{(n-1)ad}{\sigma_{v2}})^2}{2})}{((n+1)+\frac{1}{2})^2 (\frac{1}{\frac{n ad}{\sigma_{v2}}})  \exp(-\frac{(\frac{nad}{\sigma_{v2}})^2}{2})} \ (\because Lemma~\ref{ach:lemma4})\\
&= \exp(\frac{2n-1}{2}k^2) \frac{(n+\frac{1}{2})^2 (\frac{1}{(n-1)k} - \frac{1}{(n-1)^3 k^3}) }{((n+1)+\frac{1}{2})^2 (\frac{1}{nk})}\\
%&\geq \exp(\frac{3}{2}k^2) \frac{(2+\frac{1}{2})^2}{(3+\frac{1}{2})^2}(1-\frac{2}{k^2}) \\
&\geq \exp(\frac{3}{2}13^2) \frac{(2+\frac{1}{2})^2}{(3+\frac{1}{2})^2}(\frac{n}{n-1}-\frac{n}{(n-1)^3 13^2})
\ (\because n \geq 2, k \geq 13)\\
&\overset{(A)}{\geq} \exp(\frac{3}{2}13^2)\frac{(2+\frac{1}{2})^2}{(3+\frac{1}{2})^2} 0.98\\
&\geq 10^{109}.
%&\geq 9 \times 10^{15}
\end{align}

(A): Since $n \geq 2$, we have

\begin{align}
\frac{n}{n-1}-\frac{n}{(n-1)^3 13^2} \geq 1 - \frac{2}{(2-1)^3 13^2} \geq 0.98.
\end{align}

Therefore, the third term of $D_{U,1}(d,w_1)$ in (<ref>) is upper bounded by

\begin{align}
4 a^2 Q(\frac{\frac{a^s d}{6}}{2 \sqrt{a^{2(s-1)}\frac{a^2}{a^2-1}+a^{2s}\sigma_{v1}^2}})
(a^s d + \frac{a^s d}{2})^2  \frac{1}{1-10^{-37}}. \label{eqn:ach:geo2}
\end{align}

By plugging (<ref>) and (<ref>) into (<ref>), we can bound $D_{U,1}(d,w_1)$ of Lemma <ref> as follows.

\begin{align}
& \leq 2 a^{2s}(2 (\frac{d}{2})^2 (\frac{1}{1-\frac{1}{a}})^2 + 2 (\frac{1}{1-\frac{1}{a^2}}) + 2a^2 \sigma_{v1}^2 ) \\
&+ 4 a^2 (a^s d)^2 (1+\frac{5}{12})^2  Q(\frac{1}{2\sigma_{v2}}(1-\frac{5}{6})a^s d) \frac{1}{1-10^{-42}} \\
&+4 a^2 Q(\frac{\frac{a^s d}{6}}{2 \sqrt{a^{2(s-1)}\frac{a^2}{a^2-1}+a^{2s}\sigma_{v1}^2}})
(a^s d + \frac{a^s d}{2})^2  \frac{1}{1-10^{-37}} \\
& + 2(a^2 (\frac{d}{2})^2)+1 \\
& \overset{(A)}{\leq} 2 a^{2s} (2 (\frac{d}{2})^2 (\frac{5}{3})^2 + \frac{50}{21}+2a^2 \sigma_{v1}^2)\\
&+4 a^2 (a^s d)^2 (\frac{17}{12})^2  Q(\frac{a^s d}{12 \sigma_{v2}}) \frac{1}{1-10^{-42}} \\
&+4 a^2 Q(\frac{\frac{a^s d}{6}}{2 \sqrt{a^{2(s-1)}\frac{25}{21}+a^{2s}\sigma_{v1}^2}})(a^sd+\frac{a^sd}{2})^2 \frac{1}{1-10^{-37}}\\
&+2(a^2 (\frac{d}{2})^2) + 1 \\
& \overset{(B)}{\leq} 2 a^{2s} (2 (\frac{d}{2})^2 (\frac{5}{3})^2 + \frac{50}{21}+2a^2 \sigma_{v1}^2)\\
&+4 a^2 (a^s d)^2 (\frac{17}{12})^2  Q(\frac{a^s d}{12 \sigma_{v2}}) \frac{1}{1-10^{-42}} \\
&+4 a^2 (a^sd+\frac{a^sd}{2})^2  Q(\frac{a^s d}{12 \sqrt{\frac{46}{21}} \sigma_{v2}}) \frac{1}{1-10^{-37}}\\
&+2(a^2 (\frac{d}{2})^2) + 1 \\
& \leq 2 a^{2s} (2 (\frac{d}{2})^2 (\frac{5}{3})^2 + \frac{50}{21}+2a^2 \sigma_{v1}^2)\\
&+4 a^2 (a^s d)^2 (\frac{17}{12})^2 Q(\frac{a^s d}{12 \sqrt{\frac{46}{21}} \sigma_{v2}}) \frac{1}{1-10^{-42}} \\
&+4 a^2 (a^sd+\frac{a^sd}{2})^2  Q(\frac{a^s d}{12 \sqrt{\frac{46}{21}} \sigma_{v2}}) \frac{1}{1-10^{-37}}\\
&+2(a^2 (\frac{d}{2})^2) + 1 \\
&= 1 + \frac{100}{21}a^{2s} + \frac{25}{9} a^{2s} d^2 + \frac{a^2 d^2}{2} + 4a^{2(s+1)}\sigma_{v1}^2 \\
(4(\frac{17}{12})^2 \frac{1}{1-10^{-42}} + 9 \frac{1}{1-10^{-37}}) a^{2(s+1)}d^2
Q(\frac{a^s d}{12\sqrt{\frac{46}{21}}\sigma_{v2}}) \\
1 + \frac{100}{21}a^{2s} + \frac{25}{9} a^{2s} d^2 + \frac{a^2 d^2}{2} + 4a^{2(s+1)}\sigma_{v1}^2 +
17.03 a^{2(s+1)}d^2
Q(\frac{a^s d}{12\sqrt{\frac{46}{21}}\sigma_{v2}})
\end{align}

\begin{align}
&= 1 + \frac{100}{21}a^{2s} + \frac{25}{9} 4 \cdot 80000 a^{2(s-1)}P + 2 \cdot 80000 P + 4a^{2(s+1)}\sigma_{v1}^2 +
17.03 \cdot 4 \cdot 80000 a^{2s} P \cdot
Q(\frac{a^{s-1} \sqrt{4 \cdot 80000 P}}{12\sqrt{\frac{46}{21}}\sigma_{v2}}) \\
&\overset{(C)}{\leq} 1 + \frac{100}{21}a^{2s} + \frac{25}{9} 16 a^{2(s-1)} \max(a^2,a^4 \sigma_{v1}^2) + 8 \max(a^2 ,a^4 \sigma_{v1}^2) + 4 a^{2(s+1)}\sigma_{v1}^2\\
&+17.03 \cdot 4 \cdot 80000 a^{2s}P \frac{1}{\sqrt{2 \pi} \frac{a^{s-1}\sqrt{4 \cdot 80000P}}{12 \sqrt{\frac{46}{21}} \sigma_{v2}}} \exp(- \frac{1}{2} \frac{a^{2(s-1)} 4 \cdot 80000P}{144 \cdot \frac{46}{21} \sigma_{v2}^2}) \\
&= 1 + \frac{100}{21}a^{2s} + \frac{25}{9} 16 a^{2(s-1)} \max(a^2,a^4 \sigma_{v1}^2) + 8 \max(a^2 ,a^4 \sigma_{v1}^2) + 4 a^{2(s+1)}\sigma_{v1}^2\\
&+17.03 \cdot 4 \cdot 80000  \frac{\sqrt{70}}{\sqrt{2 \pi} \frac{\sqrt{4 \cdot 80000}}{12 \sqrt{\frac{46}{21}} }} \exp(- (\frac{1}{2} \frac{ 4 \cdot 80000}{144 \cdot \frac{46}{21} }-50) \frac{a^{2(s-1)}P}{\sigma_{v2}^2}) a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
&\overset{(D)}{\leq} 1 + \frac{100}{21}a^{2s} + \frac{25}{9} 16 a^{2(s-1)} \max(a^2,a^4 \sigma_{v1}^2) + 8 \max(a^2 ,a^4 \sigma_{v1}^2) + 4 a^{2(s+1)}\sigma_{v1}^2\\
&+17.03 \cdot 4 \cdot 80000  \frac{\sqrt{70}}{\sqrt{2 \pi} \frac{\sqrt{4 \cdot 80000}}{12 \sqrt{\frac{46}{21}} }} \exp(- (\frac{1}{2} \frac{ 4 \cdot 80000}{144 \cdot \frac{46}{21} }-50) \frac{1}{70})a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
&\leq 1 + \frac{100}{21}a^{2s} + \frac{25}{9} 16 a^{2(s-1)} \max(a^2,a^4 \sigma_{v1}^2) + 8 \max(a^2 ,a^4 \sigma_{v1}^2) + 4 a^{2(s+1)}\sigma_{v1}^2\\
&+831.473...a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
1 + (\frac{100}{21} + \frac{25}{9} 16  + 8  + 4 ) a^{2s} \max(1,a^2 \sigma_{v1}^2)+831.473...a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
1 + 61.206... a^{2s} \max(1,a^2 \sigma_{v1}^2)+831.473...a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
&\leq 1 + 62 a^{2s} \max(1,a^2 \sigma_{v1}^2)+832 a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) \\
&\leq 832 a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) + 63a^{2s} \max(1,a^2 \sigma_{v1}^2)
\end{align}

(A): $a \geq 2.5$.

(B): From the assumption $a^{2(s-1)}\max(1,a^2 \sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^{2s}\max(1,a^2 \sigma_{v1}^2)$, we have

\begin{align}
a^{2(s-1)}\frac{25}{21}+ a^{2s} \sigma_{v1}^2 \leq \frac{46}{21}\max(a^{2(s-1)},a^{2s}\sigma_{v1}^2) \leq \frac{46}{21}\sigma_{v2}^2.
\end{align}

(C): $P \leq \frac{\max(a^2 ,a^4 \sigma_{v1}^2)}{20000}$ and Lemma <ref>.

(D): $P \geq \frac{\sigma_{v2}^2}{70a^{2(s-1)}}$.

This justifies the upper bound on $D_U(P_1,P_2)$. By the definition of $d$ and Lemma <ref>, $P_1$ is upper bounded by $80000P$. $P_2$ of Lemma <ref> can be upper bounded as

\begin{align}
&P_2 \leq 8a^2 D_{U,1}(d,w_1) + \frac{7}{2}a^{2(s+1)}d^2+4a^2 \sigma_{v2}^2\\
&= 8a^2 D_{U,1}(d,w_1) + \frac{7}{2} 4 \cdot 80000a^{2s} P + 4 a^2 \sigma_{v2}^2 \\
&\leq 8a^2 (832 a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2})+63 a^{2s} \max(1,a^2 \sigma_{v1}^2)) \\
&+ \frac{7}{2} 4 \cdot 4 a^{2s}\max(a^2 ,a^4 \sigma_{v1}^2) + 4 a^2 a^{2s}\max(1,a^2 \sigma_{v1}^2) \\
&=  8a^2 (832 a^{2s}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) + 70.5 a^{2s} \max(1,a^2 \sigma_{v1}^2)) \\
&= 6656 a^{2(s+1)}P \exp(-\frac{50a^{2(s-1)}P}{\sigma_{v2}^2}) + 564 a^{2(s+1)} \max(1,a^2 \sigma_{v1}^2).
\end{align}

where the inequality comes from the assumptions $P \leq \frac{\max(a^2 , a^4 \sigma_{v1}^2)}{20000} $ and $\sigma_{v2}^2 \leq a^{2s}\max(1,a^2 \sigma_{v1}^2)$. This finishes the proof.

§.§ Proof of Proposition <ref>

As the proof of Proposition <ref>, by Lemma <ref> it is enough to show that there exists $c \geq 1$ such that $D_U(c \widetilde{P_1},c \widetilde{P_2}) \leq c \cdot D_L(\widetilde{P_1},\widetilde{P_2})$.

(i) When $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70 a^{2(s-1)}}$ and $\widetilde{P_2} \leq \frac{a^4 \sigma_{v2}^2}{28000}$

Lower bound: By Corollary <ref> (b)

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2})= \infty.
\end{align}

Therefore, we do not need the corresponding upper bound.

(ii) When $\widetilde{P_1} \leq \frac{\sigma_{v2}^2}{70 a^{2(s-1)}}$ and $\widetilde{P_2} \geq \frac{a^4 \sigma_{v2}^2}{28000}$

Lower bound: By Corollary <ref> (a)

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.008 a^2 \sigma_{v2}^2 +1.
\end{align}

Upper bound: By Lemma <ref>

\begin{align}
(D_U(P_1,P_2),P_1,P_2) &\leq (a^2 \sigma_{v2}^2 +1,0, a^4\sigma_{v2}^2+ a^2 \sigma_{v2}^2 + a^2)\\
&\leq (a^2 \sigma_{v2}^2 +1,0, a^4\sigma_{v2}^2+ a^2 \sigma_{v2}^2 + a^2 \sigma_{v2}^2)\\
&\leq (a^2 \sigma_{v2}^2 +1,0, (1+\frac{2}{2.5^2})a^4\sigma_{v2}^2)\\
&\leq (a^2 \sigma_{v2}^2 +1,0, 1.32 a^4\sigma_{v2}^2).
\end{align}

Ratio: Thus, $c$ is upper bounded by

\begin{align}
c \leq \max(\frac{1}{0.008}, \frac{1.32}{\frac{1}{28000}}).
\end{align}

(iii) When $\frac{\sigma_{v2}^2}{70 a^{2(s-1)}} \leq \widetilde{P_1} \leq \frac{1}{20000}\max(a^2,a^4 \sigma_{v1}^2)$ and
$\widetilde{P_2} \leq 0.0457a^{2(s+1)}\widetilde{P_1} \exp(-\frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 0.0113 a^{2(s+1)} \max(1,a^2\sigma_{v1}^2)$

Lower bound: By Corollary <ref> (d)

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) = \infty
\end{align}

Therefore, we do not need the corresponding upper bound.

(iv) When $\frac{\sigma_{v2}^2}{70 a^{2(s-1)}} \leq \widetilde{P_1} \leq \frac{1}{20000}\max(a^2,a^4 \sigma_{v1}^2)$ and
$\widetilde{P_2} \geq 0.0457a^{2(s+1)} \widetilde{P_1} \exp(-\frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 0.0113 a^{2(s+1)} \max(1,a^2\sigma_{v1}^2)$

Lower bound: By Corollary <ref> (c)

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.2541 a^{2s} \widetilde{P_1}\exp(- \frac{50 a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2})+0.066 a^{2s}\max(1,a^2\sigma_{v1}^2) + 1
\end{align}

Upper bound: By Corollary <ref>

\begin{align}
(D_U(P_1,P_2),P_1,P_2 ) \leq &( 63a^{2s} \max(1,a^2 \sigma_{v1}^2)+832 a^{2s}\widetilde{P_1} \exp(-\frac{50a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) ,80000\widetilde{P_1} \\
&, 6656 a^{2(s+1)}\widetilde{P_1} \exp(-\frac{50a^{2(s-1)}\widetilde{P_1}}{\sigma_{v2}^2}) + 564 a^{2(s+1)} \max(1,a^2 \sigma_{v1}^2))
\end{align}

Ratio: $c$ is upper bounded  by

\begin{align}
c \leq \max(\frac{832}{0.2541},\frac{63}{0.066}, 80000, \frac{6656}{0.0457}, \frac{564}{0.0113})
\end{align}

(v) When $\widetilde{P_1} \geq \frac{1}{20000}\max(a^2 ,a^4 \sigma_{v1}^2)$

Lower bound: By Corollary <ref> (e)

\begin{align}
D_L(\widetilde{P_1},\widetilde{P_2}) \geq 0.295 \cdot \max(1,a^2 \sigma_{v1}^2)
\end{align}

Upper bound: By Lemma <ref>

\begin{align}
(D_U(P_1,P_2),P_1,P_2) &\leq (a^2 \sigma_{v1}^2 +1, a^4\sigma_{v1}^2+ a^2 \sigma_{v1}^2 + a^2, 0) \\
&\leq (a^2 \sigma_{v1}^2 +1, 2a^4\sigma_{v1}^2+ a^2, 0) \\
&\leq (2 \max(1, a^2 \sigma_{v1}^2), 3\max(a^2,a^4 \sigma_{v1}^2) , 0)
\end{align}

Ratio: $c$ is upper bounded by

\begin{align}
c \leq \max(\frac{2}{0.295}, \frac{3}{\frac{1}{20000}})
\end{align}

Therefore, by (i), (ii), (iii), (iv), (v), the lemma is true and $c \leq 1.5 \times 10^5$.

§.§ Proof of Proposition <ref>

Since $a$ goes to infinity, let $a \geq 10000$.  We will first show the best linear strategy performance is $\Theta(a^3)$.

$\bullet$ The best linear strategy performance is $\Theta(a^3)$: Following the same steps in the proof of Lemma <ref>, we can lower bound the average cost as follows:

\begin{align}
&\inf_{u_1,u_2 \in L_{lin}'} \frac{1}{N} \sum_{0 \leq n < N}  \mathbb{E}[qx^2[n]+r_1 u_1^2[n]]
\\
&=\inf_{u_1, u_2 \in L_{lin}'} \frac{1}{N}
\frac{1}{2}r_1 \mathbb{E}[u_1^2[1]] + \frac{1}{2}r_1 \mathbb{E}[u_1^2[2]] + q\mathbb{E}[x^2[3]]
)+ (
\frac{1}{2}r_1 \mathbb{E}[u_1^2[2]] + \frac{1}{2}r_1 \mathbb{E}[u_1^2[3]] + q\mathbb{E}[x^2[4]]
) + \cdots \\
\frac{1}{2}r_1 \mathbb{E}[u_1^2[N-3]] + \frac{1}{2}r_1 \mathbb{E}[u_1^2[N-2]] + q\mathbb{E}[x^2[N-1]]
&\geq \frac{N-3}{N} \inf_{u_1,u_2 \in L_{lin}'} (\frac{1}{2}r_1 \mathbb{E}[u_1^2[1]] + \frac{1}{2}r_1 \mathbb{E}[u_1^2[2]]
+q \mathbb{E}[x^2[3]]
&= \frac{N-3}{N} \inf_{u_1,u_2 \in L_{lin}'} (\frac{1}{2} a \mathbb{E}[u_1^2[1]] + \frac{1}{2} a \mathbb{E}[u_1^2[2]]
+ \mathbb{E}[x^2[3]]
%&= \frac{1}{2} r_1 \mathbb{E}[u_1^2[1]]+\frac{1}{2} r_1 \mathbb{E}[u_1^2[2]]+\mathbb{E}[(a^3 x[0] + a^2 w[0] + aw[1] + w[2] + a^2 u_1[0] + a^2 u_2[0] + a u_1[1] + a u_2[1] + u_1[2] + u_2[2] )^2] \\
\end{align}

In the similar way of Proposition <ref>, we can further justify that setting $w[1]=0$, $w[2]=0$ only decrease the quadratic cost. Then, at time $1$ we have

\begin{align}
&x[1]=w[0] \\
&y_1[1]=w[0] \\
\end{align}

\begin{align}
&u_1[1]=k_{11} w[0]\\
\end{align}

At time $2$ we have

\begin{align}
\end{align}

Therefore, we can put

\begin{align}
&u_1[2]= k_{12} w[0] + k_{13} v_2[1]\\
&u_2[3]= k_{22} (w[0]+v_2[1]) + k_{23}(aw[0]+k_{11}w[0]+v_2[2])
\end{align}

At time $3$ we have

\begin{align}
&=a^2 w[0] + a k_{11}w[0]+ak_{21}(w[0]+v_2[1])+k_{12} w[0] + k_{13}v_2[1] \\
&+ k_{22}(w[0]+v_2[1]) + k_{23}(aw[0]+k_{11}w[0]+v_2[2])\\
&=(a^2 + a k_{11} + k_{12}) w[0] + k_{13}v_2[1] + (ak_{21}+k_{22})(w[0]+v_2[1]) + k_{23}(aw[0]+k_{11}w[0]+v_2[2])\\
&=(a^2 + a k_{11} + k_{12} - k_{13}) w[0] + (ak_{21}+k_{22}+k_{13})(w[0]+v_2[1]) + k_{23}(aw[0]+k_{11}w[0]+v_2[2])
\end{align}

\begin{align}
\mathbb{E}[x^2[3]] \geq (a^2+ak_{11}+k_{12}-k_{13})^2 MMSE[w[0]|w[0]+v_2[1],aw[0]+k_{11}w[0]+v_2[2]]
\end{align}

(i) When $\mathbb{E}[u_1^2[1]]+\mathbb{E}[u_1^2[2]] \leq \frac{1}{16}a^2$

The condition implies

\begin{align}
&\mathbb{E}[(k_{11}w[0])^2] + \mathbb{E}[(k_{12}w[0]+k_{13}v_2[1])^2] \\
&=k_{11}^2 + k_{12}^2 + k_{13}^2 a  \leq \frac{1}{16}a^2
\end{align}

\begin{align}
&|k_{11}| \leq \frac{1}{4}a\\
&|k_{12}| \leq \frac{1}{4}a\\
&|k_{13}| \leq \frac{1}{4} \sqrt{a}
\end{align}

Since $a \geq 10000$ we have

\begin{align}
a^2+ak_{11}+k_{12}-k_{13} &\geq a^2 - \frac{a^2}{4} - \frac{a^2}{4} - \frac{a^2}{4}=\frac{a^2}{4}
\end{align}

Moreover, we also have

\begin{align}
&MMSE[w[0]| w[0]+v_2[1], aw[0]+k_{11}w[0]+v_2[2]] \\
&\geq MMSE[w[0] | w[0]+v_2[1], \frac{5a}{4}w[0]+v_2[2]] \\
&\geq MMSE[w[0] | \frac{5a}{4}w[0]+v_2[1], \frac{5a}{4}w[0]+v_2[2]] \\
&= MMSE[w[0] | \frac{10a}{4}w[0]+v_2[1]+v_2[2]] \\
&= 1 - \frac{(\frac{10a}{4})^2}{(\frac{10a}{4})^2+2a}\\
&= \frac{2a}{(\frac{10a}{4})^2 + 2a} \\
&\geq \frac{2}{(\frac{10}{4})^2+2} \frac{1}{a} = \frac{8}{33a}
\end{align}

Therefore, in this case,

\begin{align}
\inf_{u_1,u_2 \in L_{lin}'} \frac{1}{2} a \mathbb{E}[u_1^2[1]] + \frac{1}{2} a \mathbb{E}[u_1^2[2]]
+ \mathbb{E}[x^2[3]] \geq \frac{1}{16} \cdot \frac{8}{33} a^3
\end{align}

(ii) When $\mathbb{E}[u_1^2[1]]+\mathbb{E}[u_1^2[2]] \geq \frac{1}{16}a^2$
In this case

\begin{align}
\inf_{u_1,u_2 \in L_{lin}'} \frac{1}{2} a \mathbb{E}[u_1^2[1]] + \frac{1}{2} a \mathbb{E}[u_1^2[2]]
+ \mathbb{E}[x^2[3]] \geq \frac{1}{32} a^3
\end{align}

Therefore, by (i),(ii),

\begin{align}
\inf_{u_1,u_2 \in L_{lin}'} \frac{1}{2} a \mathbb{E}[u_1^2[1]] + \frac{1}{2} a \mathbb{E}[u_1^2[2]]
+ \mathbb{E}[x^2[3]] \geq \frac{1}{66} a^3 \label{eqn:prop1}
\end{align}

$\bullet$ The optimal average cost is $O(a^2 \log a)$: Now, we will show the average cost, $O(a^2 \log a)$, is achievable by the nonlinear $1$-stage signaling strategy. Let $a \geq 20000$.
Since $\max(1,a^2\sigma_{v1}^2) \leq \sigma_{v2}^2 \leq a^2 \max(1,a^2 \sigma_{v1}^2)$ and $\frac{a}{70} \leq \frac{a \log a}{25} \leq \frac{1}{20000} a^2$, we can set $s=1$ and $P=\frac{a \log a}{25}$ in Corollary <ref>.

Then, by Corollary <ref>, the average cost is upper bounded as follows.

\begin{align}
&\inf_{u_1,u_2 \in L_{sig,1}} \frac{1}{N} \sum_{0 \leq n < N} \mathbb{E}[qx^2[n]+r_1 u_1^2[n]] \\
&\leq 832 a^2 \frac{a \log a}{25} \exp(- \frac{50 \frac{a \log a}{25}}{a})+ 63a^2 +  a \frac{80000a \log a}{25}\\
&\leq  832 \frac{a \log a}{25} +63a^2 + \frac{80000}{25}a^2 \log a\\
&\leq 3297 a^2 \log a \label{eqn:prop2}
\end{align}

In short, by (<ref>) the optimal linear strategy cost is lower bounded by $\Omega(a^3)$ . By (<ref>), the nonlinear $1$-stage signaling strategy can achieve $O(a^2 \log a)$. Thus, their ratio diverges as $a$ goes to infinity, which finishes the proof.