9
$\begingroup$

Background

The motivtion for this question comes from observations made by a colleague while he was marking homework and recording the marks this year.

His procedure for recording the marks is as follows. The homework is placed into his folder by students before the deadline, (presumably) in a 'random' order. Once the deadline passes, he collects the folder, and starts marking. He takes the first script from the folder, marks it and records the mark on the mark-sheet. Then he takes the next script, marks it and records it. And so on...

Whilst doing this, he noticed that one would surprisingly quickly have entered marks for two consecutive students on the list. For example, in a class of 20 students, it only took 4 or 5 scripts on average.

This prompted some questions from him on the distribution of this number:

  • What is the expectation and standard deviation?
  • Is there an explicit formula for any class size? (Or a recurrence relation, or any other good way to compute it?)
  • How does it behave asymptotically for large classes?

Setup of Problem

Let's phrase the problem a bit more precisely, so I can explain what we've succeeded in doing.

Suppose you have a line of $ N $ boxes, all initially unfilled. Select uniformly at random an unfilled box, and fill it in. Repeat this until two consecutive boxes have been filled in, then stop. (The boxes form a line, and do not wrap around, so the two end boxes are not considered consecutive.) The value of the discrete random variable $ X_N $ is then the number of filled in boxes.

In particular we are now looking for

  • Explicit formulae for $ E(X_N) $ and $ \operatorname{Var}(X_N) $, (or recurrence relations, or whatever), and
  • the asymptotic behaviour of these

Example: When $ N = 3 $, there possible ways to terminate with two consecutive boxes are

  • End, then middle with probability $ \frac{2}{3} \frac{1}{2} = \frac{1}{3} $ and $ X_3 = 2 $
  • Middle, then end with probability $ \frac{1}{3} 1 = \frac{1}{3} $ and $ X_3 = 2 $, or
  • End, other end and finally middle with probability $ \frac{2}{3} \frac{1}{2} 1 = \frac{1}{3} $ and $ X_3 = 3 $.

So, we've got the full distribution of $ X_3 $, and we can compute that $ E(X_3) = 2 \frac{2}{3} + 3 \frac{1}{3} = \frac{7}{3} = 2.\overline{3} $, et cetera.

Current Work

I have managed to give an explicit (though unpleasant) formula for $ E(X_N) $. Roughly this is by analysing how the process can terminate with $ n+1 $ boxes filled, looking at the configuration one step before the end, and breaking this up into various types. (No ends filled, one end filled, both ends filled and various numbers, $ k $, of 'triples' like $ \blacksquare \square \blacksquare $.) I can then count the number of each type of configuration using standard combinatorial techniques, and then work out the probability of ending with $ n+1 $ boxes filled. I get:

\begin{align} E(X_N) &= \sum_{n=1}^{\left\lfloor \frac{N+1}{2} \right\rfloor} \sum_{k=0}^{n-1} (n+1) \binom{n-1}{k} \Bigg[ (2n-k) \binom{N-2n}{n-k} + 2(2n-k-1) \binom{N-2n}{n-k-1} \\ & {} \quad + (2n-k-2) \binom{N-2n}{n-k-2} \Bigg] \left( n! \frac{(N-n)!}{N!} \frac{1}{N-n} \right) \, , \end{align}

and similarly I can get the variance. (You can still see something of my approach reflected in the structure of the formula.)

Using this, we can compute $$ E(X_{20}) = 153641/33592 \approx 4.5737377947 \, , $$ with standard deviation $ \approx 1.6291544998 $, corroborating his initial observations.

From here, we can compute the first thousand or so values of $ E(X_N) $, to get a feeling for the behaivour at large $ N $. The result is as follows:

Plot of $ E(X_N) $, with trendline $ y = 1.0944 x^{0.4709} $, for $ N = 1, \ldots, 1200 $

So, at the first glance, is looks like maybe $ E(X_N) \sim N^{1/2} $ (plus or minus a small power). But it's at this point I'm stuck.

Questions

My specific questions about this problem are:

Is there a neater/more compact/more elegant formula to explicitly compute $ E(X_N) $?

  • Can it be done via a recurrence relation?
  • What sort of techniques are well suited to this type of computation?

