关于生成独立随机字符串

### 关于生成独立随机字符串 在计算机科学领域，随机字符串的生成和应用是一个重要的研究方向。本文将探讨如何从具有一定随机性和独立性的字符串中，有效地构造出更多随机且相互独立的字符串。 #### 1. 引言 在研究随机字符串时，我们从柯尔莫哥洛夫复杂度的角度来衡量字符串的随机性。对于一个二进制字符串 $x$，其随机性由柯尔莫哥洛夫复杂度 $K(x)$ 表示，随机率定义为 $K(x)/|x|$，其中 $|x|$ 是字符串的长度。当随机率接近 1 时，我们认为该字符串是随机的。 显然，不能凭空创造随机性。当仅从一个字符串 $x$ 出发时，不存在可计算函数能生成具有更高随机率的字符串 $y$，也无法生成相对于 $x$ 具有非恒定柯尔莫哥洛夫复杂度的“新”随机字符串。因此，我们需要分析从两个或多个具有一定随机性和独立性的字符串出发，能实现什么目标。 在某些情况下，存在积极的解决方案。例如，Fortnow 等人展示了对于任意 $\sigma$，存在常数 $\ell$ 和多项式时间过程，能从 $\ell$ 个 $n$ 位字符串构造出一个 $n$ 位字符串，其柯尔莫哥洛夫复杂度满足一定条件。 本文聚焦于输入为两个长度为 $n$ 的字符串 $x$ 和 $y$ 的情况。若 $K(x) - K(x | y) \leq \alpha(n)$ 且 $K(y) - K(y | x) \leq \alpha(n)$，则称 $x$ 和 $y$ 的依赖度至多为 $\alpha(n)$。当 $\alpha(n) = O(\log n)$ 时，称 $x$ 和 $y$ 是独立的。我们提出以下两个问题： - 问题 1：给定具有一定随机性和独立性的 $x$ 和 $y$，是否能有效/高效地构造出随机字符串 $z$？ - 问题 2：给定具有一定随机性和独立性的 $x$ 和 $y$，是否能有效/高效地构造出随机且与 $x$、$y$ 以及彼此之间依赖度小的字符串？能产生多少这样的“新”随机字符串？ #### 2. 相关概念 ##### 2.1 柯尔莫哥洛夫复杂度 设 $M$ 是一个标准图灵机，对于任意字符串 $x$，其相对于 $M$ 的柯尔莫哥洛夫复杂度定义为 $K_M(x) = \min\{|p| | M(p) = x\}$。存在通用图灵机 $U$，使得对于所有 $x$，$K_U(x) \leq K_M(x) + c$。我们固定这样的通用机 $U$，并记 $K(x)$ 为 $x$ 相对于 $U$ 的柯尔莫哥洛夫复杂度。 条件柯尔莫哥洛夫复杂度 $K(x | y)$ 定义类似，它表示在给定 $y$ 的条件下 $x$ 的柯尔莫哥洛夫复杂度。信息对称性定理表明，对于所有字符串 $x$ 和 $y$，有 $|(K(x) - K(x | y)) - (K(y) - K(y | x))| \leq O(\log K(x) + \log K(y))$。当 $x$ 和 $y$ 长度为 $n$ 时，$|(K(x) - K(x | y)) - (K(y) - K(y | x))| \leq 2 \log n + O(1)$。 有时需要以自定界的方式连接两个字符串 $a$ 和 $b$，一种更高效的编码方式是：设 $|a|$ 的二进制表示为 $c_1c_2 \cdots c_k$，则 $concat(a, b) = c_1c_1c_2c_2 \cdots c_kc_k01ab$，且 $|concat(a, b)| = |a| + |b| + 2\lfloor\log |a|\rfloor + 4$。 ##### 2.2 独立字符串 - 定义 1： - (a) 两个字符串 $x$ 和 $y$ 至多为 $\alpha(n)$ - 依赖的，如果 $K(x) - K(x|y) \leq \alpha(|x|)$ 且 $K(y) - K(y|x) \leq \alpha(|y|)$。 - (b) 字符串 $(x_1, x_2, \cdots)$ 两两至多为 $\alpha(n)$ - 依赖的，如果对于任意 $i \neq j$，$x_i$ 和 $x_j$ 至多为 $\alpha(n)$ - 依赖的。 ##### 2.3 平衡表 表是一个函数 $T : [N] \times [N] \to [M]$，在我们的应用中，$N = 2^n$，$M = 2^m$。我们将 $[N]$ 与 $\{0, 1\}^n$ 等同，$[M]$ 与 $\{0, 1\}^m$ 等同。 可以将这样的函数看作一个 $N$ 行 $N$ 列的二维表，每个单元格有一种来自集合 $[M]$ 的颜色。对于 $[N]$ 的子集 $B_1$ 和 $B_2$，表 $T$ 的 $B_1 \times B_2$ 矩形是由 $B_1$ 中的行和 $B_2$ 中的列组成的部分。如果 $A \subseteq \{0, 1\}^m$ 且 $(x, y) \in [N] \times [N]$，当 $T(x, y) \in A$ 时，称单元格 $(x, y)$ 是 $A$ - 着色的。 在证明中，我们需要各种表是平衡的，即每个足够大的矩形 $B_1 \times B_2$ 中，所有颜色出现的次数大致相同。 - 定义 2：设 $k \in N$。表 $T$ 是 $(S, n^k)$ - 强平衡的，如果对于任意满足 $B_1 \subseteq [N]$，$|B_1| \geq S$，$B_2 \subseteq [N]$，$|B_2| \geq S$ 的集合对 $B_1$ 和 $B_2$，以下两个不等式成立： - (1) 对于每个 $a \in [M]$，$|\{(x, y) \in B_1 \times B_2 | T(x, y) = a\}| \leq \frac{2}{M} |B_1 \times B_2|$。 - (2) 对于每个 $(a, b) \in [M]^2$ 和每个 $(i, j) \in [n^k]^2$，$|\{(x, y) \in B_1 \times B_2 | T(x + i, y) = a \text{ 且 } T(x + j, y) = b\}| \leq \frac{2}{M^2} |B_1 \times B_2|$，其中加法是模 $N$ 运算。 使用概率方法，在某些参数设置下，可以证明强平衡表的存在性。 - 引理 1：如果 $S^2 > 3M^2 \ln M + 6M^2 \cdot k \cdot \ln n + 6SM^2 + 6SM^2 + 6SM^2 \ln(N/S) + 3M^2$，则存在 $(S, n^k)$ - 强平衡表。当 $M = o((1/\sqrt{n})S^{1/2})$ 时，该条件满足。 这种证明方法未指出构造此类表的高效方式，在应用中，我们通过穷举搜索来构建，此操作可在 EXPSPACE 中完成。 使用 Rao 的结果，可以在多项式时间内构造一种较弱类型的平衡表。 - 事实 1：对于任意 $\delta > 0$，$\epsilon > 0$，存在常数