Let $G=(n,p)$ be a random graph. For example, consider that $G$ is the following graph.
Initially, the edges of $G$ is undirected. A random $id\in R$ is assigned to each vertex of $G$. The $id$ of vertex $v$ is denoted by $id_{v}$. For each edge $e=(v,u)$, if $id_{v}>id_{u}$, $e$ is converted to a directed edge from $u$ to $v$, and if $id_{v}<id_{u}$, $e$ is converted to a directed edge from $v$ to $u$. A root is a vertex which all incident edges are outgoing edges. In the example, $V_{1}$ is a root.
Let $r$ be a root and $v$ be a none-root vertex which has the longest directed distance ($d_{r,v}$) from $r$. What is the expected value of $d_{r,v}$?
In the example, $d_{V_{1},V_{2}} = 1, d_{V_{1},V_{3}} = 1,d_{V_{1},V_{4}} = 1,d_{V_{1},V_{5}} = 2$, so $V_{5}$ is a non-root vetex which has the longest directed distance from the root.
The following solution is my solution. But I can't compute some parts of it. Is there another solution?
There are $P(n,d_{r,v}-1)$ potential different paths with length $d_{r,v}$ from $r$ to $v$. The paths are labeled with numbers $1,...,P(n,d_{r,v}-1)$. The vertices of $i$th path are donoted by $r=\sigma^{i}_{1},\sigma^{i}_{2},...,\sigma^{i}_{d_{r,v}},\sigma^{i}_{d_{r,v}+1}=v$. $X_{i}\text{ }(1\leq i\leq P(n,d_{r,v}-1))$ is a random variable such that
\begin{align}
X_{i}=\begin{cases}
1 \quad\text{$i$th potential path, $\sigma^{i}$, is a valid path from $r$ to $v$.}\\
0 \quad\text{o.w.}
\end{cases}
\end{align}
Thus, $E[d_{r,v}]$ is as follows
$$E[d_{r,v}] = \sum_{i=1}^{P(n,d_{r,v}-1)}E[X_{i}]$$
What remains is computing $\Pr(X_{i}=1)$. $X_{i}=1$ when
- There is a path from $r$ to $v$. The probability of it is $p^{d_{r,v}}$.
- The $id$s of the path's vertices are monotonically increasing. The probability of it is $\frac{1}{(d_{r,v}+1)!}$.
- There is no edge from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+2}$ ($1\leq j\leq d_{r,v}-1$), for if there is an edge $(\sigma^{i}_{j},\sigma^{i}_{j+2})$, then the length of the longest directed path from $r$ to $v$ is not $d_{r,v}$ and is $d_{r,v}-1$. The probability of it is $(1-p)^{\frac{(d_{r,v}-1)(d_{r,v}-2)}{2}}$.
- There is no path with length one from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+3}$ ($1\leq j\leq d_{r,v}-2$). I can't compute it's probability!
There is no path with length two from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+4}$ ($1\leq j\leq d_{r,v}-3$). I can't compute it's probability!
...
