Say I have an infinitely large grid where the probability any given square contains a node is $p$. Each node makes a connection with its $k$ nearest neighbours. How do I calculate the average distance between each connected node pair on the grid, in terms of Manhattan distance?
I have managed to do it for $k=4$ and $p=0.1$ by deriving the following formula:
At a distance of $d$ from any given cell, there are $4d$ cells (recall manhattan distance: there are 4 nodes at a distance of 1 apart, 8 nodes at a distance of 2 apart, 12 at a distance of 3 apart...).
Since $k=4$, we expect to find the 4 nearest nodes within $4/0.1 = 40$ cells. We cover 40 cells when our search radius $r$ is 4, since 4+8+12+16 = 40. Hence the expected avg. distance between connected pairs is (4/40 * 1) + (8/40 * 2) + (12/40 * 3) + (16/40 * 4) which is 3.
This is the same as:
Avg distance between connected pairs $= \sum\limits_{d=1}^r \frac{4d^{2}}{n}$
My problem is, what about when the search radius $r$ is not an integer? The formula no longer works. Note that you can solve for $r$ using:
$\frac{k}{p} = 2r(r+1)$
when $k=4, p=0.1$ then $r=4$. But usually it will be a non-integer.
In Taxicab metric, the "circle" of "radius" $r$ is going to the the diamond $|x|+|y|=r$ and it has $4r$ points.
Therefore we expect $4pr$ points at distance $r$. If $X$ is your random set, then $\mathbb{P}[ | \{ x \in X : |x| \leq r \} | < 4]$ is a calculations of binomial distribution. There are $2r(r+1)$ points to test.
Using Chebyshev's inequality we can estimate the odds the number of points deviates from our expectations.
$$\mathbb{P}\big[\; \big| \#\{ x \in X : |x| \leq r \} - 2pr(r+1)\big| \geq n\cdot 2p(1-p)r(r+1) \;\big] \leq \frac{1}{n^2} $$
We need to solve for $2pr(r+1) = 4$ or $r \approx \sqrt{2/p}$. What is the meaning of not having an integer radius?
Our standard deviation is $2(1-p) \approx 2$ in the limit of small probability. So you may have to search for a radius larger than you expected. $\sqrt{2/p} + 10$ has at most a 4% probability of not having your point.