There is a lot of published research on the mean passage passage time (FPT) for random walks on various types of graphs. How about the variance of the FPT and higher momenta? In fact, I would be interested to know for what graphs and random graphs the full distribution of FPTs has been computed analytically in some regime.

For elementary graphs like $K_n$, the full distribution of the FPT is a back-of-the-envelope calculation. For the Erdős–Rényi model in the sparse regime, the full distribution of FPTs has been computed in cond-mat/0410309. I have found other papers about the Erdős–Rényi -- but nothing, for instance, about the FTP distribution in the Barabasi model, or scale-free networks in general.

Perhaps I'm not searching efficiently? If somebody could redirect me, I would be grateful. I'm virtually new to this website, so I can only hope the question is not off-topic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.