随机序列中连续上升的子序列

KeyTo9_Fans

序列$\{A_n\}$是一个长度为$L$的序列。 它的每一项都是独立的、在$0$到$1$之间均匀分布的随机实数。 我们希望该序列中出现长度为$n$的连续上升的子序列的概率达到$50%$。 求该序列的长度$L$至少是多少。 例$1$： ??当$n=1$时，取$L=1$， ??出现长度为$1$的连续上升的子序列的概率为$100%$， ??所以$L(1)=1$。 例$2$： ??当$n=2$时，取$L=2$， ??出现长度为$2$的连续上升的子序列的概率为$50%$， ??所以$L(2)=2$。 当$n>2$就比较难了，不知道有什么好方法求$L(n)$的值。

jsliyuan

建议先从有限域考虑 即长度为n的随机序列 每个元素属于{0, 1, ..., p-1}, p是一个质数 最后对p->oo 给定这样的一个a1, a2, ..., an 如何求最长上升子序列呢？ 可以采用动态规划 记L(x) 为 到目前为止 最后一个元素是x的最长子序列的长度 每次加入一个元素 ai = y 我们需要更新 L(y) = max{L(y), max{L(j) | j < y}+1} 那么 问题就成了 我们需要估计下这个分布的最大值 下面就不知道怎么办了

KeyTo9_Fans

方程好像不太对。 我希望的子序列是连在一起的。 换句话说，只要给定开始位置$i$和结束位置$j$，就可以确定这个子序列为$\{A_i,A_{i+1},...,A_j\}$。