4
$\begingroup$

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

$\endgroup$
4
  • 2
    $\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$ Commented Jul 17, 2019 at 8:43
  • $\begingroup$ Yes, indexed by $L$. Yes one such purpose is to get deviation inequalities. $\endgroup$
    – Kcafe
    Commented Jul 17, 2019 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$ Commented Jul 17, 2019 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
    Commented Jul 17, 2019 at 22:23

1 Answer 1

1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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