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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom