Consider a tree T with n nodes. A random direction is assigned to each edge uniformly at random independently. A node v is a sink if all the edges incident on v receive direction pointing towards v. Find the expected number of sinks.
I am told that the answer is Ω(n), may I know why?
Tree with $n$ nodes has $n - 1$ edges and so $2n - 2$ pairs (edge, node incident to this edge). If the tree has at least $2/3n$ nodes with degree $3$ or more, it has at least $2/3n \cdot 3 = 2n > 2n - 2$ pairs. Thus number of nodes of degree more than $2$ is at most $2/3n$, and thus number of nodes of degree at most $2$ is at least $1/3n$.
Note that node with degree at most $2$ has probability at least $1/4$ to be a sink. So expected number of sinks is at least $1/3n \cdot 1/4 = 1/12 n = \Omega(n)$.