3
$\begingroup$

I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a sequence than a smaller element is proportional to the ratio of these elements' values.

For instance if we have a sorted sequence of elements: 1, 2, 3, then I'd like this algorithm to generate a permutation of this sequence in such a way that the probability of finding element 3 earlier in a sequence than the element 1 is 3 times smaller than the other way around. This property should hold for all pairs of the elements.

Is this possible? If so, can you suggest an algorithm for this?

$\endgroup$
4
$\begingroup$

Here is an algorithm: Choose a number from the sequence with probabilities proportional to their values, remove it and push_front it to the output sequence. Repeat the steps.

With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.

The algorithm can be implemented in time O(NlogN)

$\endgroup$
  • $\begingroup$ Indeed! I started out thinking along similar lines (analoguously to insertion sort or the like), but somehow convinced myself that the probabilities couldn't be untangled. $\endgroup$ – Magnus Lie Hetland May 2 '13 at 19:37
3
$\begingroup$

You could use the Metropolis-Hastings algorithm (or perhaps Gibbs sampling) to sample your sequence, as long as you can calculate the desired probability for the entire sequence (or a function that is proportional to the probability). As I understand you, you wish to let the probability of $a$ coming before $b$ be set to the odds $a\mathop{:}b$. If all such decisions were independent, you could simply multiply the probabilities (derived from the odds) over all the pairs—but of course they're not. This might be a good enough approximation of what you're after, though, depending on what the application is.

Anyway, once you have your probability function $f(s)$ (defined over the entire sequence $s$), an application of the Metropolis algorithm (a special case of Metropolis-Hastings) would be something like this:

  1. Start with an arbitrary ordering $s$.
  2. Generate a different ordering, $s'$, for example by randomly swapping two elements.
  3. Compute the acceptance ratio $\alpha = f(s')/f(s)$.
  4. If $\alpha \geq 1$, accept $s'$, that is, use it instead of $s$ for the next iteration. Go to 2.
  5. Otherwise, accept $s'$ with a probability $\alpha$. Go to 2.

And then you let this run for “a while”—exactly how long would depend on the length of your sequence (though the number of iterations should be on the order of the autocorrelation of the Markov process; you can probably find more details on this in a good book on Monte Carlo methods).

$\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.