You begin at a root node that has 2 children. Each of those two children have two more children, and each of those children have two final children (i.e., there are 15 nodes in the graph). How do I find the expected value of how many steps it will take to reach the final children, if at each step the current node moves to the parent node with probability 1/3 and to each child with probability 1/3 (except, of course the root, which just moves to its children)?
I can treat the problem like a random walk in 1d, with each forward step occurring with probability 2/3 and backwards occurring with probability 1/3. However, the root node never moves backward. I'm having trouble reconciling this part with the normal random walk analysis, as well as the different probabilities of forward and backward steps. Thanks!