2
$\begingroup$

I'm trying to figure out if there is an algorithm which can solve the following:

Given an array of randomly generated values, for example: $$[54.6, 1.96, 5.0, 31.31]$$

Find an array of equal length, in this example $[x_1, x_2, x_3, x_4]$ such that:

$$54.6 \cdot x_1=1.96\cdot x_2=5.0\cdot x_3= 31.31\cdot x_4$$

and

$$x_1 + x_2 + x_3 + x_4 = 1.0$$

Any suggestions for an algorithm to solve this?

New contributor
Sam Kennedy is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • $\begingroup$ The problem, as you have stated it, is a linear system of equations. Since you mentioned that the $x_i$ are probabilities, then you also want the constraints $x_i\geq0$. So, you have a linear programming problem. Some algorithms that solve this problems are the Simplex, and many interior point methods. $\endgroup$ – plop Feb 23 at 15:16
  • $\begingroup$ Note that the solutions below assume that the input array consists of non-zero numbers. Remember to also look at the case when some of the values in the input array are zero. In that case all $x_i$ for which the corresponding $a_i$ is non-zero, must be zero themselves. So, you get all the solutions in the convex polyhedron $\sum_{i,a_i=0}x_i=1$, with $x_i\geq0$ and $x_i=0$, for $i$ such that $a_i\neq0$. $\endgroup$ – plop Feb 23 at 15:56
4
$\begingroup$

Let the array be $a_1,\ldots,a_n$, which we assume are positive. The condition $a_i x_i = a_j x_j$ implies that $$ x_i = \frac{a_n}{a_i} x_n. $$ Since the $x_i$ must sum to $1$, $$ 1 = \sum_{i=1}^n \frac{a_n}{a_i} x_n \Longrightarrow x_n = \frac{\frac{1}{a_n}}{\sum_{i=1}^n \frac{1}{a_i}}. $$ The formula for $x_i$ shows that $$ x_j = \frac{\frac{1}{a_j}}{\sum_{i=i}^n \frac{1}{a_i}}. $$

$\endgroup$
2
$\begingroup$

If you consider an array $[a_1, …, a_n]$, then an easy way to choose the array $[x_1, …, x_n]$ is to define $x_i = \frac{1}{a_i}$. That way, $\forall i, a_i\times x_i = 1$. The problem is that $\sum x_i$ is not necessarily equal to $1$, but is instead equal to $S = \sum \frac{1}{a_i}$.

If you now consider $x_i' = \frac{1}{S\times a_i}$, then we still have $\forall (i, j), a_i x_i' = a_j x_j'$, but we also have $\sum x_i' = \frac{1}{S}\sum \frac{1}{a_i} = 1$.

Since $S$ is easy to compute, you have what you wanted.

I supposed here that all $a_i > 0$.

$\endgroup$

Your Answer

Sam Kennedy is a new contributor. Be nice, and check out our Code of Conduct.

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.