Skip to main content
2 of 3
A typo in the title.
user64494
  • 3.5k
  • 14
  • 22

Martingales and intersection of random walks

Let $G=(V,E)$ be a graph with $n$ vertices. Consider a pair of 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