I currently have two identical expander graphs, each with $n$ vertices, and each vertex has a degree of $d$, where d is a constant. Now, I connect these two expander graphs with a path of length $n$. I want to perform a random walk on this graph. What is the expected convergence time?
Initial state: The starting point is in one of the expander graphs, and the endpoint is in the other expander graph.
Random walk strategy: Randomly select a neighbor and move to that neighbor's location until reaching the endpoint.
My Attempt: While it is well-known that random walk convergence time is typically within $O(\log n)$ on expander graph, I am struggling to determine whether this property can be leveraged to calculate the expected convergence time in this specific scenario.
Thank you very much for all the suggestions and assistance provided.
I think i have found the answer.
Theorem 4 in Aleliunas 1979 states that the expected first hitting time of starting from $x$ to $y$ in connected graph $G$ is bounded by $n^3$, where n is the number of vertices.