Skip to main content
3 of 3
added 12 characters in body
Kcafe
  • 519
  • 3
  • 11

Martingales and intersection of random walks

Let $G=(V,E)$ be a graph with $n$ vertices. Consider a pair of independent simple random walks $(X,Y)$ on the graph, each of length $L$ starting from a node $v \in V$. We denote a length-$L$ random walk $X$ as a tuple in $V^L$, as $(X_1,\ldots, X_L)$. Now consider an estimate of number of intersections in such a pair of random walks, given by \begin{align} T (X,Y)= \sum_{j=1}^L \sum_{k=1}^L \mathbb{I}_{\{ X_j = Y_k\}} \end{align} where $\mathbb{I}_{\{\cdot\}}$ is the indicator function of the event $\{\cdot\}$. My question is can the random variable $T(X,Y)$ be represented as a martingale (plus some reminder terms) ?

Kcafe
  • 519
  • 3
  • 11