Understanding Circulant Permutation to Extend the CMinHash Estimator

Keegan Kang; Avery Hood; Benedict H. W. Wong

stat.MLOct 13, 2026

Understanding Circulant Permutation to Extend the CMinHash Estimator

Authors: Keegan Kang, Avery Hood, Benedict H. W. Wong

Organizations: Department of Mathematics and Statistics Bucknell University Lewisburg, PA 17837 · Institute for Infocomm Research (I2R) A*STAR Singapore, 138632

Abstract

CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.

Figures & tables

\displaystyle\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Permutation}&6&1&7&4&5&8&3&2\\ \hline\cr\text{Set 1}&\bullet&\circ&\circ&\bullet&\circ&{\bullet}&\circ&\boxed{\bullet}\\ \text{Set 2}&\circ&\boxed{\bullet}&\bullet&\bullet&\circ&\circ&{\bullet}&\bullet\\ \end{array}~~\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Draw Order}&1&2&3&4&5&6&7&8\\ \hline\cr\text{Set 1}&\circ&\boxed{\bullet}&\circ&\bullet&\circ&\bullet&\circ&\bullet\\ \text{Set 2}&\boxed{\bullet}&\bullet&\bullet&\bullet&\circ&\circ&\bullet&\circ\\ \end{array}

Figure 1: We have

\left|\mathcal{S}_{1}\right|=4

\left|\mathcal{S}_{2}\right|=5

. By treating a random permutation (left) as the indices where we sample without replacement (right),

\min\{\pi(\mathcal{S}_{1})\}=2

\min\{\pi(\mathcal{S}_{2})\}=1

, which is just the index where the first

\bullet

appears.

\displaystyle\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Permutation}&3&2&6&1&7&4&5&8\\ \hline\cr\text{Set 1}&\bullet&\circ&\circ&\boxed{\bullet}&\circ&{\bullet}&\circ&{\bullet}\\ \text{Set 2}&\circ&{\bullet}&\bullet&\boxed{\bullet}&\circ&\circ&{\bullet}&\bullet\\ \end{array}~~~~~\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Draw Order}&1&2&3&4&5&6&7&8\\ \hline\cr\text{Set 1}&\boxed{\bullet}&\circ&\bullet&\bullet&\circ&\circ&\circ&\bullet\\ \text{Set 2}&\boxed{\bullet}&\bullet&\circ&\circ&\bullet&\bullet&\circ&\bullet\\ \end{array}

Figure 2: The permutation

\pi

in Figure 2 is shifted rightward from Figure 1 by 2 units. Then

\min\{\pi_{\rightarrow 2}(\mathcal{S}_{1})\}=\min\{\pi_{\rightarrow 2}(\mathcal{S}_{2})\}=1

Figure 3: Empirical MSE vs theoretical approximate variance in Theorem 2 of MinHash and CMinHash

(\sigma,\pi)

. The dotted lines overlap almost perfectly (up to Monte Carlo error), which shows our theoretical approximate variance matches the empirical variance.

\displaystyle\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Draw Order}&1&2&3&4&5&6&7&8\\ \hline\cr\text{Set 1}&\circ&\bullet&\circ&\bullet&\bullet&\bullet&\circ&\bullet\\ \text{Set 2}&\circ&\circ&\circ&\circ&\circ&\circ&\circ&\boxed{\bullet}\\ \end{array}

Figure 4: We have

\min\{\pi_{t}(\mathcal{S}_{2})\}=8

, with

y_{t}=1

, which can be thought of as the presence (or absence) of a

\bullet

at draw 8 for

\mathcal{S}_{1}

, and

m_{t}=4

, which can be thought of as counting how many

\bullet

were seen in previous draws 1-7 for

\mathcal{S}_{1}

Figure 5: Empirical MSE vs theoretical approximate variance in Theorem 4 for count data. The dotted lines overlap almost perfectly for the last three plots.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Draw	First entry	Second entry	Tuple
	under $\pi_{\rightarrow s}$	under $\pi_{\rightarrow s+\Delta}$
Draw 1	$\widetilde{-}$	${\bf\widetilde{O}}$	$(\widetilde{-},{\bf\widetilde{O}})$
Draw 2	$\widetilde{-}$	$\widetilde{-}$	$(\widetilde{-},\widetilde{-})$
Draw 3	${\bf\widetilde{O}}$	$\widetilde{-}$	$({\bf\widetilde{O}},\widetilde{-})$
Draw 4	$\widetilde{\times}$	$\widetilde{O}$	$(\widetilde{\times},\widetilde{O})$
Draw 5	$\widetilde{O}$	$\widetilde{\times}$	$(\widetilde{O},\widetilde{\times})$

