9
$\begingroup$

I'm considering a simple random walk on a cycle graph comprising a number of vertices, labelled $1$ to $5$ consecutively. Suppose I start at vertex 1 and can traverse to either side ($2$ or $5$). I continue this random walk until I have covered all vertices. What is the probability that I finish on node $3$, and the expected number of steps to get there? How do I calculate the same quantities if I finish on the other vertices? How do I generalise to say $n$ vertices?

I have seen multiple resources discussing the cover time on a cycle graph, but in this context, I guess I have to include a discussion on either stopping time after visiting all vertices (which I don't really know how to include here, perhaps via a conditional probability) or transforming the end state as an absorbing state (which I guess won't make it a Markov chain anymore). I also suspect that for the first part (ending on node 3) we can exploit symmetry, but I'm not sure how. What should I do here? Thanks!

Edit: after simulating this, I've noticed that the probabilities of ending at any node is $1/4$. The expected number of steps terminating at $3$ (or $4$) should be $11$, and the expected number of steps terminating at $2$ (or $5$) should be $9$.

$\endgroup$
7
  • $\begingroup$ The modelization of the fact that all vertices are traversed isn't evident... $\endgroup$
    – Jean Marie
    Oct 11, 2021 at 14:45
  • $\begingroup$ @JeanMarie sorry i don't understand what you mean by that $\endgroup$
    – Ice Tea
    Oct 11, 2021 at 14:49
  • $\begingroup$ In other words, how do you express that every vertex must be traversed ? $\endgroup$
    – Jean Marie
    Oct 11, 2021 at 15:00
  • 1
    $\begingroup$ @JeanMarie that is exactly the premise of what I am trying to ask :) $\endgroup$
    – Ice Tea
    Oct 11, 2021 at 19:48
  • 1
    $\begingroup$ You should be interested by this. $\endgroup$
    – Jean Marie
    Oct 13, 2021 at 9:11

3 Answers 3

2
+100
$\begingroup$

Look at my comment under

This problem can be decomposed as several mini problems. Each of these mini problems are versions of a common expected value problem which looks something like a line of lily pads numbered $0,1,\ldots n$ with a frog starting on $k\in (0,n]$ and something bad (like a crocodile) on lilypad $0$ and something good (like food) on lilypad $n$.

Let's call the expected value of the number of steps it takes the frog to reach $n$ when starting from $k$ as $E(k,n)$. We get the following system of equations using states (assuming $n\geq 2$) $$\begin{cases} E(1,n)=1+E(2,n)\\ E(x,n)=1+\frac{1}{2}E(x-1,n)+\frac{1}{2}E(x+1,n)~\forall x\in [2,n-1]\\ E(n,n)=0\end{cases}$$

We can see that $E(x,n)$ has a really nice recursion for the non-edge cases (if $a_x=E(x,n)$, then $a_x-3a_{x-1}+3a_{x-2}-a_{x-3}=0$) We also have $3$ "initial" conditions ($E(1,n)=1+\frac{1}{2}E(2,n)$, $E(n,n)=0$, and $2E(x,n)-E(x-1,n)-E(x+1,n)=2$). We can use the properties of linear recurrences to conclude that $E(x,n)$ will be some quadratic polynomial in $x$. Let's say $E(x,n)=ax^2+bx+c$ (the constants $a,b,c$ will likely be dependent on $n$).

From the recursion, we have that $$2E(x,n)-E(x-1,n)-E(x+1,n)=2$$ $$(E(x,n)-E(x-1,n))-(E(x+1,n)-E(x,n))=2$$ $$(2ax+b-1)-(2ax+2a+b-1)=2$$ $$-2a=2$$ $$a=-1$$ So $E(x,n)=-x^2+bx+c$. Now we also have $$\begin{cases} E(1,n)=1+E(2,n)\\E(n,n)=0\end{cases}$$ $$\begin{cases} -1+b+c=1+(-4+2b+c)\\-n^2+bn+c=0\end{cases}$$ $$\begin{cases} b=2\\c=n^2-bn\end{cases}$$ $$\begin{cases} b=2\\c=n^2-2n\end{cases}$$ Hence, we have $\boxed{E(x,n)=-x^2+2x+n^2-2n}$. This result will be useful for the rest of the problem

