I am having some trouble with the following question:
We define an undirected graph:
$$ V = \{(i,j) : 0 \le i,j \le n \} $$
And the vertex $(i,j)$ is connected to the vertices: $$ (i-1,j), (i+1,j), (i,j+1), (j,j-1)$$ If they are in the graph. Note that in the graph we have $n^2$ squares of the form: $$ \{(i,j), (i,j+1), (i+1,j). (i+1,j+1)\} $$ For $ 0 \le i,j \le n-1 $.
We delete every edge from the graph independently and in a probabilty of $\frac{1}{2}$.
Let X be the number of squares that survived , i.e. the number of squares that all of the edges in it survived.
Use Hoeffding's bound to find a bound for:
$$ Pr(X > \frac{n^2}{16} + \alpha n) $$
So I have the direction to solve this but theres a stage I got stuck in.
For every $(i,j)$ I can define $X_{ij}$ the variables that the square built by the vertices $(i,j)$ survived. That is, $X_{ij} $~$ Ber(\frac{1}{16})$ Because the question says we have $n^2$ such squares, I get:
$ X = \sum_{ij}X_{ij} $ and therefore $ \mathbb{E}(X) = \frac{n^2}{16} $.
However $X_{ij}$ are not independent and their expectancy is not 0. We can define:
$ Z_{ij} = X_{ij} - \frac{1}{16}$
Now $\mathbb{E}(Z_{ij}) = 0 $ and $ Z \in \{-\frac{1}{16}, \frac{15}{16} \} \subseteq [-1, 1] $.
Now in order to use Hoeffding whats left is to look and $Z_{ij}$ in a way such that they are independent, and somehow to make the sum of them, $S$, a sum of two sums $ S = S_1 + S_2 $ such that each one is sum of independent random variables. Then I'll have something like:
$$ Pr(X > \frac{n^2}{16} + \alpha n) \leq Pr(X \geq \frac{n^2}{16} + \alpha n) = Pr(S \geq \alpha n) =Pr(S1+S2 \geq \alpha n) = Pr((S1 \geq \alpha n / 2) \cup(S2 \geq \alpha n / 2)) \leq Pr(S1 \geq \alpha n / 2) + Pr(S2 \geq \alpha n / 2) $$
Where the last inequality is from union bound,and finally I can use Hoeffding on each one of the elements in the final expression. So what I dont get how to do is the how to look at them independently? I tried figuring something out along the lines of even and odd vertices but it got me no where..
Thanks in advance..
Take $S_1$ to be the sum of those $Z_{ij}$ where $i+j$ is odd; take $S_2$ to be the sum of those $Z_{ij}$ where $i+j$ is even.
Effectively, this corresponds to a "checkerboard coloring" of the squares in the graph. A square where $i+j$ is odd is adjacent to $4$ or fewer squares where $i+j$ is even, and vice versa. The variables $Z_{ij}$ are independent if the squares share no edges, so $S_1$ and $S_2$ are both sums of independent random variables.
A nitpick in your work: the equation $$ \Pr(S_1+S_2 \geq \alpha n) = \Pr((S_1 \geq \alpha n / 2) \cup(S_2 \geq \alpha n / 2)) $$ is false. It's possible for the sum $S_1 + S_2$ to exceed $\alpha n$ if, for example, $S_1$ is small but $S_2$ is very large. However, the inequality going in the right direction still holds, since if $S_1 \geq \alpha n/2$ and $S_2 \geq \alpha n/2$, then certainly $S_1 + S_2 \geq \alpha n$.
Finally, although it's nice to be clever and find this decomposition into a sum of independent variables, we can get a similar bound just by using a different inequality. The sum of all the $X_{ij}$ is $2$-Lipschitz in the edges of the random graph: changing whether an edge is present or not can change the value of the sum by at most $2$. By applying McDiarmid's inequality, we get $$ \Pr\left[X > \frac{n^2}{16} + \alpha n\right] \le \exp\left(-\frac{2(\alpha n)^2}{8n^2}\right) = \exp\left(-\alpha^2/4\right) $$ which is a lot like the bound you get from Hoeffding. (Possibly with a different constant inside the exponent, I haven't checked.)