Looping expressions

[Paul Moore]

A common probability problem I encounter involves repeating something until a condition occurs. For example, in the game Monopoly, you roll 2d6, and if you get a pair, you reroll. You can do this up to 3 times. This can be modelled as

d1+d2+lea.if_(d1==d2,d3+d4+lea.if_(d3==d4,d5+d6,0),0)

but this is a bit clumsy, and doesn’t extend to arbitrary numbers of repeats. For example, “roll a die, then roll and total that number of dice”. Again, it’s possible, via CPTs (and you can write a function to generate the CPT for you, to make it look less cryptic) but it would be nice to have some sort of “loop-until” function.

I honestly don’t know how such a function would look, and I’m not even sure if it’s something that can be done within the current framework - it might even need an extension to the Statues algorithm for something like a “looping pex”. But I thought I’d at least document the idea here in case it’s something that others would find useful.

(One thought I had was a “self referential pex”, so you could say (in effect) X = (d1 + d2 + if_(d1==d2, X, 0)). But you might need other information like “how many times has this repeated”, and I’m not sure how you could include that).

[Pierre Denis]

Aha, this rings a bell ! We have had a long discussion on such topic (ticket #31)… in 2016! It appears that I close this ticket on 2018 (maybe it was not a good idea to close it, after all).

The problem remains much interesting, anyway. I’m not sure whether this requires development in Statues algorithm (new Pex) nor in Lea’s core engine. Actually, I see your concern as how building in an easy way such trees with variable depth. And this can be done with Python recursive functions. Here is how I would revisit my earlier proposition :

def special_dice(nb_max_throws):
    if nb_max_throws == 0:
        return 0   # ... or -float("inf") for "GAOL"!
    (d1, d2) = interval(1,6).new(2)
    return d1 + d2 + if_(d1==d2,
                         special_dice(nb_max_throws-1),
                         0)

I checked that special_dice(3) gives the very same result as your expression (which is perfectly right, indeed). You may have a look to this example also.

Now, I’ve some good news. Since 2016, an important optimization has been done (#60). If I’m not mistaken, this means that you don’t need any longer the .getAlea() trick to improve the performance—as I discussed in #31.

I let you digest all this... Of course, I’m still much open to your ideas for adding (convenience?) functions in Lea, or even something more involved in the core algorithm.

[Paul Moore]

Ah, I’m so sorry - I should have checked, I’d completely forgotten that original discussion.

Thanks for the reminder and explanation. As you can probably tell, I’m revisiting some questions I worked on a while ago. I was prompted by a friend, who is also interested in this sort of problem - but he uses other languages, so we’re having a sort of friendly competition to see who can come up with the best solutions. I’m winning on problems that need big numbers, and the “divide and conquer” algorithm in times() gives me an advantage in a number of cases. He wins on raw performance, which I’m basically OK with as he’s using copmpiled C++. But he’s got some looping constructs, so he tends to do better than me with loops, and I’d forgotten that previous discussion.

I think at times I’m guilty of jumping straight to trying to find new features that would fit my problems, rather than trying to actually use what’s already there. Thanks for your patience!

[Pierre Denis]

You're welcome, Paul. I'm delighted that you do this sort of competition. My very first goal with Lea is to compete on expressiveness and ease-of-use. Something difficult to measure by benchamrks... I hope that my answer helps you staying in the game!

[Pierre Denis]

I put this ticket as "resolved" for now, without closing it. We can continue this discussion as needed.

[Pierre Denis]

By the way, the effect of optimization of #60 can be seen easily thanks to the optimize argument of calc (set to True by default). You may compare for example

print(special_dice(6).calc(optimize=False))
print(special_dice(6))

The first flavour is much slower. It's similar to what you've got in 2016 if you did not use the getAlea() trick. The good news is that there is no undesirable side effect for using optimize=True (that's why, it's the default).