随机序列中连续上升的子序列
序列\{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)$的值。 建议先从有限域考虑 即长度为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}
那么 问题就成了 我们需要估计下这个分布的最大值
下面就不知道怎么办了 方程好像不太对。
我希望的子序列是连在一起的。
换句话说，只要给定开始位置$i$和结束位置$j$，就可以确定这个子序列为$\{A_i,A_{i+1},...,A_j\}$。
页:
[1]