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




For a random permutation P of n>1 elements and 1level 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
((n1)/n) * ((n2)/(n1)) = 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 n1 values of Q[x] occur with equal probability (n2)/(n*(n1)).
A statistical test on 2 billion pseudoradomly generated 256element 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 © 19992018 by Bartosz Zoltak

