Let $G:=(V,E)$ be an undirected, connected graph with $n:=|V| \geq 2$ nodes and a real number $0 < p < 1$. Initially, two nodes in $G$ are black, the other $n-2$ nodes are white. We consider the following stochastic process: at each step, an edge of the graph is selected uniformly at random from the set of edges. With probability $p$, the colors of the nodes of the edge are swapped. One can imagine that the nodes swap positions. With probability $1-p$, if both nodes of the edge are black, we consider that they have "met" and stop the process; else, we do nothing.
Is there a nice upper bound for the expected time until the two black nodes will meet? Using discrete Markov chains, I managed to prove the bound $O(|E|^d)$, where $d$ is the diameter of the graph. However, I suspect that this can be greatly improved. I would also appreciate any pointers to useful or related literature.
By the way, this is a question that arised in my work on a more general and complicated problem. I find the question quite interesting in itself and therefore decided to post it here.