Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some point: $(d_{1_0}, d_{2_0}, ..., d_{N_0})$.

Here, the probability for a walker to take a step towards any of the reflecting boundaries is biased - $(P[d_1],...,P[d_{2N}])$, $Sum(P[d_1],...,P[d_{2N}])=1$? Unlike the unbiased case, the probability of taking a step towards any reflecting boundary (except at the edges of the graph) is no longer $(1/2N)$.

How well can we estimate the cover time of $Z_N$ for this biased random walk?


The cover time for an unbiased random walk on $Z^N$ was answered by Andreas Rüdinger in a previous question: (Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular latticeExpected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice)

He cites the paper "Jonasson, Schramm, ON THE COVER TIME OF PLANAR GRAPHS, Elect. Comm. in Probab. 5 (2000) 85-90. (http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocbfb7.pdf).

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some point: $(d_{1_0}, d_{2_0}, ..., d_{N_0})$.

Here, the probability for a walker to take a step towards any of the reflecting boundaries is biased - $(P[d_1],...,P[d_{2N}])$, $Sum(P[d_1],...,P[d_{2N}])=1$? Unlike the unbiased case, the probability of taking a step towards any reflecting boundary (except at the edges of the graph) is no longer $(1/2N)$.

How well can we estimate the cover time of $Z_N$ for this biased random walk?


The cover time for an unbiased random walk on $Z^N$ was answered by Andreas Rüdinger in a previous question: (Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice)

He cites the paper "Jonasson, Schramm, ON THE COVER TIME OF PLANAR GRAPHS, Elect. Comm. in Probab. 5 (2000) 85-90. (http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocbfb7.pdf).

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some point: $(d_{1_0}, d_{2_0}, ..., d_{N_0})$.

Here, the probability for a walker to take a step towards any of the reflecting boundaries is biased - $(P[d_1],...,P[d_{2N}])$, $Sum(P[d_1],...,P[d_{2N}])=1$? Unlike the unbiased case, the probability of taking a step towards any reflecting boundary (except at the edges of the graph) is no longer $(1/2N)$.

How well can we estimate the cover time of $Z_N$ for this biased random walk?


The cover time for an unbiased random walk on $Z^N$ was answered by Andreas Rüdinger in a previous question: (Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice)

He cites the paper "Jonasson, Schramm, ON THE COVER TIME OF PLANAR GRAPHS, Elect. Comm. in Probab. 5 (2000) 85-90. (http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocbfb7.pdf).

Source Link
Rob Grey
  • 599
  • 1
  • 4
  • 17

Cover time for a biased random walk on an 'N'-dimensional integer lattice

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some point: $(d_{1_0}, d_{2_0}, ..., d_{N_0})$.

Here, the probability for a walker to take a step towards any of the reflecting boundaries is biased - $(P[d_1],...,P[d_{2N}])$, $Sum(P[d_1],...,P[d_{2N}])=1$? Unlike the unbiased case, the probability of taking a step towards any reflecting boundary (except at the edges of the graph) is no longer $(1/2N)$.

How well can we estimate the cover time of $Z_N$ for this biased random walk?


The cover time for an unbiased random walk on $Z^N$ was answered by Andreas Rüdinger in a previous question: (Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice)

He cites the paper "Jonasson, Schramm, ON THE COVER TIME OF PLANAR GRAPHS, Elect. Comm. in Probab. 5 (2000) 85-90. (http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocbfb7.pdf).