6
$\begingroup$

Consider this code to simulate a simple instance of the coupon collector problem. We initialize an array to {0, 0} and then keep incrementing a random element until we've incremented every element at least once.

ch = ConstantArray[0, 2];
While[Min[ch] === 0,
  i = RandomInteger[{1, 2}];
  ch[[i]]++];
ch

It returns something like {1, 1} or {3, 1}. The smallest element will necessarily be 1 because the while-loop terminates as soon as any element in the array is greater than zero.

Now suppose we decide to condense the body of the while-loop into one line:

ch = ConstantArray[0, 2];
While[Min[ch] === 0,
  ch[[RandomInteger[{1, 2}]]]++];
ch

Everything seems ok, but then, horror: sometimes it returns things like {2, 3} where neither element is 1.

How can that happen?

PS, in case it gives anyone any ideas, here's a more definitive demonstration of how the above bits of code give different results:

n = 200;

ch = ConstantArray[0, n];
While[Min[ch] === 0,
  i = RandomInteger[{1, n}];
  ch[[i]]++];

ch2 = ConstantArray[0, n];
While[Min[ch2] === 0,
  ch2[[RandomInteger[{1, n}]]]++];

ListPlot[{Sort@ch, Sort@ch2}, PlotStyle->{PointSize[.015], Automatic}]

ListPlot

$\endgroup$
12
  • 2
    $\begingroup$ I think it is BUG! I found a very simple way to show it also. I can't explain this other than it is bug, where ++ is interacting with the RandomInteger call in some strange way. That is why when you call RandomInteger before and then use its result, it works. $\endgroup$
    – Nasser
    Nov 10, 2023 at 6:55
  • 1
    $\begingroup$ No such a bug in version 8.0.4. Can anybody test versions 9--12? $\endgroup$
    – innaiz
    Nov 10, 2023 at 12:46
  • 1
    $\begingroup$ Confirming the existence of the {2,3} result for the second code block in 13.3 $\endgroup$ Nov 10, 2023 at 18:30
  • 2
    $\begingroup$ With help from @JoshuaSchrier, I've pared this down a bit: SeedRandom[3]; ca = {a, b}; ca[[RandomInteger[{1, 2}]]]++; ca That bizarrely returns {a, 1+a}. $\endgroup$
    – dreeves
    Nov 10, 2023 at 20:52
  • 1
    $\begingroup$ You can send email to [email protected] descripting the problem and also give link to this post for additional info. $\endgroup$
    – Nasser
    Nov 11, 2023 at 4:43

3 Answers 3

6
$\begingroup$

I don't know how to answer just in the comments, so here's a non-solution reply to your question.

Is there any principle you can articulate by which one could make one's code more robust to this kind of thing?

There are two side-effect-dependent patterns here. The first is simply

something[[idx]] = new

This kind of modifying in place is rarely necessary, so should be used only when nothing else will do. For example, you could repeatedly increment a randomly chosen element like this:

