ClosestRabbit

Notation: If rabbit $y$ is the closest to rabbit $x$ (under the tie-breaking rules), and we add an edge between rabbit $x$ and rabbit $y$, then we say $x$ points to $y$.

Review

Summary

Most of my initial observations were useless (although they were not necessarily incorrect). The most helpful ones ended up being the later ones, which I summarize as : "We have to use probability tricks, along with exploiting the structure of the graph."

With most probability problems, there is often a "random variable" whose expectation we are trying to find. Often-times by writing it out, you can find nice patterns. Usually, this one "random variable" turns into the sum of many smaller / simpler random variables (often variables that can only be equal to $0$ or $1$). You can then find the original expected-value as the sum of expected values of these variables (the "Linearity of Expectation"). (See below for more resources on probability problems).

First, we must be able to write down the random variable (the number of components) in a nice form. We start by looking at the structure of the components; and we notice that, because the graph has $R$ nodes and $R$ edges (where $R$ is the number of rabbits), every component of the graph contains a single cycle with "arms" (paths) attached. (Drawing a picture helps here.)

Upon further inspection, we notice that there cannot be any "long" cycles in this graph. This is because each edge corresponds to a "closest neighbour" for some node / rabbit, and we can prove that all the nodes on a given cycle must mutually be same distance to each other. (This was proved in Idea 1 above.) Because of the "tie-breaking" rule, if all of these nodes are equidistant to each other then they would all pick the same node. Using this argument we can show that there won't be a cycle of length three or more, because this would lead to some kind of contradiction. So every cycle has length exactly two (as there are no self-edges either).

The above arguments tell us: 1) There is exactly one cycle in every component; and 2) Every cycle has length exactly two (i.e.: it is a pair of nodes, that share a duplicate-edge). Altogether, this is enough to yield the characterization we need.

Let $C$ denote the number of cycles (this is a random variable that depends on the final arrangement of rabbits). For a pair of rabbits in cell $a$ and cell $b$, we define $Y_{ab} := 1$ if and only if the two rabbits are mutually closest to each other, or we set $Y_{ab} = 0$ otherwise. Based on the above arguments, in any configuration, we have that $C = \sum Y_{ab}$ over all pairs of distinct empty cells $a$ and $b$. Since our problem is to find $E[C]$ (the expected value of $C$), we can now (finally) use the Linearity of Expectation to get that:

over all pairs of distinct empty cells $a$ and $b$.

It is fairly easy to compute $E[Y_{ab}] = Pr(Y_{ab} = 1)$ by counting. Particularly, for two cells $a$ and $b$, consider a cell $c$ so that $a$ would point to $c$ instead of $b$ if both cells have a rabbit (for simplicity, we say that $a$ prefers $c$ over $b$). If $c$ has a rabbit on it, then $Y_{ab} = 0$ (obviously, since $a$ does not point to $b$). A similar truth holds if $b$ prefers $c$ over $a$. On the other hand, if we cannot find any such cell $c$ then $Y_{ab}$ must be 1, since $a$ and $b$ must point to each other. So altogether, if we let $B := \{c : a \text{ prefers } c \text{ or } b \text{ prefers } c\}$, then we can write $Pr(Y_{ab} = 1)$ as:

where $S$ is the set of all empty cells, $B$ is the set as described now, and $R$ is the number of rabbits. Note that the denominator $\binom{|S|}{R}$ is just the total number of configurations, and the numerator is the number of configurations that result in $a$ and $b$ mutually pointing to each other.

Altogether, our algorithm is to sum up the $E[Y_{ab}]$ values and return this number. For a fixed $Y_{ab}$ we only need to find the set $B$ (as described above). This can be done by manually checking all other empty cells $c$ to see if either $a$ or $b$ prefer $c$. Here is the pseudo-code.

<code class="python">
  choose(n,k):
    return n! / k! / (n-k)!;
 
  Y(a, b):
    if (a==b): return 0
    bad_cells = 0
    for each empty cell c:
      # Check if a prefers c over b or if b prefers c over a
      a_prefers_c = false
      b_prefers_c = false
      if distance(a,c) < distance(a,b) or (c beats b in the tie-breaker): a_prefers_c = true
      if distance(b,c) < distance(b,a) or (c beats a in the tie-breaker): b_prefers_c = true
 
      if a_prefers_c or b_prefers_c:
        bad_cells ++
 
    S := (total empty cells including a and b)
    R := (total number of rabbits including those on a and b)
 
    return (double) choose(S-2-bad_cells, R-2) / choose(S,R)
 
  getExpected(board, R):
    answer = 0.0
	for each pair (a,b) of empty cells in board:
	  answer += Y(a,b)
	return answer
	</code>

Where the answer is

getExpected(board,R)

.

The running time of the algorithm is $\Theta((NM)^3)$, since we essentially check every triplet of cells once in the worst case. Also, be careful about precision. I would NOT use the "choose" function as described above, and also make sure to use doubles or long doubles, because the numbers can get pretty large.

1. There is exactly one cycle in each component. This comes from the structure of the graph. Also, any graph with $n$ nodes and $n$ edges must have this property (I think).
2. No cycle can contain more than two nodes. This can be found by exploiting the symmetry of cycles and the "nearest neighbour" graph.
3. Rabbits in cells $a$ and $b$ are mutually "closest" if and only if there is no other cell $c$ such that $a$ prefers $c$ or $b$ prefers $c$.
4. **Let $S$ be the set of empty cells. Let $a,b$ be a pair of distinct empty cells. Let $B$ be as defined earlier. Let $C$ be the number of components, then $E[C] = \sum E[Y_{ab}]$, and