4
$\begingroup$

Let $A=\{a_{ij}\}_{1\le i,j\le n}$ be an $n$ by $n$ normalized Gaussian random matrix with $E[a_{ij}]=0$ and $E[a_{ij}^2]=1/n$. Ordering its eigenvalues by $\lambda_1\le \lambda_2\le \cdots \lambda_n$ with corresponding eigenvectors $v_1,\dots, v_n \in \mathbb{R}^n$. Let $u_0$ be a vector on $\mathbb{R}^n$ uniformly distributed on the unit sphere. (We also know that $v_i$ is uniformly distributed on the unit sphere for $i=1,\dots, n$.)

Define $H_j(t)=u_t\cdot v_j$ for $j=1,\dots, n$ and time $t\ge 0$, solving the following ODE with initial value $H_j(0)$: $$ \frac{1}{2}H_j'(t)=\sum_{i=1}^n[(\lambda_i-\lambda_j)H_i^2(t)]H_j(t) $$

Assume that $$\sum_{i=1}^n H_i(t)=1, \mbox{ for } t\ge 0.$$ Note that $\sqrt{n}H_j(0)\to^d N(0,1)$, without loss of generality, assume that $H_j(0)>0$ for $j=1,\dots, n$.

Question: Fix $\epsilon>0$, define the hitting time $\tau_\epsilon=\inf_{t>0}\{H_1(t)\ge \epsilon\}$. I try to prove that $\tau_\epsilon\ge n^{2/3}$ with probability 1 as $n\to \infty$


Solving the above ODE $j=1,2,\dots, n$, we get $$ H_j(t):=\frac{1}{L}H_j(0)e^{-2\lambda_j t}, $$ where $L=\sqrt{\sum_{i=1}^n (H_i(0))^2 e^{-4\lambda_i t}}$.


Approach 1: I think the approach in the answer is still not rigorous enough. I still want to try to get the answer by the method of upper bound. I try to consider the difference between $H_1(t)-H_j(t)$, is it possible to get the result in this way?

\begin{align} H_1(t)-H_j(t)&=\frac{H_1(0)e^{-2\lambda_1 t}-H_j(0)e^{-2\lambda_j t}}{\sqrt{\sum_{i=1}^n H_i(0)^2 e^{-4\lambda_i t}}}\\ &=\frac{(H_1(0)-H_j(0)+H_j(0))e^{-2\lambda_1 t}-H_j(0)e^{-2\lambda_j t}}{\sqrt{\sum_{i=1}^n H_i(0)^2 e^{-4\lambda_i t}}}\\ &=\frac{(H_1(0)-H_j(0))e^{-2\lambda_1 t}+H_j(0)(e^{-2\lambda_1 t}-e^{-2\lambda_j t})}{\sqrt{\sum_{i=1}^n H_i(0)^2 e^{-4\lambda_i t}}}\\ &=\frac{(H_1(0)-H_j(0))e^{-2\lambda_1 t}+e^{-2\lambda_jt}H_j(0)(e^{2t(\lambda_j-\lambda_1)}-1)}{\sqrt{\sum_{i=1}^n H_i(0)^2 e^{-4\lambda_i t}}} \end{align}

Note that $\sqrt{n}(H_1(0)-H_j(0))$ are i.i.d. $N(0,1)$. Without loss of generality, assume that $H_1(0)>0$ and $H_1(0)-H_j(0)<0$, then $H_1(0)<H_j(0)$ for $j=2,\dots, N$.


Approach 2:

Since $$\sqrt{\sum_{i=1}^n H_i(0)^2 e^{-4\lambda_i t}}\ge \sqrt{H_1(0)^2 e^{-4\lambda_1 t}+H_2(0)^2 e^{-4\lambda_2 t}}$$, then we get as $t$ is large enough, $$ H_1(t)\le \left(1+(H_2(0)/H_1(0))^2 e^{-4t(\lambda_2-\lambda_1)}\right)^{-1/2}=1-\frac{1}{2}(H_2(0)/H_1(0))^2 e^{-4t(\lambda_2-\lambda_1)}+O(\delta^2), $$ where $\delta=e^{-4t(\lambda_2-\lambda_1)}$.

For $t\ge \tau_\epsilon$, we have $H_1(t)\ge \epsilon$. I am stuck on how to solve $$H_1(t)\ge \epsilon$$


Actually, I can show that $\tau_{\epsilon}^{(n-1)}:=\inf\{t\ge 0: H_{n-1}(t)\ge 0\}$ with order $O(n^{2/3})$.

Note that $$ H_{n-1}^2(t)=\frac{H_{n-1}^2(0)}{\sum_{i=1}^{n-2}H_i^2(0)e^{4t(\lambda_{n-1}-\lambda_i)}+H_{n-1}^2(0)+H_{n}^2(0)e^{4t(\lambda_{n-1}-\lambda_{n})}}. $$

