Perturbation of a vector

Question

Given a vector $x=(x_1,\cdots,x_n)$ such that $0\leq x_i \leq1$ and $\sum_{i=1}^n x_i=1$. I would like to find a vector $x^*$ such that ($l_1$ norm ) $||x-x^*||_1\leq \delta$, where $\delta >0$.

How can we generate the $x_i^*$ so that still $\sum_{i=1}^n x^*_i=1$?

Answer 1

Set $\delta' = \frac{\delta}{2(n-1)}$. You can nudge each $x_i$ except for the last one by a random value in $\left[-\delta', +\delta'\right]$, and then adjust the last value to get the sum to be $1$.

Pseudocode:

1. $x \leftarrow (x_1,...,x_n)$
2. $\delta' \leftarrow \frac{\delta}{2(n-1)}$
3. $y \leftarrow (y_1, \ldots, y_n)$
4. for each $i$ until $n$ do
5. $\quad y_i \ \leftarrow \ (\,x_i + \mathsf{randomBetween(-\delta',+\delta')}\,)$
6. endfor
7. $y_{n+1} \leftarrow (1-\sum y_i)$

Using $y$ instead of $x^*$, the last line guarantees tha $\sum y_i = 1$.

We need to check that $|| x - y || < \delta$:

For $i=1,2,\ldots, n-1$ we have $|x_i - y_i| = \delta_i'$. Since the original $x$ vector sums to $1$, we also have $$|x_n-y_n| = \left|x_n - 1+\sum_{i=1}^{n-1} (x_i + \delta_i')\right| = \left|\sum_{i=1}^{n-1}\delta_i'\right|$$.

So $$|| x- y|| = \sum_{i=1}^{n-1} | \delta_i'| + \left| \sum_{i=1}^{n-1} \delta_i'\right| \le 2\sum_{i=1}^{n-1} | \delta_i'| \le \delta$$ using the triangle inequality.