There is also another problem we need to solve that will be useful. This is the probability that given lilypads numbered $0,1,\ldots n$ with a frog at $x$, what is the probability that they will go to $n$ before going to $0$. If we call this probability $P(x,n)$, we get a similar system of equations using states (assuming $n\geq 2$) $$\begin{cases} P(0,n)=0\\ P(x,n)=\frac{1}{2}P(x-1,n)+\frac{1}{2}P(x+1,n)~\forall x\in [1,n-1]\\ P(n,n)=1\end{cases}$$ Using a similar approach as previously, we can use the fact that there is a nice recursion for $P(x,n)$ to see that $P(x,n)$ must be a linear polynomial in $x$. Hence, we have $P(x,n)=ax+b$ Since $P(0,n)=0$ and $P(n,n)=1$, we can quickly see that $\boxed{P(x,n)=\frac{x}{n}}$.

Back to the original problem, to finish on $3$, you must first get to $2$ or $4$. Then you must go to the other of $2$ or $4$. Then you must go to $3$.

The only decision we have to make is whether to go to $2$ or $4$ first. After we have made this decision, there are no more decisions left to make so that we achieve our goal of finishing on $3$

Let's say that we choose to go to $2$ before going to $4$. We can treat $4$ as the $0$ lilypad and $2$ as the $n$ lilypad. The probability that we actually choose this path of going to $2$ before going to $4$ is $P(2,3)$. The expected number of steps to get to $2$ is $E(2,3)$.

From there, we must go to $4$ without going to $3$. The expected number of steps to do that is $E(1,4)$. From there we simply need to go to $3$ anyway possible. We can't actually use any of the formulae we derived above, but this is a straightforward application of states with a lot of symmetry. So I'll leave it as an exercise to the reader to prove that the expected number of steps to do this is $4$.

Now we deal with the case that we choose to go to $4$ before going to $2$. We can treat $2$ as the $0$ lilypad and $4$ as the $n$ lilypad. The probability that we actually choose this path of going to $4$ before going to $2$ is $P(1,3)$. The expected number of steps to get to $4$ is $E(1,3)$.

From there, we must go to $2$ without going to $3$. The expected number of steps to do that is $E(1,4)$. From there we simply need to go to $3$ anyway possible. As before, the expected number of steps to do this is $4$.

In total, the expected number of steps to execute this 2-part procedure is $$P(2,3)(E(2,3)+E(1,4)+4)+P(1,3)(E(1,3)+E(1,4)+4)$$ $$=\frac{2}{3}(3+9+4)+\frac{1}{3}(4+9+4)$$ $$=\frac{32}{3}+5$$ $$=\frac{47}{3}$$

Similarly, it's not hard to see that the probability you end on $3$ is $$P(2,3)P(1,4)(1)+P(1,3)P(1,4)(1)$$ $$=P(1,4)(P(2,3)+P(1,3))$$ $$=\frac{1}{4}$$

Code for finding expected number of steps to end on 3. Should return approximately 11 if trials is high enough

def f1(trials):
    successful_trials = 0
    total_steps = 0
    for i in range(trials):
        steps = 0
        pos = 1
        unvisited = [0,2,4]
        while(pos % 5 != 3):
            pos += get_random_step()
            steps += 1
            if pos % 5 in unvisited:
                unvisited.remove(pos % 5)
        if unvisited == []:
            successful_trials += 1
            total_steps += steps
    return total_steps/successful_trials

Code for finding $E(x,n)$

def f2(x,n,trials):
    successful_trials = 0
    total_steps = 0
    for i in range(trials):
        steps = 0
        pos = x
        while(pos != n and pos != 0):
            pos += get_random_step()
            steps += 1
        if pos == n:
            successful_trials += 1
            total_steps += steps
    return total_steps/successful_trials