By $e^{4t(\lambda_{n-1}-\lambda_{j})}\ge e^{4t(\lambda_{n-1}-\lambda_{n})}$ for $j=1,\dots, n-2$, we get $$ H_{n-1}^2(t)\le \frac{H_{n-1}^2(0)}{H_{n-1}^2(0)+(1-H_{n-1}^2(0))e^{4t(\lambda_{n-1}-\lambda_n)}}=\frac{1}{1+(H_{n-1}^{-2}(0)-1)e^{4t(\lambda_{n-1}-\lambda_n)}} $$ where using $\sum H_i^2(0)=1$.

For $t\ge \tau_{\epsilon}^{(n-1)}$, we have $H_{n-1}^2(t)\ge \epsilon^2$ $$ \tau_{\epsilon}^{(n-1)}\ge \frac{1}{4(\lambda_n-\lambda_{n-1})}\log\frac{H_{n-1}^{-2}(0)-1}{\epsilon^{-2}-1} $$ by the fact that $\lambda_n-\lambda_{n-1}=O(n^{-2/3})$.

Since $H_{n-1}(0)<\epsilon/2$ with high probability (with probability 1 as $n\to \infty$), then $$ \tau_{\epsilon}^{(n-1)}\ge n^{2/3} $$ with probability 1 as $n\to \infty$.


I do a simulation for $H_1(t)$ with same initial value $u_0$ with different $n$ from 200 to 2000:

enter image description here

And for another initial value $u_0$: enter image description here

$\endgroup$
6
  • 3
    $\begingroup$ this is basically the same question as the one you asked previously --- mathoverflow.net/q/432647/11260 --- best practice here is to improve a question by editing it, rather than start a new post. $\endgroup$ Nov 16, 2022 at 21:36
  • 1
    $\begingroup$ are you working with concrete $H_j(0)$? or just general ones that satisfy the conditions? I am guessing they also each depend on $n$, since you take limit that goes to Gaussian. $\endgroup$ Nov 16, 2022 at 22:10
  • 1
    $\begingroup$ @ThomasKojar I have define $H_j(0)$ for $j=1,\dots, n$ now. That is the dot product of two uniformly distributed vectors. $\endgroup$
    – Hermi
    Nov 17, 2022 at 5:26
  • $\begingroup$ @CarloBeenakker Sorry, I found a mistake on my upper bound of $H_1(t)$, I have edited it... Now, my upper bound does not work.. Do you know how to fix it? Thanks! $\endgroup$
    – Hermi
    Nov 20, 2022 at 7:24
  • 1
    $\begingroup$ Just a helpful suggestion: you are doing lots of edits in quick succession. May I suggest having a local draft of this and thinking for a bit when deciding how to change the question? And then giving yourself some time to think if you need more changes before making live changes here? Every edit bumps this up to the top of the front page, and the software is flagging the edit activity as unusual. $\endgroup$
    – David Roberts
    Nov 22, 2022 at 3:28

1 Answer 1

3
+50
$\begingroup$

By way of illustration, to get some insight, I plot $H_1(t)$ versus $t$ for a particular realization of the random matrix, with $n=1000$ [link to Mathematica notebook]

For any realisation with $H_1(0)>0$ one has the large-$t$ limit $$\lim_{t\rightarrow\infty}H_1(t)=\lim_{t\rightarrow\infty} \frac{1}{\sqrt{1+\sum_{i=2}^n[H_i(0)/H_1(0)]^2e^{-4(\lambda_i-\lambda_1)t}}}=1.$$

The function $H_1(t)$ rises from $H_1(0)$ to 1 in a time of order $t_n$. The deviation from 1 becomes exponentially small if $4(\lambda_2-\lambda_1)t\gg 1$, hence for times $$t\gtrsim t_n={\cal O}(n^{2/3}).$$ I have used that the first two eigenvalues have a spacing $\lambda_2-\lambda_1={\cal O}(n^{-2/3})$ (Tracy-Widom law). The other eigenvalues contribute to $H_1(t)$ with a larger decay rate $4(\lambda_i-\lambda_1)>4(\lambda_2-\lambda_1)$ for $i>2$, so we need not consider those for the estimate of $t_n$.

Now take $\epsilon$ fixed in the interval $(0,1)$. For large $n$ the initial value $H_1(0)\lesssim 1/\sqrt{n}$ is much less than $\epsilon$. The time $\tau_\epsilon$ it takes for $H_1(t)$ to rise up to $\epsilon\gg H_1(0)$ is some $\epsilon$-dependent fraction of $t_n$, so this hitting time grows with $n$ as $n^{2/3}$.

We have thus arrived at the scaling $\tau_\epsilon={\cal O}(n^{2/3})$ anticipated in the OP.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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