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$
  • $\begingroup$ If you take $b_1=1,b_2=0$ then you get your desired $(2P,0)$ solution. $\endgroup$ – Tom van der Zanden Aug 8 '17 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$ – K Gautam Shenoy Aug 8 '17 at 13:49
  • $\begingroup$ Considering I made a silly mistake and that this is very elementary, should I delete this question? $\endgroup$ – K Gautam Shenoy Aug 8 '17 at 13:55
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$

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.