$\endgroup$
9
  • $\begingroup$ This is not a correct solution, as I also agree with the simulated answer of $11$. I'm just putting this in here to give people ideas. I've been simulating some of the other aspects of this code, and it looks like my flaw is in my definition of $E(x,n)$. For some reason, when I simulate $E(x,n)$ I am getting that $E(x,n)\neq 1-\frac{1}{2}E(x-1,n)-\frac{1}{2}E(x+1,n)$. I'm not sure why this is the case, but if I had to guess, it could possibly be because the fact that the jumping stops when the frog reaches 0 is a nonstandard aspect of the states method, and I might be incorrect in doing it $\endgroup$ Oct 12, 2021 at 4:58
  • $\begingroup$ the minusses in the formula here are typos, right? $\endgroup$ Oct 13, 2021 at 8:24
  • $\begingroup$ @PeterKeller oops, those are typos, I can't edit it now. I meant, that when I simulated $E(x,n)$ I am getting $E(x,n)\neq 1+\frac{1}{2}E(x-1,n)+\frac{1}{2}E(x+1,n)$ $\endgroup$ Oct 14, 2021 at 0:14
  • $\begingroup$ I had some time to look through the problem, too. My computation resulted in $E(x,n)=x(n-x)$. This is the number of steps a symmetric random walk takes on average to a leave a subset with n-1 states, being absorbed in either 0 or n. The problem is then solved by noting that the expected time to visit all states is a sequence of such ruin problems as stated in the answer above. Starting at some arbitrary state, the number of steps until covering is then $1+2+3+4=10$. This is supported by simulation. I guess Alan had 11 because he counted arriving at the first state as an extra step (my guess). $\endgroup$ Oct 14, 2021 at 10:59
  • $\begingroup$ @PeterKeller How did you get that $E(x,n)=x(n-x)$, or do you have any resources on this? I also don't think that my simulation for $E(x,n)$ agrees with your formula. I will edit my post to share my code. I don't think that I counted an extra step, but you can see for sure now. Also, assuming that your formula for $E(x,n)$ is correct, if I continue my approach with the final answer being $P(2,3)(E(2,3)+E(1,4)+4)+P(1,3)(E(1,3)+E(1,4)+4)$, I am getting $\boxed{9}$. $\endgroup$ Oct 14, 2021 at 15:11
2
$\begingroup$

I'd like to propose another approach, based on the graph being the $N$-cycle.

First, let's fix the notation making it more standard.

We assume that the vertices are $0,1,\dots,N-1$ and that the walker begins from $0$. The RW is symmetric, meaning the transition function is of the form $p(i,i+1 \mod N) = \frac 12 = 1-p(i,i-1 \mod N)$.

Theorem. The distribution of the last hit vertex is uniform on $\{1,\dots, N-1\}$.

Proof Fix any vertex $j\in \{1,\dots,N-1\}$. Now consider the graph obtained by removing the state $j$. This is an "interval", a line graph with $N-1$ vertices, $\{j+1 \mod N,\dots,-1 \mod N,0,1,\dots, j-1\}$

Let $\sigma$ be the time until the walk on the cycle, starting from $0$ hits an endpoint of the interval, namely until the walk hits $j-1$ or $j+1 \mod N$.

Now $j$ will be the last vertex to be hit by the walk if and only if after $\sigma$, the walk will hit the other endpoint before hitting $j$.

Since:

  1. the walk is symmetric; and at time $\sigma$ is

  2. a. $N-2$ units from the other endpoint (remember that the interval has $N-1$ elements in it);

  3. b. $1$ unit from $j$, in the opposite direction. the position of the walk at time $\sigma$ is one unit away from $j$;

We conclude that the probability of $j$ being hit last is independent of $j$, and is the same as the probability of the walk starting from (say) $0$ to hit $N-2$ before hitting $N-1$ (much simple to draw) Since we have $N-1$ choices for $j$, the result follows. $\Box$

Expectation I'll consider the expectation of the cover time conditioned on $j$ hit last. I will only outline analysis leading to an answer. All calculations reduce to standard recurrence relations on the integers.

Let $\rho$ be the cover time. We are looking at its distribution conditioned on $j$ hit last. This is an independent sum of the following:

  1. $\sigma$: time to hit one of the endpoints of the interval above, starting from $0$.
  2. $\rho_1$: starting from that endpoint, time to hit the other endpoint, conditioned it happens before hitting $j$ (note: both endpoints are neighbors of $j$). Regardless of the choice of $j$, this has the same distribution the time to hit $N-2$ before hitting $N-1$, starting from $0$.
  3. $\rho_2$: starting from an endpoint, time to hit $j$ (remember that both endpoints are neighbors of $j$). This has the same distribution as time to hit $N-1$, starting from $0$.

Note that $\sigma+\rho_2$ has the same distribution as time $j$ is first hit starting from $0$ (start from zero, hit one of the endpoints, and then hit $j$), so effectively it is only two recurrence relations one needs to solve.

Also, only the distribution of $\sigma$ depends on $j$, the other two are the same for all $j$.

$\endgroup$
0
1
$\begingroup$

Continuing the discussion with Alan (see his answer above) I would like to present the approach here for the computation of the cover time. I am basically following the ideas of Lovász [Lov93] as presented in "Markov Chains and Mixing Times", Levin et al, Chapter 11, Example 11.1 along with the formula we will derive at the end.

