title: Beating O(n!) for computing joint distributions
body: <p>I have <code>n</code> normal distributions of varying means and standard deviations (some distributions do have the same standard deviations)</p>
  <p>My goal is to compute the expected rank of the populations in each distribution.</p>
  <p>One approach I came up with was subtracting each distribution from each other one then finding the proportion of the new distribution that was &gt; 0. Doing this allowed me to populate a nxn matrix (where <code>P(i&gt;j)</code> indicates the probability that distribution i is greater than distribution j):</p>
  <pre><code>   0   | P(1&gt;2) | P(1&gt;3) .... P(1&gt;n)
  P(2&gt;1) |    0   | P(2&gt;3) .... P(2&gt;n)
  ....
  P(n&gt;1) | P(n&gt;2) | P(n&gt;3) ....   0
  </code></pre>
  <p>But to compute the expected ranks I still had to do the following, where <code>P(dist i, rank r)</code> means the probability that a sample from distribution i is rank r eg. <code>P(dist1, rank1)</code> would mean the probability that a sample from distribution 1 is the first place winner/highest rank:</p>
  <pre><code>P(dist1,rank1) = P(1&gt;2) &amp; ... &amp; P(1&gt;n)
  P(dist1,rank2) =
      P(1&lt;2) &amp; P(1&gt;3) &amp; ... &amp; P(1&gt;n) |
      P(1&gt;2) &amp; P(1&lt;3) &amp; ... &amp; P(1&gt;n) |
      ...
      P(1&gt;n) &amp; P(1&lt;2) &amp; ... &amp; P(1&gt;n-1)
  P(dist1, rank3) = ...
  P(dist2, rank...)
  ....
  </code></pre>
  <p>Which gives me n! time (I routinely have ~150-200 distributions) so n! isn't feasible.</p>
  <p>I'd like to avoid solutions that involve sampling the distributions if at all possible, but if that isn't possible any readings/papers that explain why it isn't an/ or offer robust sampling methods would be helpful</p>
  <p>My desired result is for each of n distributions given m ranks I have the following:</p>
  <pre><code>P(dist1, rank1) | P(dist1, rank2) | ... | P(dist1, rankm)
  ...
  P(distn, rank1) | P(distn, rank2) | ... | P(distn, rankm)
  </code></pre>
  <p>Said another way; if I were to sample the distributions what would the probability be that for a given distribution their sample(s) would be ranked highest? lowest? or each rank between?</p>
  <p>Assuming I know the true mean and standard deviation for each distribution, how can I compute the probability that a given distribution's sample will be of rank n (time complexity comes in since I'm interested in knowing the probabilities for each rank for each distribution)</p>