4
$\begingroup$

Assume an undirected simple graph $G=(V,E)$ is created randomly: an edge $e=(u,v)$ is in $E$ with probability $p$, independent of other edges.

Assume we select a random cut $(S,T = V\setminus S)$ in the graph. What is the expected value of its size? (The size of the cut is the number of edges $(u,v)\in E, u\in S, v\in T$)

I have made an attempt with the following approach: the maximal possible size of such a cut is $|S|\cdot|T|$ (every vertex in $S$ is connected to every vertex in $T$). So the mean cut can be calculated as follows:

$$\sum_{i=0}^{|S|\cdot|T|}i \cdot P(\text{size of the cut is } i)$$

However, I am having difficulty with $P(\text{size of the cut is } i)$. Somehow I must refer to the total number of edges. It is the probability that an edge $(u,v)$ exists ($p$), and that $u \in S$ and $v\in T$ (the probability that $u\in S, v\in T$ are not given...) and that all other edges do not satisfy any of those three conditions. Therefore, this sounds like an infeasible approach.

$\endgroup$
  • $\begingroup$ Is this reference pertinent : (people.maths.ox.ac.uk/scott/Papers/planted.pdf) ? $\endgroup$ – Jean Marie Oct 27 '17 at 18:12
  • $\begingroup$ From an initial look, I do not think so. The paper revolves around vertex classes, while I am referring to simple cuts. $\endgroup$ – TheNotMe Oct 27 '17 at 18:15
3
$\begingroup$

This sort of depends on how you select the random cut. We might do it uniformly: for every vertex $v$, we put $v \in S$ with probability $\frac12$, $v \in T$ otherwise, and make this decision independently for all vertices.

If we fix the cut $(S,T)$, then the formula $$\mathbb E[\text{size of $(S,T)$ cut}] = \sum_{i=0}^{|S||T|} i \cdot \Pr[\text{size is }i]$$ is valid, but it's much easier to approach this by linearity of expectation: each of the $|S||T|$ edges is present with probability $p$, so the expected number of edges present is $p|S||T|$.

This is a formula that depends on $S$ and $T$ (or rather, on their sizes). To get the overall formula, we can substitute the previous result into the summation

$$\mathbb E[\text{size of cut}] = \sum_{S \subseteq [n]} \mathbb E[\text{size of $(S,[n]\setminus S)$ cut}] \cdot \Pr[\text{the cut is }(S,[n]\setminus S)].$$

In the case where $S$ is chosen uniformly from all subsets of $[n]$, this is $$\sum_{S \subseteq [n]} p |S|(n-|S|) \cdot 2^{-n} = \sum_{k=0}^n pk(n-k) \binom nk 2^{-n}$$ where we get the second sum by grouping the sets $S$ together by size. This simplifies to $\frac14 n(n-1)p$.

We can also get this result much more directly by observing that each edge of the graph $G$ is present with probability $p$, and its endpoints end up on different sides of the cut with probability $\frac12$, so it ends up contributing $1$ to the size of the cut with probability $\frac p2$. By linearity of expectation, the size of the cut is $\frac p2 \binom n2 = \frac14 n(n-1)p$.

$\endgroup$
  • $\begingroup$ I have a question regarding the last approach. "it ends up contributing $1$ to the size... with probability $\frac{p}{2}$", that I understand. How did we get the ${{n}\choose{2}}$ factor from the linearity of expectation? $\endgroup$ – TheNotMe Oct 30 '17 at 7:30
  • $\begingroup$ There are $\binom n2$ potential edges. $\endgroup$ – Misha Lavrov Oct 30 '17 at 14:45
  • $\begingroup$ Hi, first of all thanks for all these instructive answers. I was if you'd be potentially interested in this recent post: math.stackexchange.com/questions/2960593/… I feel sort of lost, have no clue how to tackle the question if i'm honest (even in the case of a finite example). Your help would be very valuable. $\endgroup$ – user929304 Oct 18 '18 at 10:56

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.