Here's a tester patch
tester.zip

The only pattern introduced by the state is the pattern of excluding the current number from the output. But that's the same pattern you get from running random again.

Thus when the range is 0-1, both algorithms simply toggle between the two values. But when the range is 0-2 or 0-99, you can still see the convergence to the same value for the probability of choosing a 0. (Speed up the metro if you want them to converge more quickly.)

But when the range is 0-2 or 0-99, you can still see the convergence to the same value for the probability of choosing a 0. (Speed up the metro if you want them to converge more quickly.)

If I understand correctly what you have done, this tester patch is checking the percentage of the time that a single specific output comes out. The fact that it converges to 0.5 (1/2) for the case 2, 0.3333 (1/3) for the case 3 and 0.01 (1/100) for the case 100 simply means that both random abstractions are uniformly distributed, which is what I stated since the beginning. The patterns your abstractions produces can be seen for strings larger than that, as I have pointed out for strings sizes 3 and 4. So this test is testing something else, and something that I believe we knew since the first posts, right? I wrote in my first reply:

that's quite a nice solution! I did check that it is in fact uniformly distributed -- as expected --, but I feel quite uneasy about using a pseudorandom number generator producing N-1 integers for spitting out N integers by simple means of addition and module operation.

@jancsika I did some further tests concerning these patterns in strings of N digits I was observing, and it turns out there was a mistake in my code which I used for the analysis! After fixing it, those patterns disappeared and so they are in fact not present in your abstraction. I tested it for strings of 2, 3, 4 and 5 digits, and the frequency of all possible strings for each N case is exactly as expected: 1/(4*3^(N-1)), and I think it's safe to say this would hold for strings of any size. So apologies for the mistake, it was a small oversight on the code which went unnoticed.

I am still very curious on how we can map a set of random numbers into a set larger than itself, but I think I will need to ask some mathematician about it.

Cheers!
Gilberto

@jancsika After spending much time with this question, I think I finally figured out what is happening. The good news is that indeed there are absolutely no problems at all with your algorithm, and it is probably the best way to generate such sequences of non-repeating integer numbers.

At first sight, your algorithm seems to take as input random integers ranging between 0 and 2 (i.e. 3 values) and output random integers ranging between 0 and 3 (i.e. 4 values) for each cycle, which seems to be problematic due to upsampling (I explained what this means above). But actually the algorithm is always choosing among 3 options only, given that each value cannot be the same as the previous one. For instance, if the very first random integer selected is 0, there are three possible values for the next integer (1, 2 or 3), which is exactly what the range PRGN is providing. So the key is to realize that 3 random values are being mapped into 4 non-repeating random values, and this can be done without causing any unwanted patterns.

Therefore, there is no problem using MOD N+1 for a random input ranging from 0 to N, because the amount of information does not change with that. But when we use MOD N+2 or larger, we actually do observe patterns that shouldn't be there if the output was truly random. For instance, certain sequences of two consecutive numbers never appear: e.g. taking N = 3 (i.e. input between 0 and 2) and MOD 5, one will never see a 0 followed by a 4, since there is no input such that the expression ((input + 1) + 0) MOD 5 = 4 would be true.

Anyway, I hope this clear something up a bit. And now I finally can sleep at night

Cheers!
Gilberto

@gsagostinho random numbers are difficult and counter-intuitive.

Notice also that the seeding state is based on value shared among all the [random] objects that exist in the running Pd instance. That means the first [random 42] you create in a running Pd instance will always give the same output (for example).

Just to be clear, what I wrote before has nothing to do with seeding, I was talking about patterns that would emerge regardless of which seed is selected, e.g. patterns that are intrinsic to certain algorithms and which are undesirable side effects of certain PRGN.

The problem I had was simply that at first sight you seem to be creating "information" out of nowhere, in your case taking a random numbers among 3 possibilities and transforming it into another one among 4 possibilities, which shouldn't be possible to do. Then I realized that actually there is nothing wrong in your case, since you can't repeat the previous number of the sequence, and therefore you are always having 3 options anyway, which is what the PRGN is giving you.

The only moment your algorithm still fails is for the very first number: it never outputs a 0! But if you use this trick below with a [loadbang], you feed a random starting value to the [+] and therefore the algorithm can have any value between 0 and 3 as first output:

Cheers,
Gilberto

@gsagostinho said:

Just to be clear, what I wrote before has nothing to do with seeding, I was talking about patterns that would emerge regardless of which seed is selected, e.g. patterns that are intrinsic to certain algorithms and which are undesirable side effects of certain PRGN.

The problem I had was simply that at first sight you seem to be creating "information" out of nowhere, in your case taking a random numbers among 3 possibilities and transforming it into another one among 4 possibilities, which shouldn't be possible to do. Then I realized that actually there is nothing wrong in your case, since you can't repeat the previous number of the sequence, and therefore you are always having 3 options anyway, which is what the PRGN is giving you.

Stated differently, I think you were focusing on the four possibilities inside a single object of the OP's black box-- i.e., in the [random] object-- while overlooking the fact that the recursive selection process limits the output to three.

The only moment your algorithm still fails is for the very first number: it never outputs a 0! But if you use this trick below with a [loadbang], you feed a random starting value to the [+] and therefore the algorithm can have any value between 0 and 3 as first output:

Good catch. But where zero originally had 0% probability, now it is too lucky (1/3 chance instead of 1/4).

So try [loadbang]----[random 4] (and leave off the [+ 1])

Stated differently, I think you were focusing on the four possibilities inside a single object of the OP's black box-- i.e., in the [random] object-- while overlooking the fact that the recursive selection process limits the output to three.

That's exact it. Three in, three out, no new information per cycle, no laws of probability broken.

Good catch. But where zero originally had 0% probability, now it is too lucky (1/3 chance instead of 1/4).

My bad, that should have been [random 4] of course!

Long story short: random numbers are hard to get right.