优惠券收集者问题变异的复杂性是什么？ -- time-complexity 领域 和 probability-theory 领域 cs 相关 的问题

What is the complexity of a variation of the Coupon collector's problem?

3

问题

$1,1,5,1,5,2$

I need to know the complexity of the following algorithm:

Draw elements from a set of size $m$, one by one, randomly, with replacement, until coming across $n$ different elements from the set ($n\le m$). We do not care what are the numbers drawn, and halt once $n$ different numbers were seen during this process.

This is a variation of the Coupon collector's problem, where one continues picking until seeing all $m$ elements of the set.

Example:

We draw numbers from the set $\{1,2,3,4,5\}$, $n=3$, $m=5$. The output $\{1,5,2\}$ is produced by the following series of draws:

$1,1,5,1,5,2$

from the pool $\{1,2,3,4,5\}$. In this case, we halt after $6$ operations.

What is the expected time complexity of this algorithm?

回答列表

6

$$t_n = 1 + g left（1- frac {1} {m}右）+ g left（1- frac {2} {m} 右）+ ... + g 左（1- frac {n-1} {m}右）$$

$g（p）$是一个几何随机变量，参数$p$（达到第一个成功的路径数，在概率$p$（我将它留给您来证明等价）。

begin {align *} mathbb {e} left [t_n light]＆amp; = sum limits_ {i = 0} ^ {n-1} mathbb {e} left [g left（1- frac {i} { m} 右）右] \ ＆amp; = sum limits_ {i = 0} ^ {n-1} frac {m} {m-i} \ ＆amp; = m left（ frac {1} {m} + frac {1} {m-1} + ... + frac {1} {m-n + 1} over）\ ＆amp; = m left（h_m-h_ {m-n} 右） 结束{align *}

begin {align *} mathbb {e} left [t_n light]＆amp; le m left（ frac {1} {2m} + ln m + gamma - left（ frac {1} {2（m-n +1）} + ln（mn）+ gamma 右）右）\ ＆amp; le m left（ frac {1} {2m} + ln frac {m} {mn} {mn} ext）= frac {1} {2} + m ln frac {m} {mn }。 结束{align *}

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability )

3  MaxSAT条款可靠性的差异  ( Variance of maxsat clause satisfiability )

6  当我们只有上限的期望时，Chernoff绑定  ( Chernoff bound when we only have upper bound of expectation )

3  设定平等的确定性和随机通信复杂性  ( Deterministic and randomized communication complexity of set equality )

-3  M元素随机样本同样可能...（CLRS 5.3-7）？ [关闭]  ( M element random sample being equally likely clrs 5 3 7 )

2  动态卡游戏算法的复杂性  ( Complexity of dynamic card game algorithm )

2  最佳赌博，以最大限度地减少预期的时间达到目​​标收益  ( Optimal wagering to minimize expected time to reach a target payoff )

3  贝叶斯网络的目的是什么？  ( What is the purpose of bayesian networks )

4  在线生成统一样本  ( Online generation of uniform samples )