Notes from a Medium-Sized Island [entries|archive|friends|userinfo]

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Mar. 20th, 2010|05:38 pm]
[Tags|, , ]

Regarding the current research project, one of the interesting dangling threads leading off into unknown (at least unknown to me) territory has to do with metrics on the space of probability distributions. The one I am considering right now is just

d(p1, p2) = max_{x : τ} | ln( p1(x) / p2(x) ) |

for p1, p2 : τ → [0,1] being probability distributions on τ. This captures the "worst case multiplicative difference" in the probability that p1 might assign to an event compared to p2, and so it's just right for getting a handle on differential privacy.

But Katrina, while we were chatting the other day, pointed me towards the Lévy-Prokhorov metric and the Fréchet metric, which both look really interesting as well. Not sure what they mean for me yet. Fréchet, as it turns out, was an esperantist, and wrote entire papers in the language. Then again, mathematicians as a rule would not blink an eye at the apparent near-futility of writing paper that is only readable by a very select minority.

From: wjl
2010-03-21 02:14 am (UTC)
(Reply) (Thread)
[User Picture]From: bhudson
2010-03-21 05:20 am (UTC)
The frechet distance is a hot topic in geometry, or at least has been the past few years. Computing it is hard.
(Reply) (Thread)
[User Picture]From: jcreed
2010-03-21 12:35 pm (UTC)
I think weak frechet may be what I want, since I'm frequently concerned about types where the monotonicity condition in regular frechet doesn't even really make sense.

And the relevant algorithm designs in the field I'm thinking about have a habit of more or less disregarding efficiency in the first attempt anyway. At least, in the exponential mechanism, there's a Boltzmann-like normalization factor you have to compute, and it's usually exponentially bad.

Edited at 2010-03-21 12:35 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: stepleton
2010-03-21 07:21 pm (UTC)
The log ratio is reminiscent of K-L divergence (not a metric).
(Reply) (Thread)
[User Picture]From: jcreed
2010-03-21 07:29 pm (UTC)
Oh yeah! I see your point. Mine manages to be a metric by being a max rather than an (asymmetrically) weighted sum. I wonder what you'd get with an unweighted sum, though, for which you'd have to assume the type τ has a reasonable measure you can integrate over. Man, first metric spaces, now measurable spaces! This is getting complicated/interesting.
(Reply) (Parent) (Thread)