10
$\begingroup$

A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, each student has at some point been in a classroom with every other student?

More generally: Starting with an edgeless (undirected) graph on $cn$ vertices, let a round consist of first randomly partitioning the vertices into $c$ disjoint sets of $n$ vertices each, then adding an edge between every pair of nonadjacent vertices that lie in the same set. What is the probability that, after $y$ rounds, the result is a complete graph?

I asked this question on math.stackexchange but received no fully useful response (see here, where I've also posted an answer with further discussion and generalization and partial "solutions"). I'd especially like to know about tools for the exact answer, but approximations or bounds would also be interesting.

The particular case above was posed by a friend, who teaches in a school with those values of $c$, $n$, and $y$. In that particular case the answer is easily seen to be "Don't hold your breath, pal."

Improve this question
$\endgroup$
2
  • $\begingroup$ It looks hard even to determine in general situation, wether this probability equals 1 or not. $\endgroup$
    – Fedor Petrov
    Nov 6, 2010 at 14:53
  • 1
    $\begingroup$ sorry, I meant probability 0 $\endgroup$
    – Fedor Petrov
    Nov 6, 2010 at 16:28

2 Answers 2

Reset to default
13
$\begingroup$

A Poisson approximation should be good here, for appropriate ranges of the parameters. Consider the events $A_{ij}=$"$i$ and $j$ are never put in the same class".

Broadly speaking, if you have a large number of these events, and each individual one has low probability, and any pair of events are close to independent, and there are no anomalous higher-order dependencies (here in particular I am being completely vague) then you expect the total number of events that occur to be approximately Poisson (with mean given by the total expected number of events).

Here $P(A_{ij})=\Big(\frac{(c-1)n}{cn-1}\Big)^y$ and the total number of events is $\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)$.

If the first of those terms is small and the product is neither too small nor too large, then one would expect the distribution of the total number of events to occur to be approximately Poisson with mean

$\left(\Big(\frac{(c-1)n}{cn-1}\Big)^y\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)\right)$

and hence the probability that none of them occur should be roughly

$\exp\left(-\Big(\frac{(c-1)n}{cn-1}\Big)^y\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)\right)$.

I tried a small simulation for c=3, n=25 and y=20, for which the approximation gives a probability of 0.33571. All students met each other on 33676 of 100000 trials, which is encouraging enough for the accuracy of the approximation in this case.

(there are conditions on the dependency between the events which guarantee that this sort of approximation is (asymptotically) reliable. For example, if the events are all positively correlated in an appropriate sense. But that doesn't seem to apply here. So for the moment what is written above is merely heuristic. But maybe someone else will see how to be more precise).

Improve this answer
$\endgroup$
5
  • $\begingroup$ The computation of $P(A_{ij})$ seems to be $(1-\frac{\binom{cn-2}{n-2}}{\binom{cn-1}{n-1}})^y$? The way I think of it is first fixing $i$, then choose a $n-1$ subset at random to put $i$ in. There are a total of $\binom{cn-1}{n-1}$ ways of choosing them. But since we want $j$ to be with $i$, we are only choosing subset of size $n-2$, out of the remaining $cn-2$ vertices. Also I looked at various examples of using Stein's method to prove Poisson approximation, but this problem seems to be a little out of reach, because it's hard to come up with an exchangeable pair that differs by 1 w. h. p. $\endgroup$
    – John Jiang
    Nov 7, 2010 at 18:06
  • $\begingroup$ In the case $n =2$, is this some form of the matching problem? What can one say about the limit as $c \to \infty$ with $n$ fixed in general? $\endgroup$
    – John Jiang
    Nov 7, 2010 at 18:08
  • $\begingroup$ @John: There are $cn$ places in all. First fix the place of $i$. Now there are $cn-1$ equally likely places left for $j$, of which $n-1$ are in the same class as $i$ and the others, $(c-1)n$, are in a different class from $i$. $\endgroup$
    – James Martin
    Nov 7, 2010 at 18:20
  • $\begingroup$ @John: if $n=2$, you can also look at it as a collection of coupled coupon-collector problems. (Try saying that after a few drinks). By coupon-collector type arguments, I think that as $c\to\infty$, the probability goes to 0 if $y-2c\log c\to-\infty$ and goes to 1 if $y-2c\log c\to\infty$. Something similar for other fixed values of $n$. $\endgroup$
    – James Martin
    Nov 7, 2010 at 18:28
  • $\begingroup$ Ah great! The choosing $j$ or choosing the partition gives the same answer. The analogy to coupon collector sounds right, but I am yet to work it out. So perhaps one could adapt Stein's exchangeable pair method a bit to get poisson limit as well? $\endgroup$
    – John Jiang
    Nov 7, 2010 at 19:12
3
$\begingroup$

The answer is given in terms of inclusion exclusion principle, much as the solution for coupon collector's problem. Let $p_t$ be the probability that at time $t$ there are still two vertices with no edge in between, and let $E_t$ be the set of edges at $t$. Then, $$ p_t = \sum_{i \neq j} P((1,2) \not\in E_t) - \sum_{i_1 \neq j_1, i_2 \neq j_2, (i_1,j_1) \neq (i_2,j_2)} P((i_1,j_1),(i_2,j_2) \not\in E_t) + \ldots + (-1)^k \sum_{(i_s,j_s) \text{ distinct pairs }: s \le k} P((i_s, j_s) \not\in E_t)$$

I computed the first two terms. $$ \sum_{i \neq j} P((i,j) \not\in E_t) = \binom{cn}{2} (1-\frac{\binom{cn-2}{n-2}}{\binom{cn-1}{n-1}})^t$$

$$ \sum_{i_1 \neq j_1, i_2 \neq j_2, (i_1,j_1) \neq (i_2,j_2)} P((i_1,j_1),(i_2,j_2) \not\in E_t) = \sum_{i_1 =i_2} P)((i,j_1),(i,j_2) \not\in E_t) +\sum_{i_1\neq i_2, j_1 \neq j_2} P((i_1,j_1),(j_2,j_2) \not\in E_t) $$ $$ = 2 \binom{cn}{3} (1-\frac{\binom{cn-3}{n-1}}{\binom{cn-1}{n-1}})^t + \binom{cn}{4}[(1-\frac{\binom{cn-4}{2n-2}}{\binom{cn-2}{2n-2}})(1-\frac{\binom{cn-2}{n-2}}{\binom{cn}{n}}) + (1-\frac{\binom{cn-4}{n-2}}{\binom{cn-2}{n-2}})\frac{\binom{cn-2}{n-2}}{\binom{cn}{n}}]^t$$

