I am looking for the probability that two random walkers initially at different sites, meet at step t if they are moving on a 2-dimensional torus(Square Lattice)

Any help would be appreciated.

  • $\begingroup$ Surely you need to say the initial probability distribution of where they start, if you want to work out the probability of when something else (that depends on where they start) happens. $\endgroup$ – znt Nov 15 '16 at 7:38
  • $\begingroup$ Like @znt said, you need to give more details if you expect a precise answer. Is is a discrete time random walk, or is it a continuous time random walk. In either case you need to give more details about the transition probabilities. $\endgroup$ – Liviu Nicolaescu Nov 15 '16 at 9:20
  • $\begingroup$ I am supposing that they start at (x1,y1) and (x2,y2) on my square lattice. They do a discrete time random walk. and they are doing a simple random walk so they hop to their neighboring sites with equal probabilities. $\endgroup$ – Klara.D Nov 15 '16 at 16:43
  • $\begingroup$ Just to be sure: you mean "meet for the first time at time $t$", or "be at the same location at time $t$"? $\endgroup$ – Serguei Popov Nov 15 '16 at 18:10
  • $\begingroup$ Thank You for your question. Be at the same location at time t. $\endgroup$ – Klara.D Nov 15 '16 at 18:38

One idea would be ot fix one random walker and look a the law of the difference, i.e., instead of looking at the distance between $X_1$ and $X_2$, you look at the distance between $X_1-X_2$ and the origin. But in here, since the two walkers have the same law and are (I guess) independent, you can write: $$\begin{align} P_{(a,b)}(X_1(t)=X_2(t))&=\sum_ {x\in T}P_a(X_1(t)=x)\times P_b(X_2(t)=x) \\ &=\sum_ {x\in T}P_a(X_1(t)=x)\times P_x(X_1(t)=b) \\ &=P_a(X_1(2t)=b) \\ \end{align}$$ where $P_{(a,b)}$ means that $X_1(0)=a$ and $X_2(0)=b$, and $T$ is the set of vertices of the torus.

  • $\begingroup$ in your first equality, you used the assumption that the random walks are reversible, correct? $\endgroup$ – alezok Nov 21 '16 at 3:42
  • $\begingroup$ Correct. This is the case here since the walkers do a simple random walk on the square torus, see the comment of klara.d. $\endgroup$ – Salsifis Nov 21 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.