  The Kemeny's constant $\kappa(G)$ of a connected undirected graph $G$ can be
interpreted as the expected transit time between two randomly chosen vertices
for the Markov chain associated with $G$. In certain cases, inserting a new
edge into $G$ has the counter-intuitive effect of increasing the value of
$\kappa(G)$. In the current work we identify a large class of graphs exhibiting
this "paradoxical" behavior - namely, those graphs having a pair of twin
pendant vertices. We also investigate the occurrence of this phenomenon in
random graphs, showing that almost all connected planar graphs are paradoxical.
To establish these results, we make use of a connection between the Kemeny's
constant and the resistance distance of graphs.
