1
$\begingroup$

In relation to a research project I'm in, an interesting question came up:

Given a classroom of a certain size, with a certain number of students in it for a certain amount of time, what is the average distance between them.

I'm ignoring the time aspect of the problem and only focusing on the other parts.

I tried modeling the room as simply a rectangular region in a Cartesian plane with $N$ students occupying some randomly chosen group of points with integer coordinates i.e lattice points.

Each configuration of $N$ students is equally probable. No 2 students can occupy the same point.

I came up with this formula for the expected value of the Euclidean distance between any $2$ students:

$$\mathbb{E}[d(s_i, s_j)] = \dfrac{1}{2N(N-1)} \dfrac{WH-2 \choose N-2}{WH \choose N} \sum_{x_i = 0}^{W} \sum_{y_i = 0}^{H} \sum_{x_j = 0}^{W} \sum_{y_j = 0}^{H} \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$

Where $W$ is the unit width of the room, $H$ the unit height, and $N$ the number of students. Each student $s_i$ is defined by a unique point $(x_i, y_i)$. The term $\dfrac{WH-2 \choose N-2}{WH \choose N}$ represents the probability that a given configuration of the class has those 2 points occupied by a student and $\dfrac{1}{N(N-1)} = P(s_i)P(s_i | s_j)$ represents the probability that those 2 students are picked (the 2 is because of double counting). These are constant so I just moved them to the outside.

Similar questions have been answered before (1,2,3,4,5) for any points within a region rather than just lattice points. The closest thing to that question is (Average shortest distance between some random points in a box) but I would like to know how it scales for any general rectangular region. In addition, that answer simply simulated the points and said the problem can be approximated as the "any 2 random points in a unit square" problem, but that only works for low values of $N$ and for a unit square. It also doesn't provide a proof.

My main questions are:

  1. Is there a closed form expression for the sum above?
  2. If not, is there a way to approximate the problem above?
  3. Is simply simulating the above problem the best course?
$\endgroup$
6
  • $\begingroup$ Can two students occupy the same lattice point? $\endgroup$ – user Jun 8 '20 at 9:54
  • $\begingroup$ There is certainly a logical problem here. Computing the prefactor you will obtain $\frac1{2WH(WH-1)}$, the value independent of $N$. This is not what one intuitively expect for the dependence (the more students - the shorter mean distance). $\endgroup$ – user Jun 8 '20 at 11:01
  • $\begingroup$ True. Maybe one of the factors is unnecessary, but if so then I would maybe have to some over elements of a sets rather than coordinates in a range which makes things more complicated. I'm wondering where my intuition went wrong. $\endgroup$ – Andrei Racila Jun 8 '20 at 11:09
  • $\begingroup$ Maybe you are correct, but the problem is ill-stated. Could it be that you are in fact interested in the mean value of the shortest distance instead? $\endgroup$ – user Jun 8 '20 at 11:12
  • $\begingroup$ The problem isn't about mean shortest distance, it's about mean distance alone. Also, I believe that $P(s_i)P(s_i | s_j)$ could equal N/WH * N/WH as the probability a point $(x_i, y_i)$ is occupied is N/WH and same for $(x_j, y_j)$. as we also include $(x_i, y_i)$ = $(x_j, y_j)$. I think that should be the real term out front but I'm not sure. It could also be just N(N-1)/WH(WH-1) as when the 2 points are equal they're just zero. What it implies is that 1/2N(N-1) is redundant. $\endgroup$ – Andrei Racila Jun 8 '20 at 11:26
1
$\begingroup$

You couch the sum in terms of placing $N$ students randomly on $WH$ lattice points and then choosing two of the $N$ students at random. But this is just a fancy way of picking two lattice points. And by the symmetries of the two operations by which you do this, no pair of points is more likely to be chosen than another.

Hence it is not surprising if you get an answer that is independent of $N.$

In fact there are $\binom{WH}{2}$ ways to choose the pair of points, and as each is equally likely, the probability weight on each point in your sum should be $$\frac{1}{\binom{WH}{2}} = \frac{2}{WH(WH-1)}.$$

Taking into account that a summation like the one you are using will visit each pair of points twice, we can instead give each term the weight $$\frac{1}{WH(WH-1)}.$$

You almost got this, except that while you were worried about double-counting the points you forgot about double-counting the pairs of students when you wrote $N(N-1).$ In fact there are $\binom N2 = \frac12N(N-1)$ ways of choosing two students out of $N,$ and this $\frac12$ cancels the factor of $2$ that you wanted to put in the denominator.

There are some other inconsistencies in your summation, however. One of these is a "fencepost" problem: you seem to have difficulty deciding whether your room of dimensions $W \times H$ has $H$ rows of lattice points with $W$ points in each row or $H+1$ rows of lattice points with $W+1$ points in each row. The claim that there are $\binom{WH}{N}$ ways to place $N$ students says that you are thinking of $H$ rows with $W$ points in each row, but a summation of the form

$$ \sum_{x_i = 0}^{W} \sum_{y_i = 0}^{H} $$

creates $(W+1)(H+1)$ terms corresponding to $H+1$ rows with $W+1$ points in each row.

If you really want $H$ rows with $W$ points in each row, a possible summation is

$$ \sum_{x_1 = 0}^{W-1} \sum_{y_1 = 0}^{H-1} \sum_{x_2 = 0}^{W-1} \sum_{y_2 = 0}^{H-1} \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}. $$ By stopping at $W-1$ you ensure that you only count $W$ rows.

Alternatively, you can let the coordinates run from $1$ to $W$ and $1$ to $H.$

If you really want coordinates from $0$ to $W$ and $0$ to $H$ then you must account for $(W+1)(H+1)$ lattice points, and the factor out front becomes

$$\frac{1}{2\binom{(W+1)(H+1)}{2}} = \frac{1}{(W+1)(H+1)(WH + W + H)}.$$


By the way, in general when summing over pairs of distinct points in a rectangular grid I would have written the last summation as something like $$ \sum_{\substack{0 \leq y_2 \leq H - 1\\(x_2,y_2)\neq(x_1,y_1)}}, $$ but I realize that in this particular summation, the terms where $(x_2,y_2)=(x_1,y_1)$ come out to zero and have no effect on the result.

$\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.