How to make an N-output selector from 2-output Bernoulli gates – Plugins & Modules

In a generative patch, suppose instead of playing the same sound on every loop, you want to randomly alternate between two different sounds. For this we often use a Bernoulli gate. It has one gate input and two gate outputs. Each input pulse gets sent to one of the two outputs. The other output keeps sending 0V.

The Bernoulli gate includes a probability control to determine how often the pulse is routed to the first or second output port. I will use this notation for a general Bernoulli gate of this kind.

Every branch on the tree has a probability. The top branch has trivial probability 1 because every time the gate input fires, it fires! The left branch coming out of the Bernoulli gate has probability p, and the right branch fires every time the left branch doesn’t, giving its probability as 1-p.

If you are familiar with using Bernoulli gates, sometimes you want to randomly route a pulse to more than 2 targets. For example, if you want each pulse to be routed with equal probability to 4 different target ports, you can connect 3 Bernoulli gates into a “probability tree” like this:

All 3 gates have their probability knob set to p = 1/2.

It takes a little more thought to solve for randomly picking one of 3 targets with equal probability. The idea is that you take 1/3 of the pulses for one of the outputs, then the remaining 2/3 gets split in half to get another pair of 1/3 probability outputs.

To solve for a larger number of outputs N, divide N by two, with any odd remainder added to the left. For example, if N = 7, we want 4 out of 7 pulses to go left, 3 out of 7 to go right. That means we have a top-level Bernoulli gate with the probability branches 4/7 and 3/7.

Now we need to split the 4/7 of the leftward pulses 4 equal ways to get the desired 1/7 probability for each of the 7 output gates. And the 3/7 of the pulses moving to the right need to be split 3 ways.

We can recursively re-use the solutions for 3 and 4 to make the solution for 7:

This solution is not unique; there are other solutions but the tree height is more variable (i.e. the tree is less “balanced”). Regardless of tree shape, you always need N-1 Bernoulli gates to select from N targets.

Any path you take from the top of the diagram, through Bernoulli gates and branches, all the way to a given output, should have probability weights that multiply to 1/N. For example, the leftmost path in the 7-output solution is: (4/7) (1/2) (1/2) = 1/7.

I thought this was both mathematically interesting and useful in practice. I hope someone else finds this interesting too.