Problem 1: Random sums

Show there is a positive number $c > 0$ such that the following holds. For any $n$ real numbers $a_1,a_2,\ldots,a_n$ satisfying $a_1^2+a_2^2+\cdots+a_n^2=1$, if $\sigma_1,\sigma_2,\ldots,\sigma_n \in \{-1,1\}$ are i.i.d. uniformly random signs, then

$$\Pr\left[\left|\sum_{i=1}^n \sigma_i a_i\right| \leq 1\right] \geq c\,.$$

[Hint: Consider the case $\max \{a_1^2,\ldots,a_n^2\} \geq 1/2$ separately.]

Problem 2: Sensor deployment

Suppose you are designing the sensor deployment system for SpaceX’s Mars exploration mission. In order to search for habitable land, you will deploy sensor packets from the atmosphere. Each packet is designed to disperse $N$ sensors uniformly over one square kilometer. (So you can imagine that the $N$ sensors are placed uniformly and independently at random in the unit square $[0,1]^2$.)

The sensors will communicate with each other via a mesh network, but to keep energy costs down, it’s important that every sensor communicates with a very small number of other sensors. There is a parameter $k$ such that every sensor can send messages to the $k$ closest sensors (in Euclidean distance; you may assume that the sensors are deployed on flat ground).

You can think of the resulting directed graph $G$: The vertices are sensors and there is an edge $(u,v)$ between two sensors $u$ and $v$ if $v$ is one of the $k$ closest sensors to $u$. In order for the mesh network to be intact, it should be that $G$ is strongly connected (in other words, between every pair of sensors, there should be a directed path in $G$).

(a) Prove there is a constant $c$ such that if $k \geq c \log N$, then

$$\Pr[G \textrm{ strongly connected}] \to 1 \quad \textrm{as} \quad N \to \infty$$

(b) Prove there is a constant $c' > 0$ such that if $k < c' \log N$, then

$$\Pr[G \textrm{ strongly connected}] \to 0 \quad \textrm{as} \quad N \to \infty$$

(c) [Bonus]: Establish a sharper threshold. Prove that there is a constant $c_0$ such that if $k = \lceil c \log N\rceil$ and

$$\begin{align*} c > c_0 &\implies \Pr[G \textrm{ strongly connected}] \to 1 \quad \textrm{as} \quad N \to \infty \\ c < c_0 &\implies \Pr[G \textrm{ strongly connected}] \to 0 \quad \textrm{as} \quad N \to \infty \end{align*}$$