I'm looking at the mean time from equilibrium for a random walk on different kinds of graphs. Right now, I'm working through at a prism graph of $n$ sides and trying to find some closed form [empirical, not proved] so I can gain a little understanding of the process.
Mean time from equilibrium works something like this: given a uniformly random starting vertex on a graph, how long is the expected random walk from the starting to a chosen target vertex. I think it's something like hitting time, but averaged over all nodes in the graph.
I'm a programmer by trade, so when I thought about this problem, I converted it into a linear algebra problem instead, and I got exact solutions with Sage for a given number of sides. [FWIW, my basic process was to write an equation for the hitting time of each vertex of the graph in terms of other verticies, realize they are a linear system of equations, then convert them into matrix form.]
The values are for $n=3,4,5,6...$ are:
$$\frac{47}{10}, \frac{29}{4}, \frac{393}{38}, \frac{279}{20}, \frac{2565}{142}, \frac{635}{28}, \frac{14731}{530}, \frac{27931}{836}, \frac{78183}{1978}, \frac{11997}{260}, \frac{393153}{7382}, \frac{708821}{11644}, \frac{380137}{5510},...$$
It feels polynomial, so I used numpy to fit some polynomial to it. It appears 'close' to the polynomial $$\frac{n^2+2n\sqrt{3} - 1}{4}$$ where $n$ is the number of sides. The error term seems to drop off exponentially if I plot it, but it's not 'perfectly' exponential, i.e, I can't fit some values $a,b$ such that the error is $e^{an+b}$. In addition, I'm intrigued that a polynomial including a square root term ends up approximating this series of rational numbers. I remember being surprised at the same thing with the Fibonacci sequence, so I tried fitting the error to the sum of two exponential functions (like $e^{ax+b}+e^{cx+d}$) but it doesn't fit any better.
This question can be answered in a few different ways [with different levels of satisfaction]
- What kinds of functions could I use to try to 'fit' the error term, or the sequence as a whole?
- What is the closed form?
- Is there a proof and an intuition of this closed form?
P.S. I'm quite happy to go into more detail for any part of the question, I just have no idea what might be useful information.
A prism graph $G$ of $n$ sides is the Cartesian product of a cycle graph $C_n$ with a path graph $P_2$. Let's label the vertices of $P_2$ by $\uparrow$ and $\downarrow$ and the vertices of $C_n$ by $0$ to $n-1$, and assume w.l.o.g. that your target vertex is $(0,\uparrow)$.
We can divide every sequence of steps into groups consisting of one step along $C_n$ preceded by any number of up or down steps along $P_2$. The random walk on $G$ thus induces a random walk on $C_n$.
Denote the expected number of steps on $G$ per step on $C_n$ by $x$. To take a step on $G$ we need $1$ step on $C_n$ with probability $\frac23$ and $1+x$ steps on $C_n$ with probability $\frac13$, so $x=\frac23+\frac13(1+x)$, so $x=\frac32$. So on average each step on $C_n$ takes $\frac32$ steps on $G$.
To get to your target, you first of all need to get to $0$ on $C_n$, ignoring for now where you are on $P_2$. It's a well-known result (that you can readily check by checking that it satsifies the linear recurrence that you know how to set up) that the expected number of steps to reach vertex $0$ in a random walk on $C_n$ starting from $k$ is $k(n-k)$. Your initial $k$ is uniformly distributed, so this yields an expected
$$ \frac1n\sum_{k=0}^{n-1}k(n-k)=\frac{n^2-1}6 $$
steps on $C_n$. By linearity of expectation, we can scale this up by the factor $\frac32$ to get the expected number of steps on $G$, $\frac{n^2-1}4$. That explains one half of your result.
Now we're at $0$ on $C_n$. We started out with a uniform distribution on $P_2$, which is invariant under the random walk, so we still have a uniform distribution on $P_2$. Thus, with probability $\frac12$ we're done, and with probability $\frac12$ we still have to get from $(0,\downarrow)$ to $(0,\uparrow)$.
Let $L$ denote the expected length of the walk from $(0,\downarrow)$ to $(0,\uparrow)$, and think of this walk as a sequence of attempts, each of which succeeds if it reaches $(0,\uparrow)$ and fails if it returns to $(0,\downarrow)$. With probability $\frac13$, we immediately succeed. With probability $\frac23$, we go to one of the other two neigbours of $(0,\downarrow)$. Then we have to take another random walk on $C_n$ until we get back to $0$. That takes us $n-1$ steps on $C_n$, and thus $\frac32(n-1)$ steps on $G$. Adding the $1$ step we take in either case yields a total of $1+\frac23\cdot\frac32(n-1)=n$ expected steps so far.
Now we need the probability for returning to $(0,\downarrow)$ instead of reaching $(0,\uparrow)$. With every step we take on $C_n$, we have a probability $\frac14$ of switching sides on $P_2$ beforehand. Thus our initial probability of $1$ of being on $\downarrow$ decays towards $\frac12$ as $\frac12+\frac12\left(\frac12\right)^j$ when we take $j$ steps on $C_n$.
Here comes the part where we disregard terms that decay exponentially with $n$. We'll sum the decaying part of this probability as if $C_n$ were infinite and we couldn't wrap around to the origin. That introduces an error of order $2^{-n}$, since the probability has decayed by at least that much before we wrap around.
Now we just have to count the paths that lead from $1$ to $0$ and sum over the corresponding powers of $\frac12\cdot\frac12=\frac14$ (where one factor comes from the probability of going right or left and the other factor comes from the exponential decay in the probability.) The number of paths starting at $1$ that hit $0$ for the first time after $2j+1$ steps is $C_j$, the $j$-th Catalan number. (The notational confusion due to the fact that both the cycle graphs and the Catalan numbers are conventionally denoted by $C$ shouldn't be too great, as they appear in quite different contexts.) Thus the probability to return to $(0,\downarrow)$ is
$$ \frac12+\frac12\sum_{j=0}^\infty4^{-(2j+1)}C_j\;. $$
The series is $\frac14$ times the generating function of the Catalan numbers, evaluated at $\frac1{16}$. The generating function of the Catalan numbers can be shown to be
$$ \sum_{n=0}^\infty C_nx^n=\frac{1-\sqrt{1-4x}}{2x}\;. $$
Thus, with probability
$$ \frac12+\frac18\cdot\frac{1-\sqrt{1-4\cdot\frac1{16}}}{2\cdot\frac1{16}}=\frac{3-\sqrt3}2 $$
we return to $(0,\downarrow)$ and have to try again, taking another expected $L$ steps. That yields a linear equation for $L$,
$$L=n+\frac23\cdot\frac{3-\sqrt3}2\cdot L=n+\left(1-\frac1{\sqrt3}\right)L\;,$$
with solution $L=\sqrt3n$. Since the probability of getting to $(0,\downarrow)$ in the first place was $\frac12$, this yields the additional term $\frac{\sqrt3}2n$ in your result.
The fact that we went through some more complicated expressions to get this simple result suggests that there might be a more elegant way to do this :-)