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

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\}$。