1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Also, 1) this looks like a pure mathematics question to me, and 2) Python is offtopic here. $\endgroup$ – Raphael Feb 12 '15 at 16:58
  • $\begingroup$ I am able get $x^*$ but I don't have any idea how to make $\sum_{i=1}^n x^*_i=1$ $\endgroup$ – Kumar Feb 12 '15 at 17:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that programming is offtopic here, so you might rather want to explain why that solution is correct. Also, how do you maintain that the sum of all components is $1$ when you add random values? $\endgroup$ – Raphael Feb 12 '15 at 16: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.