\problemdata
{expectation}
{graphs}
{counting}
{Eric Ho S02}
\begin{problem} Suppose we construct a simple $n$-node graph,
$G=(V,E)$, randomly as follows:

For every set of two distinct vertices $\set{v,v'}$, toss a biased
coin whose probability of coming up heads is $p$.  The undirected edge
between $v$ and $v'$ is included in $E$ iff the coin comes up heads.
Assume that all coin tosses are mutually independent.

A \emph{simple $k$-cycle} in a simple graph is an undirected path
going through each of $k>2$ vertices exactly once and ending where it
started.  A simple $k$-cycle can be represented by the sequence of $k$
vertices $v_1, v_2, \ldots, v_k$ along the path. Note that every
$k$-cycle can be represented by many sequences. For example, the
4-cycle represented by $1234$ is as the same cycle represented by
$2341$ or $3412$ because a cycle does not have to start at any
particular vertex.  It is also represented by $4321$, because the
cycle is undirected.

\begin{problemparts}
\problempart What is the probability that the $k$-cycle represented by
a the sequence $v_1, v_2, \dots, v_k$ exists in $G$?

\solution{A particular $k$-cycle (call it $e$) will occur only if all of
the edges in that cycle exist in the randomly constructed $G=(V,E)$.  Since
each edge is independently added with probability $p$, we have $\pr{e \in
E} = p^k$.}

\problempart What is the total number of distinct possible $k$-cycles?

\solution{ There are $P(n,k)$ ways to choose the elements within the
cycle.  Since it is a cycle, the starting position does not matter,
which means we need to divide the answer by $k$.  In addition, we need
to further divide by two because the orderings of the set of two
vertices $\set{v,v'}$ does not matter.  The result yields $P(n,k)/2k$.
}

\problempart What is the expected number of $k$-cycles in $G$?  (You
may let $X$ denote the answer to part (b) and express your answer in
terms of $X$, $k$, and $p$).

\solution{ Let $I_e$ be the indicator random variable of the event
that a particular $k$-cycle, $e$, occurs.  So the number, $N$, of
$k$-cycles is $\sum_e I_e$ where $e$ ranges over all possible
$k$-cycles, \ie all $k$-cycles in the complete graph on $V$.

We know from a previous part that $\pr{I_e = 1} = p^k$, which means that
$\expect{I_e} = p^k$.  Also, the total number of distinct possible
$k$-cycles is $X \eqdef P(n,k)/2k$.

Therefore
\[
\expect{N} = \sum_e \expect{I_e} = X p^k.
\]
}

\end{problemparts}
\end{problem}
