For two vectors in $\{\pm1\}^n$, take the probability that the ratio of their overlap and $\sqrt{n}$ is less than some integer $M$ then take its limit

Question

Take two sign vectors $\sigma, \widehat{\sigma} \in \{ \pm 1 \}^n$ where each $\sigma_k$ and each $\widehat{\sigma_k}$ are equally likely to be +1 or -1 and independent of the other $\sigma_j$'s and $\widehat{\sigma_j}$'s respectively.

Let $|\langle\widehat{\sigma}, \sigma\rangle|$ be the number of entries at which the corresponding signs are the same.

How can one show that for every $\epsilon>0$, there exists $M_{\epsilon}$ and $N$ such that $Prob\left(|\langle\widehat{\sigma}, \sigma\rangle| \leq M_{\epsilon}\sqrt{n}\right)>1-\epsilon \ $ for all $\ n > N$?

I'm learning statistical inference on graphs by myself and this came up. I've never taken anything more than a first course on undergrad probability theory, hence I don't know how to start.

Answer 1

Approach $1$ (More General): To flesh out Sherwin Lott's hint, define the indicator random variables $X_1, \cdots, X_n$, where $X_i$ is the indicator that the $i$th entries of $\sigma$ and $\hat{\sigma}$ match. Clearly, all the $X_i$'s are independent and identically distributed, taking on value $0$ half the time and taking on the value $1$ half the time. The central limit theorem asserts that for any sequence of i.i.d. random variables, $X_1, \cdots, X_n$ with mean $\mu$ and finite variance $\sigma^2$, $$\lim_{n \to \infty} \frac{X_1 + \cdots + X_n}{n} \to \mathcal{N}\left(\mu, \frac{\sigma^2} {n}\right)$$ and hence $X_1 + \cdots + X_n$ tends in distribution to $\mathcal{N}(n \mu, n \cdot \sigma^2)$. You are interested in the probability that the random variable on the right-hand side is more than its mean by more than some amount. Note that for any $k$, $$\mathbb{P}(\mathcal{N}(n \mu, n \cdot \sigma^2) - n \mu > k) = \mathbb{P}\left(Z > \frac{k}{\sigma \sqrt{n}}\right) = \int_t^\infty \frac{1}{\sqrt{2 \pi}} e^{-x^2 / 2} < \frac{1}{\sqrt{2\pi} t} e^{-t^2 / 2}$$ where $Z$ is a standard normal and $t = \frac{k}{\sigma \sqrt{n}}$. (To derive the last inequality, you can check out this link. It is a standard bound on the CDF of the normal distribution.) Plugging in our value for $t$, it can be seen that the right-hand side is less than $\epsilon$ whenever, say $$t > T_\epsilon = \begin{cases} \sqrt{- 2 \ln( \sqrt{2 \pi} \epsilon)}, & \epsilon \leq 1 / \sqrt{2 \pi} \\ 1, &\epsilon > 1 / \sqrt{2 \pi}\end{cases}$$ (You can verify it for yourself.) So we have an explicit construction of $M_\epsilon$ now: we can choose $$M_\epsilon = \sigma t = \begin{cases} \frac 12 \sqrt{- 2 \ln( \sqrt{2 \pi} \epsilon)}, & \epsilon \leq 1 / \sqrt{2 \pi} \\ \frac 12, &\epsilon > 1 / \sqrt{2 \pi}\end{cases}$$ as $\sigma = 1/2$ for all the $X_i$. It will then follow from our work above that $$\mathbb{P}(\mathcal{N}(n \mu, n \cdot \sigma^2) - n \mu > M_\epsilon \sqrt n) = \mathbb{P}\left(Z > \frac{M_\epsilon}{\sigma}\right) < \epsilon$$ and hence $\mathbb{P}(\mathcal{N}(n \mu, n \cdot \sigma^2) - n \mu \leq M_\epsilon \sqrt n) > 1 - \epsilon$ as $n \to \infty$. $\square$

Approach 2 (Less General): This approach will rely on the fact that the random variable $S = X_1 + \cdots + X_n$ has a binomial distribution with number of trials $n$ and probability of success $1/2$. The Hoeffding Inequalities provide similar bound, stating that $$\mathbb{P}(\text{Binom}(n, p) - np > \delta n) \leq e^{-2 \delta^2 n}$$ Choosing say, $\delta = \sqrt{\frac{-\ln(\epsilon / 2)}{2n}}$ yields the inequality $$\mathbb{P}\left(\text{Binom}(n, p) - np > \sqrt{\frac{-\ln(\epsilon / 2)}{2}} \sqrt{n}\right) \leq \epsilon / 2 < \epsilon$$ So choosing $M_\epsilon = \sqrt{\frac{-\ln(\epsilon / 2)}{2}}$ forces this inequality to be true for all $n$. $\square$

Remarks:

1. The Hoeffding Inequality can be proved without referencing the CLT, so these are actually two independent ways of obtaining the same result.

2. The crucial idea here is that the probability that a normal-like random variable (such as a binomial distribution for large $n$) deviates from its mean by more than $k$ standard deviations goes like $e^{-c k^2}$ (plus some smaller-order corrections) for some constant $c > 0$. This is exponentially small, and is what implies that for any constant $\epsilon$, there exists some $M_\epsilon$ such that deviating from the mean by more than $M_\epsilon$ standard deviations has probability less than $\epsilon$.