任意正整数均可无限重现的最佳数列

KeyTo9_Fans

第1次选1，第2次以1/2的等概率选1和2，第3次以1/3的等概率选1到3，第4次以1/4的等概率选1到4，依次类推到第n→∞次，以1/n的等概率选1到n，那么可证每个数都会被无限多次选中。说明这个数列a(n)=a(n-1)+1增长得太慢了。改成素数数列：第1次在2以内随机选，第2次在3以内随机选，第3次在5以内随机选，第4次在7以内随机选，第5次在11以内随机选，依次类推到第n→∞次在第n个素数以内随机选，那么依然可证每个数都会被无限多次选中。说明这个素数数列a(n)=p(n)增长得还是太慢了。增长得再快一点：a(n)=a(n-1)+a(ln(n)取下整)，那么依然可证每个数都会被无限多次选中。再快一点就不行了，就存在一些数一次都不会被选中的情况了。如果我要保证第k次从1到a(k)等概率选数(k=1,2,...n，n→∞)时，每个数都会被无限多次选中，那么a(n)的增速最快可以去到多快呢？

无心人

举个栗子呗，最好上举着栗子的图

.·.·.

首先BC引理把这个问题转化成数列发散问题
然后证明不存在最慢的发散数列
然后我们就证完了。

（以下结论未验证）
感觉a(n)=a(n-1)+a(ln(n)lnln(n))也是可以的，多写几个ln似乎也没问题

.·.·.

BC引理，对事件${X_i},i=1,2,...$
$\{X_i i . o .\}$==>$\sum_{i=1}^\infty P(X_i)=\infty$
于是我们只需要考虑数字1是否会无穷次选中
此时$P(X_i)=\frac1{a(n)}$
然后我的意思是比如a(n)=n Log[n] Log[Log[n]] Log[Log[Log[n]]]（取整）
之后有$\sum_{i=1}^\infty a(i)=\infty$（我数分不太好，但这好歹是Mathematica验证过的...）

随手查了一下
https://www.zhihu.com/question/67774899
从这里可以看到，不存在“最大的”a(n)使得$\sum_{i=1}^\infty a(i)=\infty$
只要你给定一组a(n)，一定能找到一组b(n)使得an/bn->0而$\sum_{i=1}^\infty b(i)=\infty$

BC引理全称为Borel-Cantelli引理
i.o.是无穷次出现的缩写

KeyTo9_Fans

$a(n)=a(n-1)+a(ln(n)lnln(n))$不行，增长太快了。

事实上$a(n)=a(n-1)+a(\lfloor \log_b(n)\rfloor)$里面的$b$只要小于自然指数$e$，倒数和就收敛了。

具体的讨论在这里：https://bbs.emath.ac.cn/thread-9628-1-1.html

#####

目前我能找到的增长得最快且倒数和发散的数列是$a(n)=a(n-1)+a(\ceil{ln(n)})$。

在倒数和发散的前提下，这个数列还能增长得更快吗？如果可以，该怎么改进？