N balls are sequentially and randomly allocated into M bins arranged in a circle. If a bin receives a ball, its left and right bins cannot receive any ball and are always set to be empty (new coming balls are discarded). What is the expected number of occupied bins at last?
From my simulation of N=M=100, the expected number is 36, but I want to know if it can be formulated mathematically. When N=M=4, simulation gives a value around 1.576.
Background: This is a quantitative interview question I am trying to solve. This question is an extension of the original balls-into-bins problem, which adds the dependency to the neighbour boxes by introducing a special constraint.
Additional Explanation: The original balls-into-bins question only says N balls are randomly allocated into M bins. Please calculate the expected number of non-empty bins. The answer is $$ M\left (1-\left(\frac{M-1}{M}\right)^N \right ) $$
Note: (as hinted by Henry) The solution in its current form only gives a lower bound.
Denote by $A_i$ the Bernoulli variable, which is equal to one if $i$-th bin is non-empty after throwing $N$ balls. Then, the expected value of the total number of non-empty bins $A$ is equal to $$ \mathbb{E}[A] = \sum_{i=1}^M \mathbb{E}[A_i]. $$ Since the $A_i$'s are Bernoulli variables, their expected value is $\mathbb{E}[A_i] = P(A_i = 1)$. Since $A_i$ is equal to one if it is selected at some $j$-th throw and none of its neighbors were selected before, we have \begin{align*} P(A_i=1) \geq \sum_{j=1}^N \frac{1}{M} \left(\frac{M-3}{M}\right)^{j-1} = \frac1M \frac{1-(1-(3/M))^N}{3/M} = \frac{1-(1-(3/M))^N}{3}. \end{align*} Note that this is only a lower bound, since the neighbors might be selected, but not filled, if one of their neighbors has been selected before. And thus $$ \mathbb{E}[A] \geq M \frac{1-(1-(3/M))^N}{3} $$ You can either compute this exactly or approximate the numerator for $M=N=100$ with $1-\mathrm{e}^{-3}$, which gives $\mathbb{E}[A] \geq 31.7$.