1
$\begingroup$

Let $G$ be a symmetric Gaussian random matrix with iid $E[G_{ij}]=0$ and $E[G_{ij}^2]=\frac{1}{n}$, and ordering its eigenvalues $\lambda_1\le \lambda_2\le \dots \le \lambda_n$ corresponding eigenvectors $v_1,\dots, v_n$. Define $X_t=\{X^i_t\}$ is a vector on $R^n$ for time $t\ge 0$ and $X_0$ is distributed uniformly on the unit sphere. Let $h(t)= X_t\cdot v_1$.

Let $T_\epsilon:=inf_{t>0}\{h(t)\ge \epsilon\}$. Assume that $$ h(t)\ge h(0)e^{2(\lambda_2-\lambda_1)t}\ge h(0)e^{2\delta t} $$ where $\delta=\min\{\lambda_i-\lambda_j\}$ is the smallest gap.

I try to find the upper bound of $T_\epsilon$ with high probability $1-Ce^{-c n}$ (or something like that).

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ the issue here is that $h(0)$ could be much smaller than $n^{-1/2}$ with large probability; the Gaussian distribution of $h(0)$ has a peak at 0 of height $n^{1/2}$, so $h(0)$ can be close to 0 with large probability; this produces an increase of $T_\epsilon$, beyond the $n^{2/3}\log n$ bound you write down; I have tried to work that out in the answer box. $\endgroup$ Commented Oct 17, 2022 at 18:12
  • $\begingroup$ @CarloBeenakker Thank you! Do you mean $P(|h(0)|<\alpha)\ge e^{-\alpha^2/2}$? I am not sure what do you mean "with probability $\alpha\sqrt{n}$"? Does it mean $P(|h(0)|<\alpha)=\alpha \sqrt{n}$? $\endgroup$ Commented Oct 17, 2022 at 18:41
  • $\begingroup$ yes: $P(|h(0)|<\alpha)=\alpha \sqrt{n}$ --- you're sampling from the peak of the gaussian, so the probability is large, not small. $\endgroup$ Commented Oct 17, 2022 at 18:45
  • $\begingroup$ @CarloBeenakker Can you explain why is $P(|h(0)|<\alpha)=\alpha \sqrt{n}$ true? $\endgroup$ Commented Oct 19, 2022 at 14:17
  • $\begingroup$ this estimate holds for $\alpha\ll \sqrt n$, since$\int_{-\alpha}^\alpha (n/2\pi)^{1/2}e^{-nx^2/2}\,dx=\text{Erf}\,(\tfrac{1}{2}\alpha\sqrt{n})=\sqrt{2/\pi}\alpha\sqrt n+{\cal O}(\alpha^2)$ --- the factor $\sqrt{2/\pi}$ is irrelevant here. $\endgroup$ Commented Oct 19, 2022 at 14:43

1 Answer 1

Reset to default
1
+50
$\begingroup$

I don't think this upper bound holds.

Notice that the probability distribution of $h(0)$ is a Gaussian of mean 0 and width $1/\sqrt n$, so the probability that $|h(0)|<\alpha$ is $\alpha\sqrt n$ for $0<\alpha<1/\sqrt n$.

Since $\lambda_2-\lambda_1\simeq n^{-2/3}$, the hitting time $T_\epsilon$ for $h(0)=\alpha$ is $$T_\epsilon\lesssim n^{2/3}\log(\epsilon/\alpha).$$ Choose $\alpha<e^{-\sqrt n}$, then $T_\epsilon$ can be larger than $n^{1/2}n^{2/3}>n^{2/3}\log n$ with probability $\sqrt{n}e^{-\sqrt n}$, so a larger probability than the $e^{-n}$ conjectured in the OP.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Also, since $\sqrt{n} h(0)\to N(0, 1)$ weakly as $n\to \infty$, then $h(0)=O_p(n^{-1/2})$. Then $T_\epsilon \le C n^{2/3}\log n$ with probability 1 as $n\to \infty$. Does it make sense? $\endgroup$ Commented Oct 17, 2022 at 17:59
  • $\begingroup$ my point is that your upper bound $n^{2/3}\log n$ is too small; in the example I gave the upper bound is $n^{1/2}n^{2/3}$, which greatly exceeds your upper bound when $n\gg 1$. $\endgroup$ Commented Oct 17, 2022 at 18:09
  • $\begingroup$ Oh, sorry. I see your point that $P(T_\epsilon\le n)=1-\sqrt{n}e^{-\sqrt{n}}$. $\endgroup$ Commented Oct 17, 2022 at 18:13
  • $\begingroup$ How about if we change the initial distribution of $X_0$ to be uniformly distributed on the sphere with radius $\sqrt{n}$? In this case, $h(0)$ is a Gaussian of mean 0 and width 1. Then $|h(0)|\le \alpha$ with probability $\alpha$ for $0<\alpha<1$. So it seems that we can choose $\alpha=n^{-1/2}$? $\endgroup$ Commented Oct 17, 2022 at 18:19
  • $\begingroup$ a larger sphere will not help, the problem is that $h(0)$ can become very close to zero (by choosing the vector $X_0$ perpendicular to the vector $v_1$). $\endgroup$ Commented Oct 17, 2022 at 18:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.