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) ?
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$– Davide GiraudoCommented Jul 17, 2019 at 8:43
-
$\begingroup$ Yes, indexed by $L$. Yes one such purpose is to get deviation inequalities. $\endgroup$– KcafeCommented 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$– Davide GiraudoCommented 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$– KcafeCommented Jul 17, 2019 at 22:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$).