Appendix

Table 1: Five successive tuples from one random permutation, for

D=5

s=1

and

\Delta=4

. The first entry corresponds to

\pi_{\rightarrow s}

and the second entry to

\pi_{\rightarrow s+\Delta}

	Example 1	Example 2	Example 3	Example 4	Example 5
Draw 1	$(\widetilde{-},\widetilde{-})$	$(\widetilde{-},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$
Draw 2	$(\widetilde{-},{\bf\widetilde{O}})$	$(\widetilde{-},{\bf\widetilde{O}})$	$(\widetilde{\times},\widetilde{\times})$	$({\widetilde{O}},\widetilde{-})$	$(\widetilde{-},\widetilde{-})$
Draw 3	$({\bf\widetilde{O}},\widetilde{-})$	$(\widetilde{-},\widetilde{\times})$		$({\widetilde{O}},\widetilde{-})$	$(\widetilde{-},\widetilde{-})$
Draw 4		$({\bf\widetilde{O}},\widetilde{-})$		$(\widetilde{\times},{\bf\widetilde{O}})$	$(\widetilde{-},{\bf\widetilde{O}})$

Appendix

Table 2: Five examples of sequences of draws. Each example is a vertical column.

	Example 1	Example 2	Example 3	Example 4	Example 5
Draw 1	$(\widetilde{-},\widetilde{-})$	$(\widetilde{-},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$
Draw 2	$(\widetilde{-},{\bf\widetilde{O}})$	$(\widetilde{-},{\bf\widetilde{O}})$	$(\phantom{\widetilde{O}},\widetilde{\times})$	$(\phantom{{\bf\widetilde{O}}},\widetilde{-})$	$(\phantom{\widetilde{-}},\widetilde{-})$
Draw 3	$({\bf\widetilde{O}},\phantom{\widetilde{-}})$	$(\widetilde{-},\phantom{\widetilde{\times}})$		$(\phantom{\bf\widetilde{O}},\widetilde{-})$	$(\phantom{\widetilde{-}},\widetilde{-})$
Draw 4		$({\bf\widetilde{O}},\phantom{\widetilde{-}})$		$(\phantom{\widetilde{O}},{\bf\widetilde{O}})$	$(\phantom{\widetilde{-}},{\bf\widetilde{O}})$

Appendix

Table 3: Five examples of sequences of draws, where we do not record the type of entry after the first

\widetilde{O}

is drawn. Each example is a vertical column.

	Case 1	Case 2a	Case 2b	Case 3a	Case 3b
	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
	$(\widetilde{-},{\bf\widetilde{O}})$	$(\widetilde{-},\widetilde{-})$	$(\widetilde{-},{\bf\widetilde{O}})$	$(\widetilde{-},{\bf\widetilde{O}})$	$\vdots$
	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
	$(\widetilde{-},\phantom{\widetilde{O}})$	$\vdots$	$(\widetilde{-},\phantom{\widetilde{O}})$	$\vdots$	$\vdots$
	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
Draw $t$	$({\bf\widetilde{O}},\widetilde{\times})$	$({\bf\widetilde{O}},{\bf\widetilde{O}})$	$({\bf\widetilde{O}},\widetilde{O})$	$({\bf\widetilde{O}},\widetilde{-})$	$({\bf\widetilde{O}},\widetilde{-})$

Appendix

Table 4: Pictorial intuition of the five (sub)cases of successes we consider, as we condition on the first

\widetilde{O}

seen in the first entry of the tuple. A bold

{\bf\widetilde{O}}

denotes the first

\widetilde{O}

seen for that entry. A blank entry in a tuple means it does not matter what that entry is since an

\widetilde{O}

was drawn before.

Figure 6: Empirical MSE vs theoretical approximate variance in Theorem 2 of MinHash and CMinHash

(\sigma,\pi)

, at edge cases when

f

is small. At

f=2,4

, the dotted lines do not overlap perfectly, but they do at

f=6,8

Figure 7: Empirical MSE versus both theoretical approximate variances in Theorem 2 of MinHash and CMinHash

(\sigma,\pi)

for selected word pairs. CMH Var (S) is the the sparse case where

\frac{f_{1}}{D}\rightarrow 0

. CMH Var (NS) is the the non-sparse case where

\frac{f_{1}}{D}

does not tend to zero. Both theoretical approximations and empirical MSE lines overlap perfectly.

\displaystyle\begin{array}[]{c | c c c c c c c c c c c c c}\text{\bf Draw Order}&1&2&3&4&5&6&7&8\\ \hline\cr\text{Set 1}&\circ&\bullet&\circ&\bullet&\bullet&\bullet&\circ&\bullet\\ \text{Set 2}&\circ&\circ&\circ&\circ&\circ&\circ&\circ&\boxed{\bullet}\\ \end{array}

Appendix

Figure 4: We have

\min\{\pi_{t}(\mathcal{S}_{2})\}=8

, with

y_{t}=1

, which can be thought of as the presence (or absence) of a

\bullet

at draw 8 for

\mathcal{S}_{1}

, and

m_{t}=4

, which can be thought of as counting how many

\bullet

were seen in previous draws 1-7 for

\mathcal{S}_{1}

Figure 9: Empirical MSE vs theoretical approximate variance in Theorem 4 at edge cases when

f_{i}

are small respective to

D

. We use

(f_{1},f_{2},a)=(6,8,2)

Figure 10: Empirical MSE vs theoretical approximate variance in Theorem 4 at edge cases when

f_{i}

are small respective to

D

. We use

(f_{1},f_{2},a)=(18,24,6)

Figure 11: Empirical MSE vs theoretical approximate variance in Theorem 4 at edge cases when

f_{i}

are small respective to

D

. We use

(f_{1},f_{2},a)=(24,32,8)

Figure 12: Empirical MSE vs theoretical approximate variance in Theorem 4 at edge cases when

f_{i}

are small respective to

D

. We use

(f_{1},f_{2},a)=(48,64,16)

Figure 13: Empirical MSE vs theoretical approximate variance in Theorem 4 at edge cases when

f_{i}

are small respective to

D

. We use

(f_{1},f_{2},a)=(96,128,32)

Figure 14: Empirical MSE vs theoretical approximate variance in Theorem 4 for selected word pairs. Both theoretical approximations and empirical MSE lines overlap perfectly.

Variance Reduction

Variance reduction develops methods that make Monte Carlo estimates, gradients, and experimental comparisons more precise with limited data or computation.

See all 107 papers

Tight Sample Bounds for Renyi and Min-Entropy Estimation
Jul 18, 2026Arman Adibi, Piotr KrystaSample Complexity Information-Theoretic Lower Bounds
Department of Computer Science
Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
Sep 16, 2026Mohammad Azhar Khan, Rameshwar Pratap, Amit SharmaRandomized Sketching
Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502284, Telangana, India.
It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms
Jan 29, 2026Keegan Kang, Kerong Wang, Ding Zhang +3Parameter Estimation Exponential Family
Department of Mathematics and Statistics, Bucknell University, USA · School of Data Science, University of Virginia, USA · Department of CSE, IIT Hyderabad, India +2

Jul 18, 2026J/K move · Enter open · S save

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Arman Adibi, Piotr Krysta

Department of Computer Science

Sample Complexity Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a

k

-symbol alphabet using

Θ(k/\log k)

samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-

α

R'{e}nyi entropy,

H_α

. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for

k

and integer

α>1

; our lower bounds also hold for noninteger

α\ge1.001

. We prove that min-entropy estimation to constant additive accuracy has sample complexity

Θ(k\log k)

. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires

Θ(\log^2 k)

more samples than Shannon entropy and corrects a previously stated

Θ(k/\log k)

characterization. For every integer

2\leα\le c_0\log k

, we prove the matching fixed-accuracy bound

Θ_{c_0}(αk^{1-1/α})

. Previous results gave

Ω_α(k^{1-1/α})

for fixed integer

α>1

and

O_{c_0}(α^2k^{1-1/α})

for all integer

α>1

. Our upper bound analyzes an unbiased falling-factorial estimator based on

α

-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor

α

is unavoidable. For every real

1.001\leα\le c_0\log k

, we prove the uniform lower bound

Ω_{c_0}(αk^{1-1/α})

. Finally, since

0\le H_α(p)-H_\infty(p)\le\log k/(α-1)

, min-entropy uniformly approximates

H_α

when

α

is a sufficiently large multiple of

\log k

. Combining this reduction with our min-entropy bounds gives

Θ_\varepsilon(k\log k)

sample complexity in the high-order regime.

Abstract

Variance Reduction

Explore similar work

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms