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$?
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:
- $x \leftarrow (x_1,...,x_n)$
- $\delta' \leftarrow \frac{\delta}{2(n-1)}$
- $y \leftarrow (y_1, \ldots, y_n)$
- for each $i$ until $n$ do
- $\quad y_i \ \leftarrow \ (\,x_i + \mathsf{randomBetween(-\delta',+\delta')}\,)$
- endfor
- $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.
