There are n cities. Each of the cities may have a one-way road toward another city.Sometimes a road will exist,sometimes it won't!
Given the description of all the cities and roads and the probability of each road's existence, how to determine the expected number of cycles formed?
For Example:
In this graph, answer is $0.72$.
Label the nodes $1,2,\ldots,n$ and for each pair of nodes $i,j,\;$ let edge $ij$ exist with probability $p_{ij}\equiv p_{ji}$.
Then, for each triplet of nodes $i,j,k$ with $1\leq i\lt j\lt k\leq n,\;$ for every permutation of every, possibly empty, subset of the node set $\{i+1,\;i+2,\ldots,n\} \setminus \{j,k\},\;$ which we label $n_1,n_2,\ldots,n_m,\;$ we have a unique cycle $"i,j,n_1,n_2,\ldots,n_m,k,i"$ with probability of existence equal to $$p_{ij}\cdot p_{jn_1}\cdot p_{n_1n_2}\cdot p_{n_2n_3}\cdot\ldots\cdot p_{n_{m-1}n_m}\cdot p_{n_mk}\cdot p_{ki}.$$
The expected number of cycles is the sum of all such expressions.
Example:
Four nodes: $1,2,3,4$. The possible cycles and their probabilities:
\begin{eqnarray*} 1,2,3,1\quad &&\quad p_{12}\cdot p_{23}\cdot p_{31} \\ 1,2,3,4,1 &&\quad p_{12}\cdot p_{23}\cdot p_{34}\cdot p_{41} \\ 1,2,4,1\quad &&\quad p_{12}\cdot p_{24}\cdot p_{41} \\ 1,2,4,3,1 &&\quad p_{12}\cdot p_{24}\cdot p_{43}\cdot p_{31} \\ 1,3,4,1\quad &&\quad p_{13}\cdot p_{34}\cdot p_{41} \\ 1,3,4,2,1 &&\quad p_{13}\cdot p_{34}\cdot p_{42} \cdot p_{21} \\ 2,3,4,2\quad &&\quad p_{23}\cdot p_{34}\cdot p_{42} \\ \end{eqnarray*}
Sum all these values for the expected number of cycles.