How accurate is my guess that $ E(X_N) \sim \sqrt{N} $?

  • Can I determine the asymptotic behaviour from the explicit formula?
  • If not, how can I go about finding the asymptotic behaviour?

Lastly, (though I'm not expecting anywhere near a complete answer) how does all of this generalise to more complicated arrangements of boxes?

  • Say we do this on an $ N\times M $ grid, and we stop when we fill in two adjacent boxes (including diagonally, or not including diagonally).
  • Or more generally, randomly filling in the vertices of a graph, with the edges determining adjacency.
  • What if some boxes have multiple parts, so can be filled in a number of times?
$\endgroup$
  • $\begingroup$ This is quite similar to the birthday problem, especially for large $N$. $\endgroup$ – Arthur Jun 28 '14 at 10:43
  • $\begingroup$ I'm probably not going to contribute to the solution of this problem, but just for clarification: what do you mean by "consecutive students"? Consecutive in terms of alphabetic sorting of initial names? $\endgroup$ – user144248 Jun 28 '14 at 10:49
  • $\begingroup$ It shouldn't matter what order the students appear on the list, since we're picking them randomly anyway. But in this particular case it was consecutive when sorted alphabetically by surname. $\endgroup$ – Steven Charlton Jun 28 '14 at 17:59
  • $\begingroup$ I suspect the formula would be nicer if the boxes "wrap around" $\endgroup$ – leonbloy Jun 30 '14 at 19:21
4
$\begingroup$

First show that $$E(X_N)=\sum_{i=0} P(X_N>i)=\sum_{i=0}^{\left\lceil\frac{N+1}{2}\right\rceil} P(X_N>i)$$

and that (equation 1)

$$P(X_N>i)=\frac{\binom{N-i+1}{i}}{\binom{N}{i}}$$

That gives a nice recurrence formula to compute everything easily :

$$P(X_N>0)=1$$ $$P(X_N>i+1)=P(X_N>i)\frac{(N-2i)(N-2i+1)}{(N-i)(N-i+1)}$$

Now, using equation 1, and stirling approximation, you can show that

$$P(X>\alpha.\sqrt{N})\approx e^{-\alpha^2}$$

That must be enough to show that $E(X_N)=O(\sqrt{N})$.

Finally, for the grid question, it seems to be an open question related to the Hard Square Entropy

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

The derivation for $\mathbb{E}\left(X_n\right)$ can be made simpler.

Let's think of getting the probability of having exactly two adjacent boxes filled, from a row $n$ boxes when $k$ boxes are filled, which can be done in the following manner:

First, we need to obtain the number of ways of filling $k$ boxes such no two adjacent boxes are filled, which turns out to be $\binom{n-k+1}{k}$ ways.

Hence, the probability of having at least one adjacent pair filled is: \begin{align*} \mathbb{P}_k\left(\text{at least one}\right) &= 1-\frac{\dbinom{n-k+1}{k}}{\dbinom{n}{k}} \end{align*}

Similarly, when $k-1$ boxes are filled: \begin{align*} \mathbb{P}_{k-1}\left(\text{at least one}\right) &= 1-\frac{\dbinom{n-k+2}{k-1}}{\dbinom{n}{k-1}} \end{align*}

Therefore, the probability that there is exactly one adjacent pair of boxes which is filled, when $k$ boxes are filled among $n$ boxes:

\begin{align*} P\left(n,k\right) &= \mathbb{P}_{k}\left(\text{at least one}\right)-\mathbb{P}_{k-1}\left(\text{at least one}\right) \\ &= \frac{\dbinom{n-k+2}{k-1}}{\dbinom{n}{k-1}} - \frac{\dbinom{n-k+1}{k}}{\dbinom{n}{k}} \end{align*}

From here, finding the expectation is simple: \begin{align*} \mathbb{E}\left(X_n\right) &= \sum_{i=2}^{\lfloor(n+3)/2\rfloor} i\cdot P(n,i) \end{align*}

For $n=20$, \begin{align*} \mathbb{E}\left(X_{20}\right) &= \sum_{i=2}^{11} i\cdot P(20,i) = \frac{153641}{33592} \end{align*}

I may not be able to answer your other questions for now, but I believe the above formula may make it easier.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.