Nest[Function[list, MapAt[# + 1 &, list, RandomInteger[{1, 2}]]], {a, b}, 5]

This allows the evaluation engine to manage the state changes.

The second is co-mingling the "choice" logic with the "update" logic by having the RandomInteger expression explicit in the update expression. Whenever you use a Random* function directly, you make things harder to test. Your concern now is that all of your simulations are corrupted, and that's why we want to be able to test things directly. Yes, you can use SeedRandom, but then you still need to know what actual sequence of random variables was used to verify the results. Usually better to separate out the thing that will be random and then swap later after you've convinced yourself that things are working. So, something like

myPrivateVariable = 1;
myIndexChooser[] := myPrivateVariable = Mod[1 + myPrivateVariable, 2, 1];
Nest[Function[list, MapAt[# + 1 &, list, myIndexChooser[]]], {a, b}, 5]

I'd do more to encapsulate the private variable, and I'd probably do something more sophisticated in terms of the actual chooser implementation, but this shows the gist. You don't always need a full-blown chooser function, just some way to separate the making of the choice from the applying of the choice. So even this can work:

With[
  {idx = RandomInteger[{1, 2}]},
  x[[idx]]++]

None of this is to say that there isn't a real bug here. And I wouldn't say that the above things should be used because there somehow resilient to language implementation bugs. I'm just saying that your style of programming already has some other risks independent of the fact that you hit on an actual bug.

Update

Or, given kglr's explanation, which makes it seem obvious in hindsight, your side-effect based and conflated code style was indeed the cause of your errors.

$\endgroup$
5
$\begingroup$

I suspect this is a subtle interaction between the HoldFirst attribute of Increment and the HoldAll attribute of While.

Possible Fix? Adding a semicolon inside the While block in your second code, i.e.,:

ch = ConstantArray[0, 2];
While[Min[ch] == 0,
 ch[[RandomInteger[{1, 2}]]]++;];
ch

appears to resolve the problem. (A similar modification to your second example also brings the two results into agreement.)

Note added in edit: In the comment thread, @kglr seems to have found that this doesn't work.

A functional alternative (added 11 Nov)

I'm in agreement with @lericr ... I wouldn't implement it the way that the OP did, as it seems like it opens up a possible confusion about operation order. I would personally be inclined to implement it in a more functional style like the following:

update[state_] := With[
  {index = RandomInteger@Range@Length[state]},
  state + UnitVector[Length[state], index]]

NestWhile[update, {0, 0}, ContainsAny[{0}]]
$\endgroup$
2
  • $\begingroup$ Fascinating, thank you! This is a kind of devastating bug since it could've subtly corrupted all my simulations. Is there any principle you can articulate by which one could make one's code more robust to this kind of thing? Also I guess we better report this to Wolfram Research. $\endgroup$
    – dreeves
    Nov 10, 2023 at 20:24
  • 2
    $\begingroup$ SeedRandom[3]; ch = ConstantArray[0, 2]; While[Min[ch] == 0, ch[[RandomInteger[{1, 2}]]]++;]; ch gives {3,2} in Version 13.3.1 for Linux x86 (64-bit) (July 24, 2023) $\endgroup$
    – kglr
    Nov 10, 2023 at 20:41
3
$\begingroup$

Turns out we have a bonafide Wolfram Language bug here. With help from you all, I've pared it down to this:

SeedRandom[0];
x = {a, b};
x[[RandomInteger[{1, 2}]]]++;
x

Bizarrely, that returns {1 + b, b}. The a gets lost. Instead of incrementing either the first or second element of x it adds one to the second element and replaces the first element with it.

PS: As @kglr has explained, the reason this happens is that RandomInteger is called twice. Once to pick the element and once again to do the incrementing. This version may illustrate that better:

callcount = 0;

getindex[] := (Print["the index is ", callcount+1]; ++callcount)

array = {a, b, c};
array[[getindex[]]]++;
array

The output:

the index is 1
the index is 2
{a, 1 + a, c}

Which confirms that getindex[] is called twice and, since it returns different values each time, the results are all wrong, assigning the first element plus one to the second element.

$\endgroup$
3
  • 2
    $\begingroup$ SeedRandom[0]; x = {a, b};Trace[x[[RandomInteger[{1, 2}]]]++; x] // Column shows RandomInteger is called twice ; first to determine what to increment (say, a), and then to determine the part to which a+1 is assigned. $\endgroup$
    – kglr
    Nov 10, 2023 at 21:26
  • $\begingroup$ Ah, makes so much sense now that you say that! Now I'm wondering if I was hasty in calling it a bonafide bug? Still seems a bit insidious... $\endgroup$
    – dreeves
    Nov 10, 2023 at 21:28
  • 1
    $\begingroup$ perhaps a bit more clearly, SeedRandom[0]; x = {a, b}; Reap[x[[Sow@RandomInteger[{1, 2}]]]++; x] gives {{a, 1 + a}, {{1, 2}}} $\endgroup$
    – kglr
    Nov 10, 2023 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.