Consider a random bipartite graph $G$ with $K$ left nodes and $M$ right nodes. Each of the $KM$ possible edges of the graph is connected with probability $p$ independently.

I'm trying to compute the expected number of left nodes connected to right nodes of degree $1$, as $K$ and $M$ get large. My first attempt was to observe that there are $Mp$ expected connected right nodes to each left node. By linearity, the expected number of singletons is then

$$ P(\text{this left node is singleton}) = Mp \cdot P(\text{right node is singleton}) $$

However, I'm having a hard time computing $P(\text{right node is singleton})$ since the the number of left nodes connected to each right node is a probability function.

Can anyone help me out? Am I going about this problem the wrong way? Could anyone give me a solution to this problem?

  • $\begingroup$ The degree of a node in the right part follows a binomial distribution with parameters $k$ and $p$. In math, let $v \in M$ then $d(v) \sim Bin(K,p)$ this allows you to compute the probability of a specific node in the right part to have degree one. $\endgroup$ – Rodrigo Ribeiro Oct 28 '14 at 14:29

Let $u \in K$ and $v \in M$. I'm using $K$ and $M$ to denote the sets of nodes and theirs sizes, ok?

$$P(u \leftrightarrow v, d(v)=1) = P(d(v)=1 |u \leftrightarrow v)P(u \leftrightarrow v)=(1-p)^{K-1}p$$

Now, let $$N = \sum_{u\in K}\sum_{v\in M} 1_{\{u↔v,d(v)=1\}}$$

note that $N$ counts the number of nodes in $K$ which connect to nodes in $M$ with degree one. Taking the expected value and using linearity you get $$\mathbb{E}[N]=KMp(1-p)^{K-1}$$

You can play with the expression above putting $K$ or $M$ as a function of each other. Or you can set $p$ as a function of $K$ and $M$...

Hope this can help...

  • $\begingroup$ Shouldn't there be a factor of $p^2$ in the final answer? Shouldn't the probability of a right node being a singleton be $$ K(1-p)^{K-1}p $$ since it is a binomial random variable (i.e. there are $K$ ways to choose the node that it is connected to). $\endgroup$ – Ryan Oct 29 '14 at 4:10
  • $\begingroup$ Redacted. Now I understand your solution. $\endgroup$ – Ryan Oct 29 '14 at 8:08
  • $\begingroup$ Agree now? I fixed which node on the left we are connecting, then you lose this factor $K$. $\endgroup$ – Rodrigo Ribeiro Oct 29 '14 at 16:22
  • $\begingroup$ I don't think this is correct. The summation is recounting each left node for each singleton right node it's connected to. For example, if L1 is connected to R1 and R2 (both singletons), your summation will count twice. $\endgroup$ – Zizheng Tai Feb 2 '17 at 8:33

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.