# Poisson Approximation Problem involving putting balls into boxes

I am working on a Poisson Approximation problem, but I'm stuck on essentially the converting of the word problem over to the probability problem.

Here is the problem:

Consider a single row of $n$ boxes. Balls are placed, one at a time, into uniformly chosen empty boxes. For example, the first ball is placed uniformly among all possible boxes, while the second ball is placed uniformly at random from the boxes not containing the first ball, ans so on. Let $N_{n,k}$ be the number of adjacent pairs of occupied boxes after k balls are placed, and let $T_n=\inf \{k:N_{n,k}>0\}$ be the first time (measured in the number of balls placed) that there is an adjacent pair of occupied boxes.

a) Compute the distribution of $T_n$ exactly. (Hint: If no pair among $k$ balls is adjacent, then $k-1$ of these balls effectively occupy two boxes, and this effectively reduces the number of boxes by $k-1$.)

b) Find a sequence $k_n$ so that $N_{n,k_n}$ converges in distribution to a Poisson random variable.

c) Find a sequence $a_n$ so that $T_n/a_n$ converges in distribution.

I don't really see how to convert the word problem into a probability problem and could use some help.

UPDATE:

So far I have the following:

a) Using the hint we have that $P(T_n \leq k)=1-\frac{{n-(k-1) \choose k}}{{n \choose k}}$. This is because given $k$ balls there are ${n \choose k}$ ways to put $k$ balls into $n$ boxes, and there are ${n-(k-1) \choose k}$ ways to put in $k$ balls so that there are no adjacent balls.

b) I want to try and measure the total variation distance between $N_{n,k}$ and a Poisson random variable. To do this I have the following approach:

-There are $n-1$ adjacent pairs of boxes.

-Let $\Gamma=\left\lbrace i \right\rbrace_{i=1}^{n-1}$ be the collection of adjacent pairs of boxes.

-Let $I_i=1_{\left\lbrace \text{pair } i \text{ is full} \right\rbrace}.$ Then $N_{n,k}=\sum_{i=1}^{n-1} I_i.$

-For all $i$ $p_i=E(I_i)={n-2 \choose k-2}/{n \choose k},$ and $\lambda=E(N_{n,k})=(n-1)p_1$.

Let $$J_{ji} = \begin{cases} I_j, & \mbox{if } I_i=1 \\ 1_{\left\lbrace \text{pair } j \text{ is full after filling in pair } i \text{ following the below procedure}\right\rbrace}, & \mbox{if } I_i=0 \end{cases}.$$

Here is the procedure for the coupling. Given an arrangement of balls look at the adjacent pair $i$. If $I_i=1$ do nothing. Else randomly choose 2 balls and put them into pair $i$. Then place all of the remaining balls into uniformly chosen empty boxes from the remaining $n-2$ boxes.

The resulting arrangement is still uniform and so our proposed coupling will satisfy that for each $i\in\Gamma$, $(I_i)_{j\neq i}$ and $(J_{ji})_{j\neq i}$ are coupled so that $(J_{ji})_{j\neq i} =_{\text{in distribution}} (I_j)_{j\neq i}|I_i =1.$

Now when $|i-j|\geq 2, \ J_{ji}\leq I_j$ because once we fix two balls there are less balls to fill up the remaining boxes. Now using a corollary to this theorem:

Let $\{I_i : i\in \Gamma\}$ be indicator random variables, $W=\sum_{i\in\Gamma} I_i, \ p_i=E(I_i), \ \lambda=E(W)=\sum_{i\in\Gamma} p_i,$ and assume that a coupling like the above exists then: $$d_{TV}(W,P_\lambda ) \leq \min(1,\lambda^{-1})\left[ \sum_{i\in\Gamma}\left( p_i^2 + p_i \sum_{j \in \Gamma-\{i\}} E(|J_{ji}-I_j|) \right) \right],$$ where $P_\lambda$ is a poisson($\lambda$) random variable.

