The following problem is an excerpt from the book Introduction to Probability Models, 10th edition, by Sheldon Ross. The origin of this problem is from $\S3.6.2$ A Random Graph, specifically after Equation (3.23) on page 147.

Here goes the problem:

Some backgrounds:

Let $C$ denote the number of connected components of our random graph, where each node has one arc emanating from it, and each component consist of several connected nodes. Let $$P_n(i) = P\{C = i\}$$ where we use the notation $P_n(i)$ to make explicit the dependence on $n$, the number of nodes. For example, $P_k(1)$ denotes the probability that there exists a connected component consists of $k$ nodes.

To obtain $P_n(2)$, the probability of exactly two components in a graph with $n$ nodes, let us first fix attention on some particular node—say, node $1$. In order that a given set of $k − 1$ other nodes—say, nodes $2, . . . , k$—will along with node $1$ constitute one connected component, and the remaining $n − k$ a second connected component, we must have

  • $X(i) \in \{1, 2, . . . , k\}$, for all $i = 1, . . . , k$.
  • $X(i) \in \{k + 1, . . . , n\}$, for all $i = k + 1, . . . , n$.
  • The nodes $1, 2, . . . , k$ form a connected subgraph.
  • The nodes $k + 1, . . . , n$ form a connected subgraph.

The probability of the preceding occurring is clearly $$ \left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$

and because there are ${n−1 \choose k−1}$ ways of choosing a set of $k−1$ nodes from the nodes $2$ through $n$, we have: $$P_n(2) = \sum_{k=1}^{n-1}{n−1 \choose k−1}\left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$.

Here are my questions:

  1. Why is the probability of being in the first component as $\left(\frac{k}{n}\right)$ for each node in the second to last equation? It occurs to me the probability of two consecutive selections are dependent, i.e., if we have $k$ nodes in the first component, the probability of choosing one node, which happens to be in the component, is $\left(\frac{k}{n}\right)$, then the next node being chosen will have a probability of $\left(\frac{k-1}{n-1}\right)$ to appear in the same component.
  2. Why in the last equation will we choose the $k$ nodes by first fix one and then choose the left $k-1$? Why don't we choose the $k$ nodes at once? i.e., $$P_n(2) = \sum_{k=1}^{n-1}{n \choose k}\left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$.
  • $\begingroup$ Hi @Mark L. Stone, Can you help me on this problem? $\endgroup$ – Rax Yao May 16 '16 at 22:36

I think I have an answer for you.

To Question 1:

I can offer an alternative derivation that gives the same result as the book. The probability of something being true is the number of states where it is true divided by the total number of states in the universe. For a random graph there are $n^n$ possible states. If we were able to cut the universe into two pieces one with k states and one with n-k states the probability would be $\frac{k^k (n-k)^{n-k}}{n^n}$. Since we require that the two pieces be connected we multiply by the $P_i(1)$ factor for each piece giving the book's $\frac{k^k (n-k)^{n-k}}{n^n}P_k(1)P_{n-k}(1)$.

To Question 2:

The reason we choose $k-1$ nodes rather than $k$ nodes is because the book chose the first node already. This breaks the symmetry/mystery of whether you were calculating the $k$ or $n-k$ piece from the previous equation. Thus if you include the ${n}\choose {k}$ instead you will be off by a factor of two due to double counting.

| cite | improve this answer | |
  • $\begingroup$ For the first question, I have some clues already. For each arc to reach a node within the $k$ nodes set, it has a probability of $\frac{k}{n}$. For question 2: I think $\frac{1}{2}\times\binom{n}{k}$ will not be the same as ${n-1 \choose k-1}$. $\endgroup$ – Rax Yao May 18 '16 at 3:07
  • $\begingroup$ For the question then you agree that the probabilities are independent, this is in contrast to what you were saying earlier. It looks like the $P_k$'s take care of any additional geometric factors. For the second question I'm saying the two are the same under the sum not on a factor by factor basis. (I don't think you can take it out of the sum so I don't understand your objection) $\endgroup$ – Kitter Catter May 18 '16 at 3:12
  • $\begingroup$ @ Kitter Catter, Can you be more specific on your explanation on the second question? Why would the author fix one node first and then select the rest nodes? $\endgroup$ – Rax Yao May 18 '16 at 3:45
  • 1
    $\begingroup$ @RaxYao. Sorry for not being more clear. If we look at the sum in the second question it is going over all possible sizes for one of the connected clusters, in order for such a sum to make sense/be unambiguous you would have to choose a cluster of nodes. That is what the choosing a particular node does. It chooses which set of clusters you are summing over in a fixed way. $\endgroup$ – Kitter Catter May 18 '16 at 4:05

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.