If we have a symmetric Random Walk $(X_n)_{n\geq0}$ on $\mathbb Z/n$ (cycle graph), where $n\geq 1$, we can ask for the expected time to visit all the $n$ states at least once. The counting stops when we reach the last new state for the first time. Let us call this time $\tau^n_{cov}$ (cover time).

Further we can assume that we start with probability $1$ in some given state. Then the RW visits a new state in the next step, as we can not stay where we began. We then have two options: either we leave this set of two already visited states to left or to the right. For example, if we started in 0, and the next state was 1, we either go directly to the new state 2, or we travel via 0 to n-1. Directly after, we again wait until the RW has left the set of now three states at either end. And so on. This is the classic situation of computing the number of games before a gambler either is ruined or beats the opponent. We call this ruin time $\tau^{(r,n)}$. For that we can use first-step-analysis. Let $f_n(k):=\mathbb E(\tau^{(r,n)}|Z_0=k)$.

We can now think of a state space $\{0,1,2,\ldots,n\}$, where $n$ and $0$ are absorbing.

We get: $$f_n(0)=0$$ $$f_n(1)=1+\frac12f_n(0)+\frac12f_n(2)=1+\frac12f_n(2)$$ $$...$$ $$f_n(k)=1+\frac12f_n(k-1)+\frac12f_n(k+1)$$ $$...$$ $$f_n(n)=0$$

Like in the answer by Allan, we assume that $f_n(k)$ is a quadratic polynomial, such that $f_n(k)=a\cdot k^2+b\cdot k+c$ with real numbers $a,b,c$ yet unknown.

Using $f_n(0)=0$ we get immediately $c=0$. After this reduction we just need to solve the system of equations above for general $k, 1\leq k\leq n-1$:

$$ak^2+bk=1+\frac12(k-1)(a(k-1)+b)+\frac12(k+1)(a(k-1)+b)=1+a(k^2+1)+bk$$

Luckily this reduces after some simple algebra to just $a=-1$.

Now we have $f_n(k)=-k^2+bk$ and need to find the value of $b$. For that, we use the case for $k=n$, which gives:

$$f_n(n)=-n^2+bn=0\Leftrightarrow b=n$$

Finally, we have found $f_n(k)=-k^2+nk=(n-k)k$. Indeed, we actually need to evaluate the function only at $k=1$ or equivalently at $n-1$, as we always start at the boundary.

Now we can combine both results. If we have in total n states in the cycle graph: $$\mathbb E[\tau^n_{cov}]=\sum_{i=2}^{n}f_i(1)=\sum_{i=2}^{n}(i-1)1=\sum_{i=1}^{n-1}i=\frac12n(n-1)$$

Either way, for the original question, we get exactly $\mathbb E[\tau_{cov}]=1+2+3+4=\frac125*4=10$.

Since all the states except the first one, are equally likely to be the last, the number of steps to reach 3 takes on average 10 steps, unless of course we had started in 3.

A simulation confirms that. All states exept the first one are equally likely to be the last. A histogramm confirms the uniform distribution over all non-starting states.

With 100000 samples I got an estimate of 9.97144 for the cover time and this for the distribution on the end states: [0.24762, 0.25162, 0.2512, 0.24956]

[Lov93] On the last new vertex visited by a random walk, Lovász and Winkler, Journal of Graph Theory 17, p 593-596

If needed the code i used in Processing (JAVA)

ArrayList<Integer> visitedStates = new ArrayList<Integer>();

int firstState; 
int currentState; 
int expSteps=0; 
float sum = 0; 
float samples = 100000; 
int[] hist = new int[4];

for(int i = 0; i < samples; i++) { 
  visitedStates.clear();   firstState = 1;
  currentState = firstState;
  expSteps = 0;
  visitedStates.add(firstState);

  while(visitedStates.size() != 5) {
    float theta = random(0,1);
    
    if(theta > 0.5) {
      currentState += 1;
    }
    else {
      currentState -= 1;
    }
    
    if(currentState<1) { currentState = 5; }
    if(currentState>5) { currentState = 1; }
    
    if(!visitedStates.contains(currentState)) {
      visitedStates.add(currentState);
    }
    expSteps++;   
  }
  hist[currentState-2] += 1;
  sum += expSteps; 
}

println(sum/samples); 
println(hist[0]/samples +", " + hist[1]/samples
+", " + hist[2]/samples + ", " + hist[3]/samples);

Some extra notes:

With some adaptions, we can also see what the expected number of steps until cover with respect to some given end state is.

