论文标题
使用扩展器图测试样品是否为I.I.D
Using Expander Graphs to test whether samples are i.i.d
论文作者
论文摘要
本说明的目的是指出，扩展器图理论会导致一个有趣的测试。对于任何独特的实数$ x_1，\ dots，x_n $，我们将4个常规图$ g $关联，如下所示：使用$π$表示订购元素的订单，$ x_ {π（1）} <x__ {π（π（2）} <x} <x____________________________________ { N \ right \} $通过连接$ i $和$ i+1 $（周期性）和$π（i）$和$π（i+1）$（周期性）。如果数字是I.I.D.然后，弗里德曼（Friedman）的结果意味着$ g $接近拉玛努扬（Ramanujan）。这表明了这些数字是否为I.I.D：计算邻接矩阵的第二大特征值（以绝对值）特征值进行测试。较大的$λ-2 \ sqrt {3} $，数字为i.i.d.我们解释了为什么这是一个合理的测试，并给出了许多例子。
The purpose of this note is to point out that the theory of expander graphs leads to an interesting test whether $n$ real numbers $x_1, \dots, x_n$ could be $n$ independent samples of a random variable. To any distinct, real numbers $x_1, \dots, x_n$, we associate a 4-regular graph $G$ as follows: using $π$ to denote the permutation ordering the elements, $x_{π(1)} < x_{π(2)} < \dots < x_{π(n)}$, we build a graph on $\left\{1, \dots, n\right\}$ 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\sqrt{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.
