0
$\begingroup$

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.

Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple edges and self-loops aren't allowed). Let $p$ is a probability that that for any given node $v_i$ there is an edge from this node to node $v_{k\ne i}$, $p<1$.

What is an expected numbers of cycles $<l_k>$ and closed walks $<w_k>$ of length $k$ on this graph?

Thanks!!!

$\endgroup$

1 Answer 1

1
$\begingroup$

For a given sequence $v_1, \ldots, v_k$ of distinct vertices, the probability that this is a cycle (i.e. that all $v_i v_{i+1}$ and $v_k v_1$ are edges) is $p^k$. There are $N!/(N-k)!$ such sequences, but each cycle corresponds to $k$ of them, so the expected number of $k$-cycles is $\dfrac{N! \; p^k}{(N-k)!\; k}$.

$\endgroup$
3
  • $\begingroup$ Thank you @Robert. TWhat is bother me that number of cycles length k and number of closed walks with same length should be different, because cycle is restricted to come in same node only once, while close walk can pass same node several times, For example $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_3 \rightarrow v_5 \rightarrow v_1$ $\endgroup$
    – rth
    Aug 12, 2014 at 21:12
  • $\begingroup$ Yes. I didn't try calculating the expected number of closed walks, because it looks complicated (with repetition of edges as well as nodes). $\endgroup$ Aug 12, 2014 at 22:58
  • $\begingroup$ Thank you @Robert. You gave me the answer on half of my question at least. Unfortunately I cannot set + on your answer, because I have very low reputation here :) $\endgroup$
    – rth
    Aug 13, 2014 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.