Let $E$ be a random even permutation of the set $\{0\dots n-1\}$. We construct a permutation $P$ of the set $\{0\dots m-1\}$, for some $m\le n$, using cycle-walking; that is, computing $P(x)$ is as follows:
- repeat
- $x\gets E(x)$
- until $x<m$
- output $x$
What is the probability that the parity of $P$ is $n-m\bmod 2$, as a function of $m$ and $n$? How low should be $m$ so that this is withing $\pm\epsilon$ of $1/2$?
The motivation was to decide if cycle-walking is enough to transform a small Feistel Cipher into a pseudo-random permutation of a smaller domain, in the cipher of this question. Poncho rightly pointed out that in a Feistel cipher, using modular addition rather than XOR also achieves this goal.
I observe that when $n-m\ll\sqrt n$, probability that $P$ has parity $n-m\bmod 2$ is high, because for most $E$, there are $2m-n$ values of $x<m$ such that the repeat loop is executed once, and $n-m$ values such that the repeat loop is executed twice.
