固定长度k的字w∈{0,1}^k，求(0,1)中几乎处处x的二进制展开中w的出现频率

问题回顾 #

固定长度为$k$的二进制字$w \in {0,1}^k$，求集合$(0,1)\setminus { \frac{p}{2^n}: 0<p<2^n; n\geq 1}$中几乎每个$x$，其二进制展开里$w$的出现频率。

你的思路分析 #

你尝试用加倍映射+伯克霍夫遍历定理的方向完全正确，构造特征函数$f=\chi_{( \frac{w_1}{2}+....+ \frac{w_k}{2^k}, \frac{w_1}{2}+...+ \frac{w_k}{2^k}+ \frac{1}{2^k})}$的思路也没问题，只是在计数函数和遍历定理的结合上可能没捋清楚细节。

完整推导过程 #

• 首先明确：加倍映射$T(x)=2x \mod 1$在$(0,1)$上关于勒贝格测度是遍历的；题目中排除的有限二进制展开点集合测度为0，不影响“几乎每个”的结论。
• 对$x \in (0,1)$，其二进制展开为$x=\sum_{n=1}^\infty \frac{a_n(x)}{2^n}$（$a_n(x) \in {0,1}$）。字$w=w_1w_2...w_k$在第$i$位开始出现，等价于$a_i(x)=w_1, a_{i+1}(x)=w_2,...,a_{i+k-1}(x)=w_k$，也就是$T^{i-1}(x) \in I_w$（$I_w$就是你定义的那个区间，长度为$\frac{1}{2^k}$）。
• 定义$N_n(x)$为前$n$个位置中$w$的出现次数，则当$n \geq k$时，$N_n(x)=\sum_{i=1}^{n-k+1} \chi_{I_w}(T^{i-1}(x))$。
• 根据伯克霍夫遍历定理，勒贝格几乎处处的$x$满足：
  $$\lim_{n \to \infty} \frac{N_n(x)}{n} = \int_{(0,1)} \chi_{I_w}(x) dx$$
• 计算积分：$I_w$的长度是$\frac{1}{2^{k}$，所以积分结果为$\frac{1}{2}k}$。
• 补充：$\frac{N_n(x)}{n}$和$\frac{N_n(x)}{n-k+1}$的极限一致，因为$\frac{n-k+1}{n} \to 1$，不影响最终频率。

结论 #

对于题目中指定集合里的几乎每个$x$，二进制展开中$w$的出现频率是$\frac{1}{2^k}$。

内容的提问来源于stack exchange，提问作者user534042