Given a mesh network of N nodes, where each node is connected to C other nodes, what is the probability a node is connected to another directly, or indirectly through a maximum of D bridge nodes?
Please look for the latest attempt within the answers.
Attempt 1 (wrong)
(As pointed by Amaury.)
I have developed a function, but I doubt it is correct for 1) I've never been good at calculating probabilities, and 2) it is easy for this function to yield greater than 1 probabilities. Here it goes anyway:
The probability of a direct connection would be
$$P(N,C,0) = \frac{1}{N-1}$$
The probability of an indirect connection should be multiplied by $C$, which yields
$$P(N,C,1) = \frac{1}{N-1} + C \frac{1}{N-1}$$
Abstracting the pattern, we should get
$$P(N,C,2) = \frac{1}{N-1} + C \left(\frac{1}{N-1} + C \left(\frac{1}{N-1}\right)\right)$$
for a depth of 2 bridge nodes. And generalizing the abstraction, I get
$$P(N,C,D) = \frac{1}{N-1} \sum_{n=0}^{D}{C^{D-n}}$$
Now, is this correct? Please point my flaws otherwise.
Best Answer
Attempt 3
(By author.)
This is a totally different approach. The following assumptions were made to develop it:
So I figured this time the probability of A being connected to B must have the form $$P = \frac{S}{N-1}$$ where $S$ is the amount of nodes in A's network.
The probability $P_n$ of discovering $C$ new nodes by picking them at random from the network of $N$ nodes in the $n$th try is given by $$P_n = \frac{ _{F_n}C_C }{ _NC_C }$$
Where $F$ is the amount of nodes in the network yet to pick. $$F_n=N-S_n$$ Where $S_n$ grows from $S_0 = 0$ with each iteration, until $C^D$ iterations are reached. In fact, $$S_n = C P_n$$
So $S$ is given by $$S = \sum_{n=1}^{C^D}{C P_n}$$
Then the probability $P$ is fully defined by the parameters $N$, $C$ and $D$. The algorithm found is very prone to taking up long computation times.