Proof of the lower bound

Our proof of the lower bound for the clique number of random geometric graphs (see Theorem 1 in the previous post) is a little bit contrived, but it might actually have some value. Our approach can be described as follows. Suppose that our goal is to study some property ${P}$ of some random variable ${X}$ . (Here ${X=G_{n,d}}$ and ${P}$ is some statement on ${\omega(G_{n,d})}$ .) Then you can try to apply the following recipe:

Set up a statistical hypothesis testing problem where the random variable ${X}$ arises naturally as a ‘good’ test.
Study the type I and type II error of this test, assuming that the property ${P}$ is true.
Derive a statistical lower bound on the risk (i.e., the sum of the type I and type II error) of any test.
Conclude that if ${P}$ was true, the test based on ${X}$ would beat the statistical lower bound, and thus ${P}$ is false.

There are other ways to phrase the above recipe. I used here the language of statistics, but I could have explained everything in terms of distances between distributions. Let us see now how we can apply the steps described above for our particular problem.

Step 1. Let ${Z^1, \hdots, Z^d \in {\mathbb R}^n}$ be i.i.d. random variables. The two hypothesis on the distribution of this sequence are the following:

$H_0$ : $Z^1 \sim \mathcal{N}(0,I_n)$ , v.s. $H_1$ : $Z^1 \sim \mathcal{N}(0,A_S)$ , for some $S \subset [n]$ with $|S|=k$ ,

where

$\displaystyle (A_S)_{i,j} = \left\{\begin{array}{ll} 1, & i = j, \\ \rho, & i \neq j, \text{ with } i, j \in S, \\ 0, & \text{ otherwise}. \end{array}\right. \ \ \ \ \$

In words, under ${H_0}$ each coordinate of ${Z^t}$ is an independent ${\mathcal{N}(0,1)}$ , while under ${H_1}$ there exists a subset of ${k}$ coordinates which have a covariance of ${\rho}$ between each other. Now let us consider ${Z_i=(Z^1_i, \hdots, Z^d_i) \in {\mathbb R}^d, i \in [n]}$ be the vector of ${i^{th}}$ coordinates of the sequence of observations ${Z^1, \hdots, Z^n}$ , and let ${X_i = \frac{Z_i}{\|Z_i\|}}$ . Under ${H_0}$ we would assume the vectors ${X_i}$ to be uniformly distributed on ${\mathbb{S}^{d-1}}$ , while under ${H_1}$ we would expect a ‘cluster’ of size (of order) ${k}$ to appear (if ${\rho}$ is ‘large enough’). Thus a natural test is to build the random geometric graph ${G}$ corresponding to the vectors ${X_1, \hdots, X_n}$ , compute its clique number ${\omega(G)}$ , and reject the null hypothesis if ${\omega(G)}$ is ‘too large’.

From now on we shall assume that

$\displaystyle k := \text{Median}(\omega(G_{n,d})) ,$

and that the test reject if ${\omega(G) \geq k}$ .

Step 2. By definition the type I error of the test is smaller than ${1/2}$ . Let us now consider the type II error:

$\displaystyle \mathop{\mathbb P}_1(\omega(G) < k) \leq \mathop{\mathbb P}_1(\exists (i,j) \in S^2 \; \text{s.t.} \; X_i^{\top} X_j < 0) \leq {k \choose 2} \mathop{\mathbb P}_1(Z_i^{\top} Z_j < 0) ,$

where ${i, j}$ in the last probability are arbitrary points in ${S}$ . Now using Chernoff’s bound, and the moment generating function of two correlated one-dimensional Gaussian random variables, it is easy to check (see Lemma 10 in Devroye et al.) that

$\displaystyle \mathop{\mathbb P}_1(X_i^{\top} X_j < 0) \leq \exp(- d \rho^2 / 10 ).$

In particular we conclude that if ${k^2 \exp(- d \rho^2 / 10 ) \leq 1/4}$ then the risk of our test is smaller than ${3/4}$ .

Step 3. Using (almost) standard techniques (see Theorem 2.1. here, and Theorem 1 here), one can show that if ${\rho \leq c \frac{\log (c n / k^2)}{d}}$ (where ${c}$ is a positive numerical constant), then there does not exist a test with a risk smaller than ${3/4}$ .

Step 4. If one take ${\rho}$ of order ${\log(n) / d}$ , then Step 3 shows that there are no test with risk smaller than ${3/4}$ (note that we can assume that ${k = o(\sqrt{n})}$ , otherwise our theorem is already proved). Plugging this value of ${\rho}$ in the result of Step 2, we see that we must necessarily have ${k^2 \exp(- \log^2(n) / (10 d) ) > 1/4}$ , which gives exactly the lower bound we were trying to prove.

At this point we don’t know if the above ‘statistical method’ can be applied successfully to other (difficult) problems, so an interesting direction for further research would be to find such problems!

This post concludes my first sequence of posts on random graphs. The next sequence is going to be much longer, and it will be focused on optimization (more on that in the next post).

Proof of the lower bound

Leave a reply

Archives

Categories

Recent Posts

Subscribe to Blog via Email

Meta

Blogroll