Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

You are given a rectangular $n_1\times n_2$ grid with one light bulb $b_i$ at every node. Each bulb is on or off with probability $p$ and $1-p$, respectively, and furthermore you know that exactly $m$ bulbs are on. Equip the grid with the Manhattan metric $d$, and look at the set of distances between distinct bulbs which are on:

$$S:=\{d(b_i,b_j): i\neq j, b_i \textrm{ and } b_j \textrm{ are on}\}.$$

To understand how close two lit bulbs should be, I would like to compute the expected value of the random variable $X:=\min S$ (in terms of $n_1,n_2,p$ and $m$). Any hints on how to start thinking about this problem?

Thank you.

share|improve this question
If you demand that exactly $m$ bulbs are on, are you restricted to considering the case $p=m/(n_1n_2)$? – Chris Taylor Dec 6 '11 at 6:38
The value of $p$ is irrelevant. Since every configuration with $m$ bulbs on is equiprobable, one chooses one such configuration uniformly at random. – Did Dec 6 '11 at 6:44
Note that for each $n_1,n_2$ there is $m^*$ such that $\mathsf E X = 1$ for all $m\geq m^*$. – Ilya Dec 6 '11 at 7:48
1  
It looks to me like a very hard problem. I would be surprised if there was a closed-form solution. – Robert Israel Dec 6 '11 at 7:50
@Robert: Can you give me some insight on why this should be such a hard problem? – user17240 Dec 6 '11 at 21:44
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.