I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says
Consider a square $n \times n$ array of lights (see Figure 5.1). There is one switch corresponding to each row and each column (i.e., $2n$ switches). Throwing a switch changes the state of all the lights in the corresponding row or column. We now consider the problem of setting the switches so as to maximize the number of lights that are on, starting from an arbitrary initial on/off configuration of the lights.
Note first that, if we set all the switches independently and uniformly at random, we would expect $\mathbb{E}(|\#\mathrm{ON}-\#\mathrm{OFF}|)\sim O(\sqrt(n^{2}))=O(n)$ Hence we would expect to be able to achieve about $\frac{n^{2}}{2}+O(n)$ lights on. (Note that we can always ensure that at least half are on simply by flipping all the switches if necessary.)
Questions: Firstly do they mean each switch is switched on or not with probability $\frac{1}{2}$ or we can flick one switch which is picked uniformly at random?
Secondly I don't see how the intuition in $\mathbb{E}(|\#\mathrm{ON}-\#\mathrm{OFF}|)\sim O(\sqrt(n^{2}))=O(n)$. Could someone help explain this?
Thanks.
The idea is to imagine each light as an independent coin flip. The standard deviation in the number of heads in $k$ flips is $\frac 12 \sqrt k$ When you take the difference between the heads and tails you double it because if one is high the other is low, so the $\frac 12$ goes away, and $k=n^2$ so we expect the standard deviation in the difference to be about $n$.