Misc: [0, 1]均匀取点，单调序列的期望长度

[shenxiangzhuang]

在[0,1]上均匀随机的一直取点，如果你当前的序列是一个单调递增序列就继续，请问这个单调序列的期望长度是多少？

• 出处: https://www.acethedatascienceinterview.com/

• 解析解

  • Solution1: [0, 1]均匀取点，单调序列的期望长度 #70
  • Solution2: [0, 1]均匀取点，单调序列的期望长度 #71

• 数值解

[Alex222222222222]

因为这个问题有些许地方描述的不是很清楚，譬如你这个如果是单调递增序列就继续，那么有可能出现无穷情况，这种情况怎么处理。再者，长度在数学上是一个很模糊的词语，我不清楚这里指的是序列的长度1，2，3 还是这个单调序列的最大值，就是这个序列在$[0,1]$上的长度。所以根据我的个人理解，可以formalize成如下问题。

Remark: $\mathbb{N} = \{ 1,2,\dots \}$

Consider the space $X = [0,1]^\mathbb{N}$, where a probability measure $p$ is defined by selecting a sequence of points uniformly from the interval $[0,1]$. And given function $f: X \rightarrow [0,1]$ as:

$$ f(\gamma) = \sup \{ \gamma_n \mid \gamma_i < \gamma_{i+1}, \forall i < n, n \in \mathbb{N} \} $$

Calculate $E[f(X)]$.

[shenxiangzhuang]

@Alex222222222222 感谢反馈！抱歉这里题目描述的确实不是很清晰。我先来明确一些已知的细节，希望能解答你的问题：首先这里的长度指的是这个单调序列的长度，而不是其最大值。另外，无穷的情况是会出现的，在求解的时候需要考虑这种情况。

这个问题最早是由 @yuanhang0 分享的，后续会联系下学长补充下题目细节～

[shenxiangzhuang]

@Alex222222222222 本题目前打算放在misc目录下，如果有兴趣的话欢迎PR提供解答。解答的模版可以参考这里, 有任何问题欢迎随时联系，我会尽可能帮助解决。

另外README已经增加微信群的信息，欢迎加入一起讨论！

[Alex222222222222]

@Alex222222222222 感谢反馈！抱歉这里题目描述的确实不是很清晰。我先来明确一些已知的细节，希望能解答你的问题：首先这里的长度指的是这个单调序列的长度，而不是其最大值。另外，无穷的情况是会出现的，在求解的时候需要考虑这种情况。

这个问题最早是由 @yuanhang0 分享的，后续会联系下学长补充下题目细节～

如果指序列长度的话，那么函数 $f$ 改为如下形式就可以了。

$$ f(\gamma) = \sup \{ n \in \mathbb{N} \mid \gamma_i < \gamma_{i+1}, \forall i < n \} $$