Is there a (easy) way to count the (expected) number of random walks of length $k$, in $d$-regular tree with depth $k$, such that they end in the same starting node?
- $d$-regular: degree of each vertex is $d$.
Note that it's asking for "walk" (not path), meaning that you can visit each node multiple times, otherwise the answer would be 1.
Some thoughts:
If we don't have the condition of ending in the same starting node, it should be easy. Since from each node we can transition to $d$ other nodes, the count is $d^k$. However I think this condition complexity changes the nature of the problem.
Another attempt was to use recursion, but I think it doesn't work, because I didn't find a way to decouple probability functions (the events, to be more accurate).