I'm new to Pd and going through the official tutorial. And I'm am overcome by the complexity of the proposed solution to the first exercise, "2.2.1.2.7 Random without repetitions".

More precisely, I'd like to know why such complexity? Why would my attached patch cause problems?

Thanks in advance for your insights

But the smaller the limit number, the more likely it is you will get repeat numbers, and hence the less efficient this method becomes. If you choose [random 2], there is a 1/1024 chance that you'll get 10 in a row, which is not negligible. And if you take it to the absolute limit and make [randiff 1], you're going to get a stack overflow because it will always choose and then reject 0.

Here is a hybrid solution. random-hybrid.pd

If the number is rejected, it adds and wraps another random number, maximum n-1. That way it will never take more than 2 cycles, but also avoids the un-even distribution that Gilberto is worried about.

@cmnmnum Johannes Kriedler does have a peculiar patching style, and many of those examples can be made more efficient. I still have a lot of respect for the man though!

@gsagostinho I'll have to think about that one a bit more...

@cmnmnum You're right that in the manually-triggered example the extra cycles are unlikely to matter. I'm just thinking of situations where that functionality is made general inside an abstraction. Then the code could be used in many different contexts-- it its used rapidly to generate many random values while audio is running the cycles could become important. (Especially if one employed many copies of the abstraction in a more complex patch.)

@gsagostinho Do you mean that someone using my abstraction as a model could easily lead to unintended side effects, or are you saying that the abstraction itself has side-effects which the first two approaches do not?

@jancsika I mean that the model could have unintended side effects. Supposing these side effects exist, they might be noticeable or not depending on what you use the pseudorandom numbers for. For instance, generating 20 numbers in order to select random chords for a composition very likely won't give you enough data to see side effects, but if you generate a million of them then you might spot something. Any PRNG should output numbers that are uniformly distributed, and as I mentioned to you your abstraction does do that correctly, but there are other characteristics that can be observed, for instance the presence of patterns in the output.
For instance, PRNG do cycle back and start outputting the same series of numbers again in the same order, and the larger these cycles (periods) are the better a generator is. If you think about it, a simple counter does fulfil the uniform distribution requirement, but those "random" numbers it output will be very poor given that they have a short cycle of repetition (e.g. 0 1 2 0 1 2 0 1 2). On the other hand, the RANDOM_NUMBER subroutine in Fortran has a period of 2^1024 - 1 (aprox. 10 to the 308 power), and so that is an excellent period size. And then there are other types of side effect that could be observed (see for instance https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Potential_problems_with_deterministic_generators ).

@LiamG

That way it will never take more than 2 cycles, but also avoids the un-even distribution that Gilberto is worried about.

To be precise, I do think that solution is uniformly distributed as I checked it for very large numbers, my worries is concerning other side effects. I just can't wrap my head around the idea of using N input numbers to generate N+1 output numbers without side effects.

@gsagostinho I'm going to go ahead and claim that they are functionally equivalent. But if I'm wrong I'd love to see a demo showing the side-effect.

@jancsika

I'm going to go ahead and claim that they are functionally equivalent.

Well, a claim like this does not bring much to the table, does it?

But if I'm wrong I'd love to see a demo showing the side-effect.

I think I found just that. I created a large number of outputs from your algorithm and analysed it for patterns that shouldn't be there. So even if the output of a PRGN does obey a uniform distribution, it will still be weak if it show certain patterns (remember, randomness is the lack of patterns). I calculated the frequency of every string of size 4 output by your algorithm, and the results display a quite non-random behaviour. See, there are 4×3×3×3 = 108 possible strings of size 4 of non-repeating numbers (4 options for the first position, 3 for the second position since it can't repeat the previous, 3 again for the third position since it can't repeat the value of second position and 3 for the last position for the same reason). So it means that any string of 4 numbers should appear 1/108 = 0.009259259 = 0.9 % of the time. What I found out is that your algorithm is not able to output any sequence of four digits in which every digit is unique (e.g. {0,1,2,3}, {3,1,0,2}, {2,0,1,3}, etc.). If out of those 108 possibilities we remove the 24 that are made out of unique numbers (4×3×2×1 = 24), we then have 84 options. And indeed all other strings appear 1/84 = 0.011904762 = 1.2% of the time each. This shouldn't be a characteristic of a PRNG.

I then took a quick look at strings of size 3. I found that several strings do not appear either, such as {0,1,2}, {2,3,0}, {3,0,1}, {0,1,0}, {0,2,0}, and so the ones that appear do it much more frequently than they are supposed to. In fact, I believe that this behaviour will be present in strings of any size. And I am quite certain that this is a side effect of the mapping I mentioned before.

Hope this helps, cheers!
Gilberto

@LiamG and in that case, I suspect your hybrid algorithm above will also have some undesirable side effects.

@gsagostinho said:

@jancsika

I'm going to go ahead and claim that they are functionally equivalent.

Well, a claim like this does not bring much to the table, does it?

True.

Suppose that instead of trying again on contiguous repetitions the original patch instead used [random 10] and tried again for all outputs between 2 and 9.

Ignoring the cpu usage, is the output of such a patch functionally equivalent to [random 2] or not?

@jancsika I believe so, because a good PRNG is trying to emulate true randomness, and true random events are not affected by previous or future events.

This is why the approach of ignoring repetitions by [random] might be better, since a repeated number is simply ignored, and the chance of having {0,0} is the same as {1,1} or {2,2} etc., and so no pattern is introduced.

@gsagostinho said:

@jancsika I believe so, because a good PRNG is trying to emulate true randomness, and true random events are not affected by previous or future events.

Ok.

Is a revised version of OP's patch where N = 2 equivalent to [random-no-contiguous-repeasts-in-constant-time 2] or not?

Edited: originally compared to [random 2] which is wrong

@jancsika

Is a revised version of OP's patch where N = 2 equivalent to [random-no-contiguous-repeasts-in-constant-time 2] or not?

Sorry but I do not understand, which version of the OP's patch are you talking about? This one here?

And if so, I do not understand what you want to compare it to (I got confused by what you mean with the [random-no-contiguous-repeasts-in-constant-time 2] ).

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!