Fastest Way To Iterate Over A Probability Simplex

[Efrat Regev]

Hello,

Let's say a probability vector of dimension d is x_1, ..., x_d, where
each one is a non-negative term, and they all sum up to 1. Now I'd like
to iterate over all probability vectors, but this is impossible, since
they're uncountable. So instead, let's say I want to iterate over all
such vectors under the constraint that the granularity of each component
is at most some delta.

To make things pythonesque, here's the interface:
<interface>
class simplex:
def __init__(self, dim, delta):
...

def __iter__(self):
...

def next(self):
...
</interface>

The problem is, what's a fast implementation? I tried something simple,
and it is slooooooooooooow. If anyone can think of something clever, I'd
love to hear it.

Many Thanks,

Efrat

 

[bearophileHUGS]

I want to iterate over all
such vectors under the constraint that the granularity of
each component is at most some delta.

You can think of this like your sum is an integer>=1 and the single
"probabilities" are integers>=1 So given the sum, like 6, you can find
all the parts of it, and then find all the permutations of such parts.
Eppstein has given code for the parts of an integer, and you can can
find the iterable permutations code on the cookbook. But the number of
such possible vectors grows very quickly...

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/218332
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124

Bye,
bearophile

 

[Efrat Regev]

You can think of this like your sum is an integer>=1 and the single
"probabilities" are integers>=1 So given the sum, like 6, you can find
all the parts of it, and then find all the permutations of such parts.
Eppstein has given code for the parts of an integer, and you can can
find the iterable permutations code on the cookbook. But the number of
such possible vectors grows very quickly...

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/218332
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124

Bye,
bearophile

Many thanks. I modified the recipes you attached some, and it works much
better. Nice and informative answer!