Timeline for Exist closed forms of the distribution of return time in markov chains?
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 5, 2011 at 10:28 | vote | accept | Chris | ||
| Jan 12, 2011 at 10:17 | comment | added | Did | (cont'd) Another example is the discrete circle with $4$ vertices, for which the return times is twice a shifted geometric random variable with parameter $\frac12$. | |
| Jan 12, 2011 at 9:59 | comment | added | Did | For which graphs the distribution of the return time of the SRW to a given vertex is (shifted) geometric I do not know. But graphs for which this occurs are the complete graphs on $N$ vertices. For every starting vertex, the probability that the return time equals $1+t$ is $p(1-p)^{t-1}$ with $p=1/(N-1)$. | |
| Jan 12, 2011 at 9:43 | comment | added | Did | @Chris: the one line proof I know requires that $p(x,y)=p(y,x)$ for every $x$ and $y$ (which, if the random walk is simple, amounts to the fact that the degrees of the vertices are all equal). To see this, one decomposes $P_{(x,x)}[X_t=Y_t]$ as the sum over every possible $y$ of $P_{(x,x)}[X_t=Y_t=y]$ which is $P_x[X_t=y]P_x[Y_t=y]=p_t(x,y)^2=p_t(x,y)p_t(y,x)$ and one notices that the sum over $y$ of $p_t(x,y)p_t(y,x)$ is also the decomposition of $P_x[X_{2t}=x]$ along the possible values $y$ of $X_t$. | |
| Jan 12, 2011 at 7:46 | history | edited | Chris | CC BY-SA 2.5 |
added 14 characters in body
|
| Jan 12, 2011 at 7:45 | comment | added | Chris | @Ori: I am interested in a simple random walk. But the graph is not required to be regular. Does the relation of return time of a single random walker and that two random walkers starting at the same vertex meet still hold if the graph is not regular? | |
| Jan 12, 2011 at 6:28 | comment | added | Did | @Ori: yes, reversible | |
| Jan 11, 2011 at 20:06 | comment | added | Ori Gurel-Gurevich | @Didier: reversible random walk with uniform stationary distribution. | |
| Jan 11, 2011 at 19:47 | comment | added | Did | @Ori: indeed, and more generally, for every random walk with uniform stationary measure. | |
| Jan 11, 2011 at 18:32 | comment | added | Ori Gurel-Gurevich | More clarifications are needed: are we talking about simple random walks? For a SRW on a regular graph the following is true: the probability of 2 independent SRW starting at the same vertex to be in the same place at some time $t$ is equal to the probability that a single SRW on the same graph returns to the starting vertex at time $2t$. But this does not say anything about the first time 2 SRWs meet. | |
| Jan 11, 2011 at 8:33 | comment | added | Did | The first time when two independent random walks on $G$ both starting from $x_0$ with transition probabilities $p$ meet is the first return time to the diagonal $\Delta=\{(x,x);x\in G\}\subset G\times G$ by the random walk on $G\times G$ starting from $(x_0,x_0)$ whose transition probabilities $p_2$ are given by $p_2((x,y),(x',y'))=p(x,x')p(y,y')$. | |
| Jan 11, 2011 at 7:31 | history | edited | Chris | CC BY-SA 2.5 |
overworked question
|
| Jan 10, 2011 at 21:21 | answer | added | Bill Thurston | timeline score: 3 | |
| Jan 10, 2011 at 21:14 | answer | added | Ori Gurel-Gurevich | timeline score: 2 | |
| Jan 10, 2011 at 19:35 | history | asked | Chris | CC BY-SA 2.5 |