Return to Answer

The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.

It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at time $t=\sqrt(n)$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$.

If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p<0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is

• $0$ if $i=j$ or if $|i-j| > 1$
• $p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)
• $1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)

You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$.

The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.

It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at a distance of $n$ on average at time $t=n^2$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$.

If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p<0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$. The drift is $p-(1-p)=2p-1$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is

• $0$ if $i=j$ or if $|i-j| > 1$
• $p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)
• $1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)

You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$.

The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is

• $0$ if $i=j$ or if $|i-j| > 1$
• $p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)
• $1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)

You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$.

If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.

It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at time $t=\sqrt(n)$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$.

If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p<0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$.

The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.

It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at time $t=\sqrt(n)$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$.

If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p<0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is

• $0$ if $i=j$ or if $|i-j| > 1$
• $p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)
• $1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)

You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$.

The question as proposed is more like a random walk on a $C_{2n+1}$, the cycle graph of size $2n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{2n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $-n, -n+1,... -1,0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $2n+1$ rows and columns, where each element $T_{i,j}$ is

• $0$ if $i=j$
• $p$ if ($i=j+1$) or ($i=1$ and $j=2n+1$)
• $1-p$ if ($i=j-1$) or ($i=2n+1$ and $j=1$)

The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.

This is a biased random walk on a graph, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the negative direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the positive direction (CW, clockwise) with the probability $p$.

Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is

• $0$ if $i=j$ or if $|i-j| > 1$
• $p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)
• $1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)

You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$.

If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.

It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at time $t=\sqrt(n)$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$.

If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p<0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$.