{'fraction_non_alphanumeric': 0.05564924114671164, 'fraction_numerical': 0.011804384485666104, 'mean_word_length': 4.029661016949152, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On restricted min‐wise independence of permutations

A family of permutations ℱ ⊆ Sn with a probability distribution on it is called k‐restricted min‐wise independent if we have Pr[min π(X) = π(x)] = 1/|X| for every subset X ⊆ [n] with |X| ≤ k, every x ∈ X, and π ∈ ℱ chosen at random. We present a simple proof of a result of Norin: every such family has size at least Some features of our method might be of independent interest. The best available upper bound for the size of such family is 1 + ∑  kj=2 (j − 1)(  nj ). We show that this bound is tight if the goal is to imitate not the uniform distribution on Sn, but a distribution given by assigning suitable priorities to the elements of [n] (the stationary distribution of the Tsetlin library, or self‐organizing lists). This is analogous to a result of Karloff and Mansour for k‐wise independent random variables. We also investigate the cases where the min‐wise independence condition is required only for sets X of size exactly k (where we have only an Ω(log log n + k) lower bound), or for sets of size k and k − 1 (where we already obtain a lower bound of n − k + 2). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003