Rebalancing discrete probability distribution

Question

I'm working on a machine learning algorithm and have gotten stuck with how to rebalance a discrete probability distribution. I have a distribution represented as a simple array of $n$ numbers which are all bounded between $0$ to $1$ and that always sum to $1$. At a particular point I wish to update on of the numbers in the distribution by some random amount (it's still between $0$ and $1$) . At that particular point I must also update the remaining $n-1$ numbers so that the sum of the numbers in the distribution remain $1$.

My problem is that any algorithm I come up with for rebalancing fails for certain cases.

First algorithm was to uniformly distribute the difference to the remaining values. Obviously that didn't work (eg. can't subtract $0.1$ from $0.05$).

Second approach was as follows:

Let the distribution be represented by $\{p_{1},p_{2},...,p_{n}\}$ and let's assume I wish to update $p_{1}$ for the sake of argument.

Let $p^{new}_{1}$ be the new value for $p_{1}$.

Then I rebalance the remaining $n-1$ numbers by:

$p_{i} = p_{i} + ( p_{1} - p^{new}_{1} ) \frac{p_{i}}{sum}$

Where $sum = \sum_{j=2}^{n}(p_{j})$

Which also fails. For example, if some values in the distribution are $0$ then they will not get increased in the case of a positive update. I tried to correct this by checking if the sum is $0$ but that only allows me to solve the case where all $n-1$ numbers are $0$.

I feel like this should probably be very easy and that I'm just having a brain freeze at the moment...

Answer 1

In the comments you say that the "algorithm in question is used to find a neighbor distribution in the search space".

So, here is a simple (@whuber?) way to get another point on the Simplex which is "close" to a given one.

Suppose that your current point is $x=(x_1,x_2,\dots,x_k)$, with $x_i\geq 0$ and $\sum_{i=1}^k x_i=1$.

Let $a_0$ be a positive constant.

Define $Y=(Y_1,Y_2,\dots,Y_k)\sim \mathrm{Dirichlet}(a_0 x_1, a_0 x_2, \dots,a_0 x_k)$. By the properties of the Dirichlet distribution, we know that $$ \mathrm{E}[Y_i] = \frac{a_0 x_i}{a_0 x_1+a_0x_2+\dots+a_0 x_k} = \frac{a_0 x_i}{a_0( x_1+x_2+\dots+x_k)} = x_i \, , $$ for $i=1,\dots,k$, and the concentration parameter is just $$ a_0 x_1+a_0x_2+\dots+a_0 x_k = a_0 \, . $$ So, if you want your next point to be close to the current point, you choose a "big" value for $a_0$. Small values of $a_0$ will "spread out" the distribution of $Y$, which is "centered" on $x$.

Here is an implementation in R.

rdirichlet <- function(a) {
    y <- rgamma(length(a), a, 1)
    return(y / sum(y))
}

a0 <- 10

x = c(0.1, 0.2, 0.1, 0.6)

y <- rdirichlet(a0 * x)

Finally, how to deal with zero components? Add $(\epsilon,\epsilon,\dots,\epsilon$) to $x$ before drawing $Y$. Fine tune $a_0$ and $\epsilon$ and it will probably work.