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[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
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)