2020/08/03 by Stefan Steinerberger, Steinerberger, Stefan · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Random Matrices and Applications #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2008.01153
openalex publication_date 2020/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The purpose of this note is to point out that the theory of expander graphs leads to an interesting test whether n real numbers x1, …, xn could be n independent samples of a random variable. To any distinct, real numbers x1, …, xn, we associate a 4-regular graph G as follows: using π to denote the permutation ordering the elements, xπ(1) < xπ(2) < … < xπ(n), we build a graph on \1, …, n\ by connecting i and i+1 (cyclically) and π(i) and π(i+1) (cyclically). If the numbers are i.i.d. samples, then a result of Friedman implies that G is close to Ramanujan. This suggests a test for whether these numbers are i.i.d: compute the second largest (in absolute value) eigenvalue of the adjacency matrix. The larger λ- 2√(3), the less likely it is for the numbers to be i.i.d. We explain why this is a reasonable test and give many examples.