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$
2
  • 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
    Commented Feb 12, 2015 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
    Commented Feb 12, 2015 at 17:04

1 Answer 1

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$
1
  • $\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
    Commented Feb 12, 2015 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.