2
$\begingroup$

I have Bernoulli random graph model. With probability $p$ we take each edge. We have n vertices. Expected number of isolated vertices is $n{(1-p)}^{n-1}$.

But what about conditional expectation? I cant compute expected number of isolated vertices given number of edges.

I am starting with the definition $\mathbb{E}(X|Y)=\sum_{x \in X}x\mathbb{P}(X=x|Y)$ Where $X$ is the RV to denote number of isolated vertices, $Y$ is RV to denote number of edges in our random graph. $x \in \{0, 1, .. , n\}$.

And I can not compute probability $\mathbb{P}(X=x|Y)$. It is needed to know to compute this expectation by definition.

Maybe there is a good way to compute it or different way to compute conditional expectation.

$\endgroup$
  • 2
    $\begingroup$ Is the answer $$n\cdot\frac{\binom{\binom{n-1}2}y}{\binom{\binom n2}y}\ ?$$ $\endgroup$ – bof Oct 16 '16 at 2:55
  • 1
    $\begingroup$ (This confirms @bof's comment.) Assume there are $y$ edges and fix some vertex $v$, then $v$ is isolated if and only if all the $y$ edges avoid it. There are $c_n={n\choose2}$ possible edges and $c_{n-1}={n-1\choose2}$ edges avoiding $v$ hence the probability that all the $y$ edges avoid $v$ is $${{c_{n-1}\choose y}\over{c_{n}\choose y}}$$ Let $X$ denote the number of isolated vertices and $Y$ the number of edges, this yields $$E(X\mid Y)=n{{c_{n-1}\choose Y}\over{c_{n}\choose Y}}$$ Note that this does not require to compute ... $\endgroup$ – Did Oct 16 '16 at 14:29
  • 1
    $\begingroup$ ... the conditional distribution of $X$ conditionally on $Y$, which is fortunate since this latter task is more complicated. Note also that $E(X\mid Y)=n$ on the event $[Y=0]$ and that $E(X\mid Y)=0$ on the event $[Y>c_{n-1}]$, which is only logical. $\endgroup$ – Did Oct 16 '16 at 14:29
  • 1
    $\begingroup$ No. The expected number of isolated vertices is the sum of the probabilities that each vertex is isolated, which, by symmetry, equals $n$ times the probability that a given vertex is isolated. Once again: expectations do not require distributions. $\endgroup$ – Did Oct 16 '16 at 15:05
  • 1
    $\begingroup$ Maybe this could help: let $A_i$ denote the event that vertex $i$ is isolated, then $X=\sum\limits_{i=1}^n\mathbf 1_{A_i}$ hence $E(X\mid Y)=\sum\limits_{i=1}^nP(A_i\mid Y)=nP(A_1\mid Y)$. This is one miracle the linearity of expectation can perform... $\endgroup$ – Did Oct 16 '16 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.