Let $M$ be some metric space. We will also say that $M$ is a measurable space.

How do you find a probability measure $P$ on $M$ that maximizes the expected distance between two points? (That is, $P$ maximizes $E[d(X,Y)]$, where $X$ and $Y$ are independent random variables with distribution $P$.)

If $M$ is a discrete metric, then $P$ will the uniform distribution, for example.

Note that we can think of this as a game, and $P$ as a mixed strategy. You would have two players, which are both trying to maximize the distance. This is not a purely game-theoretical situation though, since we need to require the players to pick the same strategy. There is something called superrationality that might apply, but it is not well studied though. Maybe techniques similar to those used in game theory could be used though.

  • $\begingroup$ You need a measure on $M^2$ (i.e. the joint distribution of 2 random points on $M$). $\endgroup$ – d.k.o. Feb 4 at 20:36
  • $\begingroup$ @d.k.o. wouldn't that just be a product space of $M$ with itself? $\endgroup$ – PyRulez Feb 4 at 20:38
  • $\begingroup$ Do you mean the product measure $P\otimes P$? Maybe, if you assume independence. $\endgroup$ – d.k.o. Feb 4 at 20:40
  • $\begingroup$ @d.k.o. yes, I want to assume they are i.d.d. Otherwise, you could just pick to points that are a diameter apart, and always choose them. The point is that you need to choose randomly, because if you don't, the expected distance is guaranteed to be $0$. $\endgroup$ – PyRulez Feb 4 at 20:42
  • 2
    $\begingroup$ Very interesting question, but it depends a lot on the details of the metric space. If your space is $\{0,\pm1\}$, though, with $d(x,y)=|x-y|$, I think the optimum is to pick $\pm1$ uniformly, not to pick all 3 points uniformly, though. $\endgroup$ – kimchi lover Feb 5 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.