Finding the highest probability balls 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.
 A: 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.
