1
$\begingroup$

During my research, I had encountered the following issue. Consider the equation $$\sum_{k=1}^K\alpha_k P_k = P$$

where $\sum_{k=1}^K\alpha_k=1$, $\alpha_k > 0$, $P_k > 0, P>0$.

So you are given $\{\alpha_k\}$, $K$ and $P$. The task is to generate randomly $\{P_k\}$ such that the above equation is satisfied. I am looking for an efficient way to generate these numbers.

My strategy

I have one method. Basically, we generate $K$ distinct uniform numbers between $(0,1)$. Call them $\{b_k\}$. Then we compute $\sum_{k=1}^K\alpha_k b_k = B$. Now the sequence $\{\frac{b_kP}{B}\}$ is the desired sequence.

However, if you observe, using this method, $P_k$ can never exceed $P$ and in my work, I require some of the values to exceed $P$. E.g. if $\alpha_1=0.5, \alpha_2=0.5$, even $(2P,0)$ is a valid solution.

Is there a way to generate these numbers so as to circumvent this issue?

Update: Given $\{\alpha_k\}$, it follows that $P_k \leq P/\alpha_{\min}$. Note: The above counter example is not valid. Apparently the algorithm works fine.

$\endgroup$
3
  • $\begingroup$ If you take $b_1=1,b_2=0$ then you get your desired $(2P,0)$ solution. $\endgroup$ Aug 8, 2017 at 13:06
  • $\begingroup$ Looks like I made a calculation error. In my simulations, I never got any value to exceed $P$. Thanks. Perhaps I just didn't get lucky. $\endgroup$ Aug 8, 2017 at 13:49
  • $\begingroup$ Considering I made a silly mistake and that this is very elementary, should I delete this question? $\endgroup$ Aug 8, 2017 at 13:55

1 Answer 1

2
$\begingroup$

A reasonable solution is to first generate a random point in the simplex $$ x_1 + \cdots + x_K = 1, \qquad x_1,\ldots,x_n \geq 0. $$ Check out this question for several ways to do this. Then take $$ P_i = \frac{P}{\alpha_i} x_i. $$ This should give you a uniformly random point in the geometric body you are interested in $$ \sum_{i=1}^K \alpha_i P_i = P. $$

$\endgroup$
0

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.