6
$\begingroup$

I'd appreciate any insights or references to research regarding the following:

Suppose you have a discrete metric space with a probability distribution on it. also, suppose that I'm given a number $k$. My problem is finding the highest probability ball.

A ball is the set of all points whose distance from a given point is less than or equal to $k$, and the "probability of the ball" is just the sum of the probabilities of this set of points.

The continuous case (less interesting in my case, but potentially helpful) would be to have a probability distribution on $R^n$, an finding the n-ball with the highest integral when integrating the density function on the $n$-ball.

This problem is an abstraction of a practical problem I try to solve. the solution of special case of $k=0$ (e.g. in which case a "ball" is just a single point) is just the mode of the distribution.

The general case arises for example in the following prediction problem: suppose you try to "predict" $n$ independent binary events. So every prediction is a binary $n$-tuple (with a probability distribution imposed on that space, based, for example, on assumptions, previous data, etc.). Now, suppose you are allowed to have a few mistakes in your prediction, and you try to find a prediction that maximizes the probability of "success" (that is, not making too many mistakes). The solution is exactly an n dimensional "ball" in the n-tuple space with the hamming metric.

Any idea, insight, or reference to relevant research would be much appreciated.

$\endgroup$
  • 2
    $\begingroup$ It's a nice question. Presented abstractly, though, as a problem about arbitrary metric spaces, it strips away all the relationships that could be exploited to obtain efficient algorithms. For instance, $\mathbb{F}_2^n$ with the Hamming distance enjoys a tremendous number of isometries. In the general case there's nothing to exploit, so you would just have to make some kind of exhaustive search of the balls, exploiting nothing but basic properties of a metric (symmetry and triangle inequality). What is the metric space you are actually dealing with in your practical problem? $\endgroup$ – whuber Sep 24 '13 at 13:24
  • $\begingroup$ Thanks for the comment. I intentionally asked an abstract question, so not to constrain too much the direction of a solution. I did gave some context, so that people can answer for the special case of the Hamming distance. My real case, if you want to know has a trenary n-tuples, with weights over the dimensions (that is, some dimensions are "more expensive" than others to make a prediction error), also, I'm looking into a "weighted sum" of the probabilities of the points, so that the prediction with no errors and the prediction with 2 contribute differently to overall "ball" value. $\endgroup$ – amit Sep 24 '13 at 13:30
  • $\begingroup$ Unless there's some pattern to the weights, it looks like you haven't any hope of obtaining an exact solution without exhaustive search. You could readily apply simulated annealing to obtain reasonably good solutions. $\endgroup$ – whuber Sep 24 '13 at 14:35
  • $\begingroup$ Do you mean there is no solution for the general case? the special of binary n-tuples with the hamming distance? the more specific case I described in the above comment? what pattern would you look for in order for a solution to exist (beyond exhaustive search. my n is big enough so exahaustive search is infeasible) $\endgroup$ – amit Sep 24 '13 at 15:09
  • 1
    $\begingroup$ I don't know what patterns might work, but what is clear is that if your weights are arbitrary, then your problem is one of finding maximal neighborhoods in a vertex-weighted graph, which I suspect is NP-hard. I don't think that difficulty goes away just because yours is a complete graph. $\endgroup$ – whuber Sep 24 '13 at 15:41
4
$\begingroup$

While the problem is in general intractable, your motivating example assumes independent events, which provides more than enough structure to solve this problem. Let me restate what you are trying to show to make sure that I understand:

You have $n$ independent Binomial random variables $X_i\sim \mathrm{Binomial}(p_i)$, $i=1,\dotsc,n$. Your goal is to find a point $\hat x \in \{0, 1\}^n$ that maximizes the probability $$\mathbb{P}\{\mathrm{d}_H(\hat x, {X})\le k\},$$ where $\mathrm{d}_H$ denotes the Hamming metric and ${X}=(X_1,\dotsc,X_n)$ is the vector of binomial random variables.

Because of independence, the answer is trivial: Choose the most likely point, i.e., set

$$ \hat{x}_i = \begin{cases} 0,& p_i \le 0.5 \\ 1, &p_i >0.5.\end{cases}$$

