Do you have an idea how I could model the following process somehow as a sum of independent indicator random variables?
I have given a grid of size $n \times n$ for $n \rightarrow \infty$.
Now I color each point of this grid uniformly at random with one out of $k$ colors, where $k=\mathcal{O}(1)$.
I am interested in the probability that none of the $3 \times 3$-subgrids in this grid are monochromatic (monochromatic=all 9 points have the same color) and should show this probability is at most $e^{- \Omega(n^2)}$.
My task is explicitly to model this such that I can use Chernoff bounds. Chernoff bounds, in the context we had it, can be applied if we have a sum $X:=\sum_{i=1}^m X_i$ of independent indicator random variables $X_i \sim Be(p_i)$.
My problem is that clearly the different $3 \times 3$ grids are not independent, so the easy approach to state $X=\sum_{s \in S} X_s$ where $S$ is the set of all $3\times 3$ subgrids and $X_s$ is $1$ if $s$ is a monochromatic grid, and calculate $P[X=0]$ does not work.
Would be very happy about any hint. Thank you very much!