Premium
Simple permutations mix even better
Author(s) -
Brodsky Alex,
Hoory Shlomo
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20194
Subject(s) - combinatorics , permutation (music) , simple (philosophy) , mathematics , notation , random permutation , derangement , parity of a permutation , simple random sample , discrete mathematics , symmetric group , cyclic permutation , arithmetic , physics , population , philosophy , demography , epistemology , sociology , acoustics
We study the composition of random permutations drawn from a small family of O ( n 3 ) simple permutations on {0,1} n . Specifically, we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k ‐wise independent. We improve on the results of Gowers (Combin Probab Comput 5 (1996) 119–130) and Hoory et al. (Presented at 31st ICALP 2004) and show that it suffices to compose min( O ( n 3 k 2 ), Õ ( n 2 k 2 )) random permutations from this family for any n ≥ 3 and k ≤ 2 n − 2. The Õ notation suppresses a polylogarithmic factor in k and n . © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008