A crude bound is given by $$ (1-\frac{\binom{cn-2}{n-1}}{\binom{cn-1}{n-1}})^t \le p_t \le \binom{cn}{2} (1-\frac{\binom{cn-2}{n-1}}{\binom{cn-1}{n-1}})^t$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ You might like to follow the link in the original post to my solution on math.stackexchange, which is identical to yours but is expressed perhaps more elegantly. Sadly, these can't be used to get any actual results; try it even for $c=n=2$! Or write out one more term (they get tougher very quickly) and note that there are $cn\choose 2$ terms in all. [Continued next comment] $\endgroup$
    – Larry Denenberg
    Nov 13, 2010 at 20:16
  • $\begingroup$ I believe your bound is incorrect; you don't want "1 -" on either side, right? This bound is very crude; it says that the probability that some two students miss each other is at least the probability that a particular pair of students do, and is at most this value times the number of pairs of students. It's analogous to saying that if you throw a fair die $N$ times, the chance of getting at least one 3 is between $1/6$ and $N/6$. In the case at hand ($c=3$, $n=25$, $y=6$) it says that the probability of failure (not all students see each other) is 0.095 at least and 264.06 at most. $\endgroup$
    – Larry Denenberg
    Nov 13, 2010 at 20:20
  • $\begingroup$ The two types of counting give the same result. One is by counting the number of ways to put the first and second students in the same class, the other is by counting the number of students that are in the same class as the first person. You are right that this computation will have cn terms in general. I don't claim the computation has been carefully checked. But I think 1- is correct. $\endgroup$
    – John Jiang
    Nov 15, 2010 at 7:36
  • $\begingroup$ ${cn -2\choose n-1}\over{cn -1\choose n-1}$ is the probability that two given students are in different classes. It equals $(cn-n)/(cn-1)$; there are $cn-1$ seats for the second student, $cn-n$ of which are not in the first student's class. Subtracting from 1 gives the probability that two given students are in the same class. Raising to the $y$ power gives the probability that two given students are always in the same classroom, which is irrelevant. We need the probability that the two students are always in different classrooms. So we shouldn't subtract from 1 before exponentiating. $\endgroup$
    – Larry Denenberg
    Nov 16, 2010 at 15:01
  • $\begingroup$ Oh yea you are right. I somehow thought $\binom{cn-2}{n-2}/ \binom{cn-1}{n-1}$ was small, that's why it made sense to me to subtract from 1. But in fact it's very close to 1. Thanks for the correction! $\endgroup$
    – John Jiang
    Nov 17, 2010 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .