# 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) ?

• Do you want to express $T(X,Y)$ as a martingale indexed by $L$, plus remainder terms? What is your purpose with the martingale representation? I mean, do you want to establish a deviation inequality or a central limit theorem? – Davide Giraudo Jul 17 '19 at 8:43
• Yes, indexed by $L$. Yes one such purpose is to get deviation inequalities. – Kcafe Jul 17 '19 at 20:20
• I see. And now I have an other question: do you assume that $X$ is independent of $Y$ or not necessarily? – Davide Giraudo Jul 17 '19 at 21:49
• $X$ and $Y$ are two independent random walks. I will update the question now. Thanks for asking for clarification. – Kcafe Jul 17 '19 at 22:23

Let the transition probability be $$p(v, u) = \mathbb{P}_v\{X_1 = u\}$$, $$v, u \in V$$. Define the occupation times processes $$\{\mathcal{X}_t, t \in \mathbb{Z}_+ \}$$, $$\{\mathcal{X}_t, t \in \mathbb{Z}_+ \}$$ by $$\mathcal{X} _t (v) = \sum_{s \leq t} \mathbb{I}\{X_s = v \}, \ \ \ \mathcal{Y} _t (v) = \sum_{s \leq t} \mathbb{I}\{Y_s = v \}, \ \ \ v \in V.$$
The processes $$\{\mathcal{X}_t, t \in \mathbb{Z}_+ \}$$, $$\{\mathcal{X}_t, t \in \mathbb{Z}_+ \}$$ take values in $$(Z_+ )^V$$. Let the function $$Q: V\times (Z_+ )^V \to [0,\infty)$$ be defined by
$$Q (v, \xi) = \sum_{u \in V} p(v, u) \xi (u)$$
The process $$T(X,Y)$$ is an a.s. increasing process, therefore it has a predictable compensator. If I did not miss something in the computations, the increments of the compensator are
$$K_t := Q(X_t, \mathcal{Y} _t) + Q(Y_t, \mathcal{X} _t) + \sum _{u \in V} p(X_t, u) p(Y_t,u),$$ so that $$A_t = \sum_{s \leq t-1} K_s$$ is the compensator. The process $$M_t := T_t(X,Y) - A_{t}$$ is then a martingale (w.r.t the filtration generated by the processes $$X$$ and $$Y$$).