# Probability of eventually randomly select every node in a given set

I'm trying to calculate the probability of reaching all the nodes in a given set of nodes in X rounds.

The rules are the following:

• The game starts with one node talking to k random other nodes;
• k is the ammount of nodes every node can talk to in each iteration;
• Every node can only contact k other nodes if it was contacted by any other node/nodes in the previous round;
• Every node can communicate with any other node;
• The game ends when every node gets contacted throughout the game. Doesnt need to contact all the nodes in a given round but instead need to contact the last remaining nodes in that round;
• No node has previous knowledge of the nodes contacted before and keeps its choices random in every round.

A given example of the game would be something like this: Problem example

My problem is that since the number of nodes that send a message in every round keeps changing, because a node can only participate in the next round if it was contacted in the previous.

The answer to this problem depends on the number of rounds. A good example of a question to this problem would be something like: "Given a set of 500 nodes what is the probability that in 10 rounds every node will be contacted given that every node can only contact 25 other nodes"

• Can any node contact any other node? Commented Oct 13, 2020 at 18:08
• Yes every node can communicate with every other node @QC_QAOA Commented Oct 13, 2020 at 18:12

There might be a clever way to discover the probability (especially since every node can communicate with every other node) but I couldn't figure one out. However, here is a theoretical way of getting the probability. I say theoretical since no computer could actually do this process for anything other than small $$n$$. That being said, this process would theoretically work if every node does not communicate with every other node (which might be handy for other applications).

There are a finite number of possibilities that can occur before every node has been reached at least once. However, this number is extremely large. Here is one possible way of enumerating each possible state. Consider a bit string of $$2n$$ digits, each of which can take the values $$0$$ and $$1$$. The first $$n$$ digits state whether a particular node has been communicated with before. The second $$n$$ digits state whether a particular node was communicated with in the previous round. For example, with $$3$$ nodes you would read

$$(101,100)$$

to mean: Nodes $$1$$ and $$3$$ have been communicated with in any previous rounds and node $$1$$ was communicated with in the previous round. Thus, there are on the order of $$2^{2n}=4^n$$ possible states for $$n$$ nodes. This number is not exact as certain states are impossible to attain (like the all $$0$$s state) but it is a good upper bound. For a lower bound, note that there are at least $$2^(n-k)$$ states since there will always be at least $$k$$ states that were communicated with the previous round (except for the first round) and the remaining $$n-k$$ nodes all are either on or off. Either way, there are an exponential number of finite states in $$n$$. So for the example given, there are at least $$2^{500-25}=2^{475}\approx 9.76\star 10^{141}$$ (Like I said, no computer could actually do this). Of particular note, the state

$$(11...1,...)$$

signals the end of the game as every node has been communicated with in some previous round.

The process: Since we have a finite number of possible states, we can use Markov Chains to find the probability that any particular state has been reached after $$m$$ rounds. That is, we need to find

$$P(\text{first n digits are all 1 after m rounds})=\sum_{i=0}^{2^n-1}P((11...1,[i]_2)\text{ after m rounds})$$

(here, $$[i]_2$$ is the binary representation of $$i$$). However, let me reiterate again how impossible this is to do for any large $$n$$. This would require:

$$-$$ Multiplying a $$4^n\times 4^n$$ matrix $$m$$ times and reading $$2^n$$ entries (upper bound)

$$-$$ Multiplying a $$2^{2n-k}\times 2^{2n-k}$$ matrix $$m$$ times and reading $$2^n$$ entries (lower bound)

For example, for $$n=3$$ and $$k=1$$ (which corresponds to a $$64\times 64$$ matrix), we find that the probability of of succeeding after $$m$$ rounds is $$1-2^{1-m}$$. This answer could actually be found fairly simply without the process outlined above. However, this is because $$k=1$$. For $$k>1$$, the probability becomes much more complicated to figure out. In general, the $$k=1$$ problem is equivalent to the Coupon Collectors Problem.