For that we something more. Assuming, we start in state 1 we either go to {1,2} which is neighbouring 3. Therefore we have to leave that subset via 1 to 5. The other case is {1,5}, then it is not important to which other state we go next, as both are not 3. The complete case study is displayed in the image. Red subsets are neighbouring 3 only on one side.

Diagram of covering

We therefore need to compute the average number of games in a symmetric gambler's ruin chain if condition the process to ruin in the end. We assume again a state space of the natural numbers from 0 to some fixed n. In this situation 0 and n are absorbing.

Let $\tau_R$ be the (stopping) time until ruin (time to reach 0). We know that the event $\{\tau_R<\infty\}$ is equivalent to the event of ruin at some point in the future.

For given $i,j\in\{1,\ldots,n-1\}$ we can compute the following conditional probability: $\mathbb P(X_n=j| \tau_R<\infty, X_0=i)$.

In this form it is not very handy, but we can simplify the expression:

$$\mathbb P(X_n=j|\tau_R<\infty,X_0=i)=\frac{\mathbb P(\exists m\geq0:X_{n+m}=0|X_n=j)}{\mathbb P(\exists m'\geq0:X_{n+m'}=0|X_n=i)}\cdot\mathbb P(X_n=j|X_0=i)$$ $$=\frac{\mathbb P(\tau_R<\infty|X_0=j)}{\mathbb P(\tau_R<\infty|X_0=i)}\mathbb P(X_n=j|X_0=i)$$

The ratio of probabilities is actually known, as these are just the ruin probabilities that Alan computed. Therefore
$$\mathbb P(\tau_R<\infty|X_0=k)=1-\frac kn$$ and therefore

$$\mathbb P(X_n=j|\tau_R<\infty,X_0=i)=\frac{n-j}{n-i}\mathbb P(X_n=j|X_0=i).$$

In particular, if we assume time homogeneity (as we did in the previous computation), we also get for a single step: $$\mathbb P(X_1=j|\tau_R<\infty,X_0=i)=\frac{n-j}{2(n-i)}.$$

This transforms the problem now into a simple absorption problem. Note, the probability to go from state n-1 to n is now zero. Naturally, one could swap the roles of 0 and n, as everything is symmetric.

To compute the average absorption time we simply follow the same approach as before using first step analysis. Let $g(i)=\mathbb E[\tau|X_0=i]$ where $\tau$ is now the absorption time in the new system.

$$g(0) = 0$$ $$g(k)=1+ \frac{n-k+1}{n-k}g(k-1)+\frac{n-k-1}{n-k}g(k+1)$$ $$g(n-1)=1+g(n-2)$$

The last equation states that we have to go to n-2 if we are in n-1, as now going to n is not allowed anymore. I have not bothered to find the general solution to this.

In any case, we just need to solve this for $n=3$ and $n=4$. Escaping to 0 in the first case is on average 8/3 if started in n-1, and in the second case we get 5.

Now we just need to notice that in the above diagram the transition from one set to another are determined just by either the probability to leave or to leave at one side starting at a boundary state.

$\endgroup$
8
  • $\begingroup$ It looks like we interpreted the covertime differently. I thought it was asking for the expected number of steps to reach each node with the restriction that it ends at $3$. While it looks like you thought it was asking for the expected number of steps to reach each node without caring for what the ending state is on. $\endgroup$ Oct 16, 2021 at 0:07
  • $\begingroup$ I see. My mistake was that i assumed that the expectations would all be the same just because the end state is uniformly distributed. I adapted the simulation. Indeed, it points towards Average Cover Times of 11 for states three and four and 9 for ending in either two or three given we started in one. But then, we need to mix our solutions, don't we? Because, if we first go to state five, then we are in my situation, where it's not important to which side we leave the set {1,5} as three is not a neighbour. But if we first go to two, we are in your case. $\endgroup$ Oct 16, 2021 at 14:29
  • $\begingroup$ PS: But then, we cannot just take first step analysis. We have to condition on the future event that the system is left at a specific site. This explains, why your equation didn't work as you mention in the comment. The problem is that under this condition, the probabilities to go left or right change and are no longer symmetric. Maybe i should add something above. $\endgroup$ Oct 16, 2021 at 14:41
  • $\begingroup$ Ok, sounds interesting. I'm glad we fixed any confusion. Do you have any insight on how we could properly set up the states equation then? $\endgroup$ Oct 16, 2021 at 23:26
  • 1
    $\begingroup$ @PeterKeller it's a question that popped in my head while I was reading about cover times on cycle graphs :) $\endgroup$
    – Ice Tea
    Oct 18, 2021 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .