# What does the completed graph of a function mean

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!

-
I guess, completion here is the completion w.r.t. metric –  Ilya Feb 25 '13 at 14:33
@Ilya: Thanks! In a metric space, completion of a subset and cloure of a subset are the same? So redundant to say "closures of the completed graphs"? –  Tim Feb 25 '13 at 18:00

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) + \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) + \epsilon \text{ and } G(x-\epsilon) - \epsilon \leq F(x) \leq G(x+\epsilon) + \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) + \epsilon, \forall x \in \mathbf{R} \} = \inf \{ \epsilon > 0 : G(x-\epsilon) - \epsilon \leq F(x) \leq G(x+\epsilon) + \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)$.

-
Thanks, zab! I will get back to your reply later. –  Tim Apr 19 '13 at 15:50
I think your definition of the Levy distance is missing a $+\epsilon$ on the rightmost inequality. –  sourisse Nov 19 '14 at 5:28

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.

-
Are you talking a graph of vertices and edges as in graph theory? I think "the graph of a function" is the set between its argument axis and its plot, which has nothing to do with graph theory? –  Tim Feb 24 '13 at 23:36
@Tim Yes, I am thinking of graph theory. You can easily create this kind of graph from a function by thinking of the function as a set of ordered pairs. These ordered pairs are then the edges of the graph. This, of course, works only if the domain and range of the function are the same (or one is a subset of the other). –  Code-Guru Feb 24 '13 at 23:40
The function here has a domain and codomain which are both uncountable sets. So the graph you created will have uncountably many vertices? –  Tim Feb 24 '13 at 23:42
@Tim You can certainly have graphs with infinite vertex and edge sets. I'm not familiar with the theory of such infinite graphs and don't know what a "complete graph" means in that context. –  Code-Guru Feb 24 '13 at 23:53
Even though "completion" can be referred to many things, it is quite clear that "closure" here is the topological closure, and thus your approach with (weighted) graphs for the functions is misleading. –  Ilya Feb 25 '13 at 14:28