1
$\begingroup$

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.

Given $a_1,\dots,a_D$ (all strictly positive), I want to draw points uniformly from

$\qquad X =\{(x_1, x_2, ..., x_D) \mid 0 \leq x_1 \leq x_2 \leq \dots \leq x_D\leq 1, \sum_{i=1}^D a_i x_i = 1 \} $

How do I achieve this? I would also like to understand how $x_1$ might be distributed over $[\frac {1} {\sum_i a_i}, \frac {1} {a_1}$] (a theoretical query).

This question solves it for $a_i=1$ and without the $x_i$'s having a prior order, but I do not see any obvious way to generalize from that answer.

There is a similar question on MO, but without the weights $a_1,\dots,a_D$.

$\endgroup$

closed as off-topic by David Richerby, Evil, Rick Decker, D.W. Jul 6 '16 at 3:51

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Simultaneously crossposted to mathoverflow - please don't do this. mathoverflow.net/questions/243687/… $\endgroup$ – usul Jul 5 '16 at 3:17
  • $\begingroup$ I don't understand the definition of your set. I assume $x_n$ is a typo for $x_D$ but that's not super-important. What are the $a_i$? Are they a fixed parameter for the set? Are they existentially quantified for each element of the set? And what do you mean by a "good" way? Fast? Very close to uniform? Memory-efficient? Using only a few random bits? Something else? $\endgroup$ – David Richerby Jul 5 '16 at 10:21
  • $\begingroup$ @DavidRicherby $a_i$ are a fixed parameter of the set. By a good way, I first want to know what is the correct way theoretically. If you see the link to the "question I asked elsewhere", you would see that I started with a wrong way of dealing with this. From this question I would further like to understand how $x_1$ might be distributed over $[\frac {1} {\sum_i a_i}, \frac {1} {a_1}$] (once again a theoretical query) Finally, I think simulation wise I would like to know a fast way. I will edit the question a bit to make the language clearer. $\endgroup$ – Juanito Jul 5 '16 at 12:05
  • $\begingroup$ Please edit your clarifications into the question so people don't have to read the comments to find out what you mean. I've no idea what "the correct way theoretically" means -- that just sounds like "good" written in language that sounds more objective but isn't. $\endgroup$ – David Richerby Jul 5 '16 at 13:13
  • $\begingroup$ I do not come from a CS back ground, hence you have to forgive whatever lack of objectivity you are pointing to. That being said, are you telling me, that there are multiple ways of getting this done, and you would answer according to how I define this "objective" measure? Or are you just asking me to do this out of curiosity? $\endgroup$ – Juanito Jul 5 '16 at 22:01