With a single node $v_1$, at every step $t$ with $1 < t ≤ n$, a single node $v_t$ is added to the graph, together with a single outgoing edge; the destination of the edge is a node chosen uniformly at random among the existing nodes in the graph.
Let $G$ be the graph at the end of time step $n$.
- What is the expected number of edges entering node $v_j$ in $G$? Give an exact expression in terms of $n$ and $j$, as well as an asymptotic expression using $Θ$ notation.
- What is the expected number of nodes with no incoming edges in $G$?
All I know so far is that $G$ cannot have self-loops nor multi-edges.