# A probability problem on randomly generated graph

The graph we discuss here is a directed pseudo-graph (two vertices can have multiple edges) with self-loops. The problem is to prove a very intuitively probability formula at the end.

The background

Given a set of vertices $V$, suppose we know there are $|E|$ edges, and the edges are generated in the following fashion: for the $i$th edge, randomly choose one ${\cal U}_i∈V$ and then randomly choose one ${\cal V}_i∈V$ where ${\cal U}_i,{\cal V}_i$ are random variables and $i=1,…,|E|$. Since it is pseudo-graph with self-loops, then each choice of vertex can be assumed to have no impact on future choices, i.e. all choices of vertices are independent, then the generation of these edges are also independent, and

$\mathbb{P}\left( E \right) = \mathbb{P}\left( {{\mathcal{U}_1} = {u_1},{\mathcal{V}_1} = {v_1}, \ldots ,{\mathcal{U}_{\left| E \right|}} = {u_{\left| E \right|}},{\mathcal{V}_{\left| E \right|}} = {v_{\left| E \right|}}} \right) = \mathop \prod \limits_{i = 1}^{\left| E \right|} \mathbb{P}({\mathcal{U}_i} = {u_i})\mathbb{P}({\mathcal{V}_i} = {v_i}) = \mathop \prod \limits_{i = 1}^{\left| E \right|} \mathbb{P}({\mathcal{U}_i} = {u_i},{\mathcal{V}_i} = {v_i}) = {\left( {\frac{1}{{{{\left| V \right|}^2}}}} \right)^{\left| E \right|}} = \frac{1}{{{{\left| V \right|}^{2\left| E \right|}}}}$

Vertex "Membership"

Now we can assign each vertex a number in $1,...,k$ and thus partition the graph vertices into $k$ disjoint sets, which we can call "groups", the number can be named "membership" of each vertex. We use a function $z$ to denote the labeling, and $z_v$ is the membership of vertex $v$.

Given $z$, we know the number of vertices of each group, denoted by $n_i,i=1,...,k$. Let

$n_{i,j}=\mathop \sum \limits_{u,v \in V} {\mathbb{I}_{{z_u} = i,{z_v} = j}}$

where $\Bbb I$ is an identity function using the subscript as the condition, then this is the maximum number of possible "unique" edges from group $i$ to group $j$.

Suppose a pseudo-graph is generated in the way mentioned above. Now randomly draw an edge $({\cal U},{\cal V})$ from the generated graph. The knowledge of z does not affect $\mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v|z} \right)$, i.e.

$\mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v|z} \right) = \mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v} \right)$

then we have

$\begin{gathered} \mathbb{P}\left( {{z_\mathcal{U}} = i,{z_\mathcal{V}} = j{\text{|}}z} \right) = \mathop \sum \limits_{u,v \in V} \mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v,{z_u} = i,{z_v} = j{\text{|}}z} \right) \hfill \\ = \mathop \sum \limits_{u,v \in V} \mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v|z} \right){\mathbb{I}_{{z_u} = i,{z_v} = j}} = \mathop \sum \limits_{u,v \in V} \mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v} \right){\mathbb{I}_{{z_u} = i,{z_v} = j}} \hfill \\ = \mathop \sum \limits_{u,v \in V} \frac{1}{{{{\left| V \right|}^2}}}{\mathbb{I}_{{z_u} = i,{z_v} = j}} = \frac{{{n_{i,j}}}}{{{{\left| V \right|}^2}}} \hfill \\ \end{gathered}$

where $\mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v,{z_u} = i,{z_v} = j{\text{|}}z} \right) = \mathbb{P}\left( {\mathcal{U} = u,\mathcal{V} = v|z} \right){\mathbb{I}_{{z_u} = i,{z_v} = j}}$ since $z_u,z_v$ are determined by $z$.

My problem

Suppose we now can observe the whole generated edge set $E$, and let $e_{i,j}$ be the actual number of edges from group $i$ to group $j$. Still randomly draw an edge $({\cal U},{\cal V})$ from the graph, show

$\mathbb{P}\left( {{z_\mathcal{U}} = i,{z_\mathcal{V}} = j{\text{|}}{{z}},E} \right) = \frac{{{e_{i,j}}}}{{\left| E \right|}}$

This is very intuitively true, but I have difficulty showing it rigorously as showing $\mathbb{P}\left( {{z_\mathcal{U}} = i,{z_\mathcal{V}} = j{\text{|}}z} \right) = \frac{{{n_{i,j}}}}{{{{\left| V \right|}^2}}}$ above.

Thanks a lot!

• The calculation of $P(E)$ is wrong. The generation considers order, but $P(E)$ should not consider order. Suppose $m-1$ edges are placed between some $u,v$ with the remaining one be placed between another pair $w,z$. Here $w,z$ could be anywhere in the sequence, with the generated E be the same. – Tony Feb 28 '17 at 23:45