# finding the number of circles we get when randomly placing given patterns into a grid of squares

We have an 11$\times$11 table of squares (consist of 121 squares of dimension 1$\times$1). we have 3 tiles shown in the picture. Each tile has dimension 1$\times$1. we now randomly pick 3 tiles into the table. Let $N$ denote the total of number of circles we get in a random drawing. Compute expected value of $N$, mean of $N$ and standard deviation of $N$.

I think of an idea that we construct a $X$-$Y$ coordinate in accordance with the 11$\times$11 table, the only way to get a circle is to put the first tile in square $(x,y)$ and $(x+1,y-1)$ and put the third tile in square $(x+1,y+1)$ and $(x,y-1)$ for $0 \le x,y \le 11$. I want to construct a variable that takes on value 1 if this arrangement occurs and 0 if not, then construct what I want. But now I get stuck. Any help would be really appreciated. thanks

The image of the three tile patterns is below

-

Let $n_k$ be an indicator rv (Bernoulli, $p=1/81$) which takes the value 1 if the $2\times 2$ block $k$ forms a circle, 0 otherwise. The index $k$ runs over the $(L-1)^2=100$ blocks, where $L=11$ is the number of squares per side. Then, if $N$ is the number of circles, we have $N =\sum_k n_k$ and $E(n_k)=p$, hence

$$E(N) = (L-1)^2 \, p = \frac{100}{81} = 1.2345679$$

Further,

$$E(N^2) = E\left[\sum_k n_k\right]^2 = (L-1)^2 E(n_k^2) + \sum_{k \ne j} E(n_j n_k)$$

Now, $E(n_j n_k)=0$ if the blocks overlap at two squares; there are $2(L-2)(L-1)=180$ such pairs.

If the block pair operlaps diagonally, at one square, $E(n_j n_k) =1/3^7$; there are $(L-2)^2=81$ such pairs.

And $E(n_j n_k)= E(n_j)E(n_k)= p^2$ if the pair doesn't overlap: $(L-2)^{2}\,( {L}^{2}-2)= 9639$ pairs.

Then $E(N^2) = 74/27$ and $Var(N) = E(N^2) - E(N)^2=7982/6561=1.2165828$

Notice that is a little less that the variance obtained by the Binomial approximation suggested in Ross's answer ($1.2193263$), which was to be expected (the negative correlation tends to lower the variance of the sum).

-
Why is $E(n_jn_k)=0$ if the blocks overlap? Can't both blocks have circles if they overlap in exactly one square? – MJD May 9 '13 at 17:59
@MJD oops, you're right. – leonbloy May 9 '13 at 18:03
@MJD Fixed... I hope – leonbloy May 9 '13 at 18:37
@leonboy: thanks. in the journal, they randomly use computer to get this drawing and get 2 circles. they ask:"is 2 an unusual value for N? Explain" i personally think it's too high value but don't know how to give a reasoning for that – Chelsea May 9 '13 at 22:59
Well, you'd typically compute the mean and the standard deviation for that. I got $\mu=1.23$ and $\sigma=1.1$, the value 2 is less than one deviation apart from the mean, so one would say that it's not at all unusual. BTW, the distribution should be quite similar to a Poisson with $\lambda=1.23$ – leonbloy May 9 '13 at 23:28

A naive way to think of it is to say that each $2 \times 2$ block of squares has a chance of $\frac 1{3^4}=\frac 1{81}$ of hosting a circle. You have $100$ such blocks. You can use the binomial distribution to calculate the mean and standard deviation of the number of circles.

This pretends that the various squares are independent, which is not true. It should be very close, though, because the chance of a given block hosting a circle is low.

-
i once thought of this idea. 2x2 block of squares you mentioned is a combination of square 1 and 3. and we call "success" is the event that we get this combination. but as you said, it's not true. so i vie for a solid reasoning to solve this problem. btw thanks – Chelsea May 9 '13 at 17:08
That should be exact for the mean, right? – leonbloy May 9 '13 at 17:46
@leonbloy: I'm not sure. Note that if the block in the upper left has a circle, the block one small square to the right overlaps two of the squares and cannot have a circle. The one diagonally down is now guaranteed that one of its squares is right to make a circle. So I don't think the mean will be exact. – Ross Millikan May 9 '13 at 18:03
I was thinking on the linearity of the mean, using an indicator function, see my answer. – leonbloy May 9 '13 at 18:30