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!
No comments:
Post a Comment