I get $$d_{TV}(N_{n,k},P_\lambda)\leq \min(1,\lambda^{-1})\left[ \lambda^2 - \sum_{i,j \ |i-j|\geq 2} E(I_i I_j) + \sum_{i,j, \ |i-j|<2, \ i\neq j} (2p_ip_j +E(I_i I_j)) \right]$$

Where I have that $E(I_iI_j)={n-4 \choose k-4}/{n \choose k}$ for $|i-j|\geq 2,$ and $E(I_i I_j)={n-3 \choose k-3}/{n \choose k}$ for $|i-j|<2, i\neq j$.

So I get: $$d_{TV}(N_{n,k},P_\lambda)\leq (n+3)\frac{{n-2 \choose k-2}}{{n \choose k}} - \frac{(n-3){n-4 \choose k-4}}{{n-2 \choose k-2}} + \frac{{n-3 \choose k-3}}{{n-2 \choose k-2}}$$ $$=\frac{(n+3)k(k-1)}{n(n-1)}-\frac{(n-3)(k-2)(k-3)}{(n-2)(n-3)}+\frac{k-2}{n-2}$$ If this is correct, I can't seem to find an appropriate $k_n$ so that the final portion goes to $0$ as $n\rightarrow\infty$.

c) I don't have any idea how to solve this question.

Thank you for any assistance.

• You can do (a) with a counting method. There are ${n \choose k}$ ways of placing $k$ balls in $n$ boxes (no more than one each). Using the hint there are ${ n -(k-1) \choose k}$ ways of placing $k$ balls in $n$ boxes (no more than one each and none adjacent). So you can find $P(T_n \gt k)$ – Henry Nov 24 '15 at 8:34

First of all, \begin{equation*} \lambda_{n,k}= \mathbb{E}(N_{n,k})= (n-1)\frac{k(k-1)}{n(n-1)} = \frac{k^{2}}{n} - \frac{k}{n} \end{equation*} and we want $\lambda_{n,k}\rightarrow c>0$ as $n\rightarrow \infty$. So we should choose $k = \sqrt{cn}$ (rounding omitted). Then \begin{equation*} \lambda_{n,k}=c+ O(n^{-1/2}). \end{equation*}
Second, your independent coupling is not negatively related to the original indicators since re-swapping $n-2$ balls uniformly at random could get $j$th pair occupied or may as well destroy an already occupied pair. Instead consider the following coupling: \begin{equation*} J_{ji} = \begin{cases} I_{j} & \text{if $I_{i}=1$} \\ 1_{\{ \text{pair $j$ is full after filling in pair $i$ with one or two balls chosen u.a.r. from balls not in pair $i$ } \}} & \text{otherwise} \end{cases} \end{equation*} It is easy to see that this coupling has the correct conditional distribution, and also we have negative relation ($J_{ji}\le I_{j}$ for $j\ne i$) to the original indicators since we could only destroy an already occupied pair.
\begin{equation*} d_{TV}(N_{n,k},P_{\lambda_{n,k}}) = O(n^{-1/2}). \end{equation*} Since $\lambda_{n,k} = c + O(n^{-1/2})$, we also have \begin{equation*} d_{TV}(P_{\lambda_{n,k}},P_{c}) = O(n^{-1/2}), \end{equation*} so we conclude $N_{n,\sqrt{cn}} \Rightarrow P_{c}\sim \text{Poisson}(c)$ as $n\rightarrow \infty$.
Finally, note that $\{T_{n}>k\} = \{N_{n,k}=0\}$, so \begin{equation*} \mathbb{P}(T_{n}>\sqrt{cn}) \rightarrow e^{-c} \end{equation*} as $n\rightarrow \infty$. This implies \begin{equation*} \mathbb{P}(T_{n}/\sqrt{n}> t) \rightarrow e^{-t^{2}} \end{equation*} as $n\rightarrow \infty$, so we see that $\frac{T_{n}}{\sqrt{n}}\Rightarrow \sqrt{X}$ where $X\sim \text{Exp}(1)$.