Riffle is Biased!

[Darin.K]

As the unofficial chairman of the National Riffle Association, I was seriously ticked off this morning to discover a major flaw in the LV implementation of the good, old Fisher Yates shuffle.  Fortunately, when it matters to me, I never use code that I can not trace back to the source, so I have always used my own implementations.  But myself, and one or perhaps two others, have tried to raise awareness of this potentially nifty VI.

I have included a VI which repeatedly Riffles an array of integers 0..9.  It then calculates the distribution of final position for each value as well as the distribution of values for each index in the riffled array.  This should be flat, but notice the bias near the edges.  For reference I have added a simple implementation of the FY shuffle, notice the lack of bias in the results.   

Other than license protection (Riffle is FDS+), why is the implementation of such a standard algorithm hiding in a CLFN?  Why is the algorithm, like many others not referenced?

Tested in LV9, LV10 on Windoze.

[tst]

---

@Darin.K wrote:

Other than license protection (Riffle is FDS+), why is the implementation of such a standard algorithm hiding in a CLFN?

---

• Allows reuse of the code in other products (such as CVI)?
• Speed (an old VI, so you would have to test it in an old version to confirm)?

[Darin.K]

---

tst wrote:

• Allows reuse of the code in other products (such as CVI)?
• Speed (an old VI, so you would have to test it in an old version to confirm)?

---

I'll buy speed considering Ramp still uses a CLFN as well.  I'd like to see more G and less C from NI, although refurbishing older VIs is probably not a path to more sales.  Maybe I'll OpenG a VI or two one of these days.

[jcarmody]

---

@Darin.K wrote:

As the unofficial chairman of the National Riffle Association,[...]

---

"I'll give up my Signal Operation VIs when someone pries my cold dead fingers from around their connector panes." ~ Charlton "CrossCorrelation" Heston

[Darin.K]

During some afternoon coffee, it was not too hard to figure out the blunder as it is one of the oldest ones in the book.  The algorithm being used by the Riffle VI takes each index in the array and swaps it with a randomly chosen element.  Nice and simple, right?  Unfortunately, in this case the method is generating 10^10 combinations when we all know that there are 10! = 3,6280,800 possible permutations.  Since 10^10 is not divisible by 10!, not all configurations are going to be equally represented, therefore bias.

The Fisher-Yates method generates the correct number of combinations so they are all equally likely.

The help for Riffle claims that both indices for the swap are chosen randomly, this would be even worse.

Choose 'Mod Riffle' to compare the method I described to the Riffle results.

[Hornless.Rhino]

It almost looks like a saddle function as the top surface.

What happens if you go beyond 9 say, to 99.

[tst]

---

@Darin.K wrote:

The help for Riffle claims that both indices for the swap are chosen randomly, this would be even worse.

---

I don't know anything about the riffle algorithm, but doing that should result in ~14% of the elements never been moved. I'm not sure what effect that would have on the distibution. You can see some details here - http://lavag.org/topic/3238-randomise-array/page__view__findpost__p__15997

[altenbach]

Just some links to other related discussions:

Now available for download: "Randomize 1D Array.vi" that accepts any array type

Randomize Array

And yes, I agree this does not look good and should be fixed.

[Darin.K]

---

@tst wrote:

---

@Darin.K wrote:

The help for Riffle claims that both indices for the swap are chosen randomly, this would be even worse.

---

I don't know anything about the riffle algorithm, but doing that should result in ~14% of the elements never been moved. I'm not sure what effect that would have on the distibution. You can see some details here - http://lavag.org/topic/3238-randomise-array/page__view__findpost__p__15997

---

I guess I did not leave it in the second test VI, but as you suspected choosing two random indices results in the original array being the most probable configuration. The graph shows a ridge along the diagonal with a value of roughly 14%.

[altenbach]

Form same casual benchmarking, your FY-shuffle beats riffle by about 25% if made into a subVI (debugging disabled). Curioulsy, it is only faster if either inlined or fully reentrant. It almost looks like a reentrant version is inlined even if not specifically so configured.

I have never seen a subVI that changes speed by a factor of two between reentrant and non-reentrant. I guess the code is small enough that the compiler decides to inline the reentrant version even if not secifically inlined. Maybe I am completely off. 😉