Let $G = (V,E)$ be a connected graph. Now consider a random walk on $G$, where we pick a random vertex $v_0$ sampled uniformly at random from $V$. Let $v_i \in V$ denote the vertex in the current iteration. In iteration $i$ we either stay at $v_i$ and terminate with probability $1-p$ or uniformly at random select a random vertex from the neighborhood of $v_i$.
Can anything be said about the expected number of iterations? For a fixed length walk of length $k$ this of course the expectation of the Binomial distribution.
I feel that your problem is quite similar to randomised gossip algorithm. So you can read paper "S. Boyd, randomized gossip algorithm, IEEE Trans. on Information Theory, 2006", in which the number of iterations is formulated as a function of the pre-defined error. Hope that it will help you. Best.