2

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.

Nathan
  • 79
  • 2
    Is the answer $$n\cdot\frac{\binom{\binom{n-1}2}y}{\binom{\binom n2}y}\ ?$$ – bof Oct 16 '16 at 02:55
  • @bof Can you explain the logic? – Nathan Oct 16 '16 at 09:11
  • @bof it also should depend on number of edges I think. – Nathan Oct 16 '16 at 09:15
  • Of course it deponds on $y,$ the number of edges. The is that the fraction is the conditional probability, given $Y=y,$ that a vertex $v$ is isolated; I multiply by $n$ to get the expected number of isolated vertices. Is my answer wrong? – bof Oct 16 '16 at 10:07
  • @bof the fraction will give number of graphs with at least 1 isolated vertix. That is denoted by $\mathbb{P}(X\ge 1 | Y)$. But what I need to calculate is $\mathbb{P}(X = x | Y)$. – Nathan Oct 16 '16 at 11:52
  • 1
    (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 ... – Did Oct 16 '16 at 14:29
  • 1
    ... 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. – Did Oct 16 '16 at 14:29
  • @Did I understand the formula of probability. But in my opinion this will also include graphs which have isolated vertices which are other than $\nu$. And in formula for calculating conditional expectation we need exact number of nodes, not at least. – Nathan Oct 16 '16 at 15:02
  • 1
    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. – Did Oct 16 '16 at 15:05
  • @Did Thank you. But now I feel totally disoriented. I will try to figure out. – Nathan Oct 16 '16 at 15:09
  • 1
    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... – Did Oct 16 '16 at 15:12
  • @Did thanks a lot now I understand. Is it correct that $\mathbb{E}(\mathbb{E}(X|Y))=\mathbb{E}(X)$?

    Offtop: How to mark this as an answer?

     – Nathan Oct 16 '16 at 15:25
  • I have checked this property it seems to be correct! Thanks again. – Nathan Oct 16 '16 at 15:33
  • Yes, $E(E(X\mid Y))=E(X)$ holds in full generality. – Did Oct 16 '16 at 15:41
  • 1
    Does this answer your question? Expected number of isolated vertices for random graph G(n, N) – Andrew Uzzell Mar 22 '22 at 18:22

0 Answers0