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

  • 1
    $\begingroup$ 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? $\endgroup$ – Davide Giraudo Jul 17 '19 at 8:43
  • $\begingroup$ Yes, indexed by $L$. Yes one such purpose is to get deviation inequalities. $\endgroup$ – Kcafe Jul 17 '19 at 20:20
  • $\begingroup$ I see. And now I have an other question: do you assume that $X$ is independent of $Y$ or not necessarily? $\endgroup$ – Davide Giraudo Jul 17 '19 at 21:49
  • $\begingroup$ $X$ and $Y$ are two independent random walks. I will update the question now. Thanks for asking for clarification. $\endgroup$ – 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$).

| cite | improve this answer | |

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.