Thanks, corrected! And yes, that's right, so if you're comfortable arguing from $n^k \leq C_k 2^n$ down to $n^k < 2^n$, then you don't need the compression, but it's a fun trick and it felt in the spirit of the question.

What have you tried? One can start writing down some things using basic facts about the Fourier transform, but it would help to know where the basics are proving insufficient for your desired application.

Do you mean to assume that the graph is weakly connected? If not, then consider, for a counterexample, a graph $G$ with four states $A,B,C,D$, with three edges: a $2$-cycle $A \to B \to A$ and a lone edge $C \to D$. If the graph is weakly connected then I think it's probably true. (I use the convention that $A$ for the $G$ I described has $3$ entries equal to $1$ and $13$ entries equal to $0$.)

@fedja Beautiful! That's quite similar to what I was trying in my answer below, but the analysis of your graph is a lot simpler!

No, probably not! That seems like a good way to prove that what I'm outlining here can't work.

Also -- do you expect this to be true or false, i.e. do you expect a proof or a counterexample? Where did it come from?

The function $f$ is fixed when taking the expectation?

@SamHopkins Yes, $k=1$ is special because a single map generates a commutative monoid; $k \geq 2$ should be different. An average-case version of my question, closer to yours: Fix $k$ and $\ell$. Let $\{ f_1, \dots, f_k \}$ be a set of $k$ distinct maps $[n] \to [n]$ chosen uniformly at random. Let $i_1, \dots, i_{\ell}$ be chosen from $\{ 1, \dots, k \}$ uniformly and independently (both from each other and the $f_i$'s). What is the probability that $f_{i_{\ell}} \circ \cdots \circ f_{i_1}$ is a constant map?

A refinement of the question, since the accepted answer links to a complete solution: suppose you draw your functions instead from the uniform distribution on some subset $\{ f_1, \dots, f_k \}$, where there is some sequence of these $f_i$'s that composes to a constant map. For a given $k$, which sets $\{ f_1, \dots, f_k \}$ will maximize the expected number of compositions required for a constant map? How small does $k/n^n$ have to be before this worst-case expectation is substantially larger than $2n$?