Let's see why this is true using induction. The recipe above is trivially true for $n=1$. Let $n>1$ and suppose that the recipe holds for $n-1$. Then by independence,

$$ \mathbb{P}\{ \mathrm{d}_H(x,X)\le k\} = \mathbb{P}\{x_n = X_n\} \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k\} + \mathbb{P}\{x_n \ne X_n\} \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k-1\}$$

where we use the shorthand $x^{(n-1)} = (x_1,\dotsc,x_{n-1})$. By the induction hypothesis, our best possible choice of $x^{(n-1)}$ is $\hat{x}^{(n-1)}$, the most likely point of $X^{(n-1)}$. Moreover, since we always have

$$\mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k\} \ge \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)})\le k-1\},$$

we should always choose ${x}_n$ to maximize $\mathbb{P}\{\hat x_n = X_n\}$, which is the claimed recipe. #

Near independence?

Independence is clearly a very strong assumption, but in many cases we have reason to believe that the elements are nearly independent. On common way to measure the "nearness" of (say, binary) random variables $X$ and $Y$ is the total variation metric:

$$ d_{TV}(X,Y):= \sup_{A \subset \{0,1\}^n} | \mathbb{P}\{ X \in A\} - \mathbb{P}\{Y\in A\} | $$

Taking, for example, $A:= \{y \mid d_H(x,y) \le k\}$, we find that for any binary random variables $X$, $Y$

$$ |\mathbb{P}\{ d_H(x, X) \le k\} - \mathbb{P}\{d_H(x,Y)\le k\}| \le d_{TV}(X,Y).$$

We conclude that when $Y$ is "almost independent" in the sense that the TV norm distance to an RV variable $X$ with independent entries is very small, then it is possible to argue that taking $\hat x$ to be the most likely vector for $X$ is a also a good choice for $Y$.

Care must be taken to apply this logic, however. First of all, I've given no clue how to compute a TV metric; you'll need to use the specific facts at hand and some ingenuity.

A more subtle danger lies in the fact that the TV norm estimate will typically be useless unless $k$ is large. This is because the supremum in the TV will often occur for sets $A$ with measure near $1/2$. Unless $k$ is large, it is likely that the Hamming ball of width $k$ has miniscule measure compared to the TV norm.

You may be able to refine your arguments somewhat, but the ability to control the error using this approach is (once again) strongly dependent on your particular situation.

$\endgroup$
  • $\begingroup$ Could you show us a little more explicitly how your interpretation fits into the framework of the question? I do not see the connection between your answer and the question, even the simplified Hamming distance version. In that version, the metric space in question has $2^n$ points, whence it has $2^n$ probabilities associated with those points. How do you reduce this to just $n$ parameters? $\endgroup$ – whuber Sep 24 '13 at 17:08
  • $\begingroup$ @whuber If the events are independent, then all $2^n$ probabilities are determined by just the $n$ parameters $p_i$. Does this answer your question? $\endgroup$ – Mike McCoy Sep 24 '13 at 17:12
  • $\begingroup$ Thanks; I see the connection with the last paragraph of the question, which I did not read sufficiently carefully. You provide a nice example of how additional structure on the metric space, its probabilities, and the weights can change an inherently intractable problem into one that is computationally easy. $\endgroup$ – whuber Sep 24 '13 at 17:16
  • $\begingroup$ This is a good solution for the special case. I had a feeling that this would be the answer, but I couldn't prove it. so thanks. However, it exlpains why I asked a more general case - the solution you presented exploited the simplicity of structure that makes it difficult to take some intuitions from this solution and generalize it. However, I have a follow up question even for this special case: suppose we need to choose not only 1 ball, but 2 or 3 (or more generally, m) such balls, so that we maximize the sum of the probabilities of all covered cases - what would be a good strategy? $\endgroup$ – amit Sep 24 '13 at 17:34
  • 1
    $\begingroup$ There is a bit of generality here. The same proof works for an arbitrary (finite) "state space" for $X_i$, for example. As far as $m$ balls go, my hunch is that you are in for an intractable problem, even for $m=2$. You may find some information in the literature on covering codes. $\endgroup$ – Mike McCoy Sep 24 '13 at 17:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.