Coupling of random variables on a random graph

106 Views Asked by At

I am trying to understand Remark $3$, page $941$ and it's application in Proof of Lemma $9$ in page $945$ here.

$\textbf{Background:}$ See Section 3.2, sequential generation, first paragraph. A random directed graph is created in a sequential process, using the Configuration model, where each vertex has a given number of tails and heads associated with it i.e. outgoing and incoming half edges. $m$ is the total number of heads = total number of tails. We form directed edges in the following way:

1) An unmatched tail $e$ is chosen according to some priority

2) An unmatched head $f$ is chosen uniformly at random

3) $e$ is matched with $f$ to form the directed edge $ef$

$\textbf{Remark $3$:}$

Instead of choosing heads uniformly among the remaining unmatched ones, we may choose uniformly from all heads, and retry if the chosen head was already matched. The chance that this occurs within the first $k$ steps is $p = 1-\Pi_{i=0}^{k-1}\frac{m-i}{m}$. This creates a coupling between the first $k$ chosen heads and an i.i.d. sample from the uniform distribution on all heads, under which the two sequences coincide with probability $1− p$. In the analysis of the sequential process, we may thus replace the former by the latter at a total-variation cost $p ≤ k^2/m$.

$\textbf{Lemma 9:}$ See second bullet point. the walk has reached an unmatched tail by time $l$ : as explained in remark $3$, the remainder of the trajectory after the first unmatched tail can be coupled with an i.i.d. sample from the in-degree distribution on V at a total-variation cost $\leq \frac{\Delta r (t+l)^2}{m} = o(1)$.

Question: in-degree distribution is the same as the uniform distribution on all heads described in Remark $3$. So I was thinking the total variation cost would be $\leq \frac{j^2}{m}\leq \frac{(t+l)^2}{m}$, where $j$ is the length of the remainder of the trajectory but may I know why they have a factor of $\Delta r$ in the front? Thanks.