In a random walk on a directed graph, at each step a new vertex $y$ is chosen from neighbours of the previous vertex $x$ that are connected by outgoing edges $(x, y)$ but not incoming edges $(y, x)$.
I need to prove that we can't do the following:
Assuming that I have a fair coin, and I'm at a certain vertex $u$, let $X$ be the set of nodes adjacent to $u$. I can use the coin to generate a binary number $2^n > |X|$ such that the probability of it corresponding to a particular node is $2^{-n}$. Hence I keep flipping the coin n times till the number I get is $<=$ $|X|$ (All nodes in $|X|$ have an equal probability of showing up, but I'm not sure if this counts as choosing "uniformly at random"?).
I then move to the vertex I get through the coin flips.
Why would this not work in a directed graph? I know that for an undirected graph this would work as a random walk of length $4n^3$ beginning at s visits all vertices in the connected component of $s$ with probability at least $1/2$, so I can use probability amplification to boost the probability for it.
But there's no such theorem for a directed graph, and I'm trying to figure out how to disprove this algorithm for it. Also, Does it help if we allow the random walk to return to the start vertex u specified in the reachability instance, with some probability (at each step)