What does the completed graph of a function mean

Question

zab said:

the Levy metric between two distribution functions $F$ and $G$ is simply the Hausdorff distance $d_C$ between the closures of the completed graphs of $F$ and $G$.

I have difficulty in understanding the sentence. In particular, what does the completed graph of a function $F$ mean? What are the two sets the Hausdorff distance is applied to?

Is the Levy-Prokhorov metric also similar to Hausdorff metric in some ways? I haven't figured out a way to understand the L-P metric either, so If you would reply to the linked question or here, I would appreciate it too!

Thanks and regards!

Answer 1

Sorry Tim, I just saw this post.

The completed graph of a function $F$ is simply a closed connected subset of $\mathbf{R}^2$ that consists of the set $\{ (x,F(x)), x \geq 0 \}$, together with the vertical line segments joining the points $(x,F(x-))$ and $(x,F(x+))$ whenever $F$ has a discontinuity at $x$. (Note that since $F$ is a distribution function, it is monotone, so any discontinuities are jumps.)

Now going back to the original discussion here:

What is the motivation of Levy-Prokhorov metric?

Take two distribution functions $F$ and $G$, and let $\overline{F}$ and $\overline{G}$ represent the respective completed graphs of $F$ and $G$. Then the Levy-Prokhorov metric between distribution functions can indeed be interpreted as an appropriately defined Hausdorff distance between $\overline{F}$ amd $\overline{G}$.

The Levy distance is

$L(F,G) = \inf \{ \epsilon > 0 : F(x-\epsilon) - \epsilon \leq G(x) \leq F(x+\epsilon), \forall x \in \mathbf{R} \}$.

In words, it means this: For $(x,y) \in \mathbf{R}^2$, define a square of sides $2 \epsilon$ centred at $(x,y)$ as $S_\epsilon(x,y)$. Then $\{ S_\epsilon(x,y), \forall (x,y) \in \overline{F} \}$ is the "tube" traced out by the square $S_\epsilon(x,y)$ as $(x,y)$ travels along the connected set $\overline{F}$. Now take the smallest $\epsilon$ for which the above "tube" contains $\overline{G}$. This gives the Levy-Prokhorov distance between $F$ and $G$.

Now let $d_C((x_1,y_1),(x_2,y_2)) := |x_1-x_2| \vee |y_1-y_2|$. This is a metric on $\mathbf{R}^2$ called the Chebychev metric. Under this metric, an $\epsilon$-neigbourhood $N_\epsilon(x,y)$ of the point $(x,y)$ is simply a square of sides $2 \epsilon$ centred at $(x,y)$. This is the same set as $S_\epsilon(x,y)$ defined above. Let $h_C(A,B)$ be the Hausdorff metric induced by $d_C$ on the space of closed subsets of $\mathbf{R}^2$. Then the $d_C(\overline{F},\overline{G})$ is the smallest $\epsilon$ for which the $\epsilon$-inflation of $ \overline{F}$ i.e., $ \cup \{ N_\epsilon(x,y), (x,y) \in \overline{F}\}$ contains $\overline{G}$ and vice versa, i.e.,

$\inf \{ \epsilon > 0 : \overline{G} \subseteq \cup\{ N_\epsilon(x,y), (x,y) \in \overline{F}\} \text{ and } \overline{F} \subseteq \cup \{ N_\epsilon(x,y), (x,y) \in \overline{G}\} \}$.

Note further that strictly speaking, the Huasdorff metric is equal to

$\inf \{ \epsilon > 0 : F(x-\epsilon) - \epsilon \leq G(x) \leq F(x+\epsilon) \text{ and } G(x-\epsilon) - \epsilon \leq F(x) \leq G(x+\epsilon), \forall x \in \mathbf{R} \}$,

but since $F$ and $G$ are increasing functions, $\overline{F}$ and $\overline{G}$ are rather special closed sets, and

$\inf \{ \epsilon > 0 : F(x-\epsilon) - \epsilon \leq G(x) \leq F(x+\epsilon), \forall x \in \mathbf{R} \} = \inf \{ \epsilon > 0 : G(x-\epsilon) - \epsilon \leq F(x) \leq G(x+\epsilon), \forall x \in \mathbf{R} \}$.

Note: $\cup\{ N_\epsilon(x,y), (x,y) \in \overline{F}\}$ seemed cleaner than $\cup_{(x,y) \in \overline{F}} N_\epsilon(x,y)$.

Answer 2

Since you are talking about distance metrics, I assume the graphs under consideration are weighted. My guess is that you create a complete graph from an arbitrary graph by adding a 0-weight edges where is no edge in the original graph.