Back to Homepage

Frequency of occurrence of situation Q[x]=P[x+1] for VMPC1


For a random permutation P of n>1 elements and 1-level VMPC function (Q[x]=P[P[P[x]]+1]): Q[x]=P[x+1] occurs with probability 2/n.

Explanation: For a random permutation P, P[P[x]]=x occurs with probability 2/n.
[proof: P[P[x]]x when (z=P[x]x) AND (assuming the first condition, P[z]x), thus with probability
((n-1)/n) * ((n-2)/(n-1)) = 1 - 2/n]

Put back into Q[x]=P[P[P[x]]+1] we get that Q[x]=P[x+1] occurs with probability 2/n.
Each of the other n-1 values of Q[x] occur with equal probability (n-2)/(n*(n-1)).

A statistical test on 2 billion pseudo-radomly generated 256-element permutations shows that the standard deviation from the expected value of 1/128 is on average about zero (-0.23) and within range (-5.5, 4.3).

by Francois Grieu
(statistical test by Bartosz Zoltak)

Copyright © 1999-2018 by Bartosz Zoltak