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

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


简体版||繁體版
3
vote

问题

中文

我需要知道以下算法的复杂性:

从一组尺寸$ m $绘制元素,随机,随机替换,直到从集合中跨越$ n $不同的元素($ n le m $)。我们不在乎绘制的数字是什么,并且在此过程中看到了一旦每次$ n $不同的数字。

这是优惠券收集器的问题,其中一个人继续挑选看到集合的所有$ M $元素。

示例:

我们从设置$ {1,2,3,4,5 } $,$ n = 3 $,$ m = 5 $中绘制数字。输出 $ {1,5,2 } $由以下系列绘图制作:

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

从池$ {1,2,3,4,5 } $。在这种情况下,我们在6美元的运营之后停止。

该算法的预期时间复杂程度是多少?

英文原文

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
 
vote
vote
最佳答案
 

当$ M $大于$ N $时,预期的试验数量基本上是线性的$ n $。我们可以更精确地使这种更精确,如下所示。

让$ t_n $是随机变量计算,这会对看到$ n $不同的元素的试用次数,其中元素从一组大小为$ m $随机均匀挑选。

您可以将$ t_n $写为几何随机变量的总和

$$ 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]& = sum limits_ {i = 0} ^ {n-1} mathbb {e} left [g left(1- frac {i} { m} 右)右] \ & = sum limits_ {i = 0} ^ {n-1} frac {m} {m-i} \ & = m left( frac {1} {m} + frac {1} {m-1} + ... + frac {1} {m-n + 1} over)\ & = m left(h_m-h_ {m-n} 右) 结束{align *} $$

其中$ h_k $是 harmonic sum ,它满足$ frac {1} {2(k + 1)} le h_k- ln k - gamma le frac {1} {2k} $,其中$ gamma $是eulerâ€" mascheroni常数(见 wolfram的谐波编号的页面)。使用我们具有的谐波数字的这些界限:

$$ begin {align *} mathbb {e} left [t_n light]& le m left( frac {1} {2m} + ln m + gamma - left( frac {1} {2(m-n +1)} + ln(mn)+ gamma 右)右)\ & le m left( frac {1} {2m} + ln frac {m} {mn} {mn} ext)= frac {1} {2} + m ln frac {m} {mn }。 结束{align *} $$

注意,$ m ln frac {m} {mn} = m ln left(1+ frac {n} {mn} other)大约n $当$ n ll m $时,所以对于M $大于$ N $,预期​​的试验次数是线性的$ N $。

 

When $m$ is much larger than $n$, the expected number of trials is basically linear in $n$. We can make this more precise, as shown below.

Let $T_n$ be the random variable which counts the number of trials up to seeing $n$ different elements, where the elements are picked uniformly at random from a set of size $m$.

You can write $T_n$ as the sum of geometric random variables

$$T_n=1+G\left(1-\frac{1}{m}\right)+G\left(1-\frac{2}{m}\right)+...+G\left(1-\frac{n-1}{m}\right)$$

where $G(p)$ is a geometric random variable with parameter $p$ (number of trails up to the first success, where success happens with probability $p$ (I leave it to you to prove the equivalence).

Using linearity of expectation:

$$\begin{align*} \mathbb{E}\left[T_n\right]&=\sum\limits_{i=0}^{n-1}\mathbb{E}\left[G\left(1-\frac{i}{m}\right)\right]\\ &=\sum\limits_{i=0}^{n-1}\frac{m}{m-i}\\ &=m\left(\frac{1}{m}+\frac{1}{m-1}+...+\frac{1}{m-n+1}\right)\\ &=m\left(H_m-H_{m-n}\right) \end{align*}$$

where $H_k$ is the harmonic sum, which satisfies $\frac{1}{2(k+1)}\le H_k-\ln k - \gamma\le \frac{1}{2k}$, where $\gamma$ is the Eulerxe2x80x93Mascheroni constant (see Wolfram's page on harmonic numbers). Using these bounds for harmonic numbers we have:

$$\begin{align*} \mathbb{E}\left[T_n\right]&\le m\left(\frac{1}{2m}+\ln m +\gamma -\left(\frac{1}{2(m-n+1)}+\ln(m-n)+\gamma\right)\right)\\ &\le m\left(\frac{1}{2m}+\ln\frac{m}{m-n}\right)=\frac{1}{2}+m\ln\frac{m}{m-n}. \end{align*}$$

Note that $m\ln\frac{m}{m-n}=m\ln\left(1+\frac{n}{m-n}\right)\approx n$ when $n\ll m$, so for $m$ much larger than $n$, the expected number of trials is linear in $n$.

 
 

相关问题

0  启发式确定值f,使得概率d / f接近1/2  ( Heuristically determine a value f such that a probability d f approaches 1 2 ) 
我们有一个m个元素的x。我们希望获得具有m致大小的新组x' ñ。 Choose a first element x from X and put it in X' for each element x in (X - X') Let x' the element from X' which is the cl...

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically ) 
所以我最近重新发现了模拟退火,但其他人似乎很清楚的道路。我知道Metropolis-Hastings作为一种采样算法,它创造了一个Markov-Chain,该链条是通过归一化一些功能而产生的分布。意识到您可以使用它来优化许多事物,并且您甚至可以继续拒绝,这是一个很小的飞跃,甚至可以抵制到目前为止你发现的最少值。但是更...

24  如何接近垂直棍子挑战  ( How to approach vertical sticks challenge ) 
此问题是从 prokentstreet.com 我们给出了一个整数的数组$ y = {y_1,...,y_n } $代表$ n $行段,以便分段$ i $的端点为$(i,0)$和$ (我,y_i)$。想象一下,从每个段的顶部射到左侧,当它触及另一个段时,这射线会停止,或者它击中y轴。我们构造了一系列N个整数,$...

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability ) 
我有一个英语字典(文本文件)和2克,3克和4克的频率作为每个单词的开头。我需要编写一种算法,使用给定的单词,基于转换概率计算可能的字谜(必须进入字典)(我的赋值要求我使用此方法)。 我想使用维特比算法,但我不知道它是否是正确的选择。您如何看待模拟退火算法?你能给我任何帮助吗或建议? ...

3  MaxSAT条款可靠性的差异  ( Variance of maxsat clause satisfiability ) 
对于给定的MaxSAT问题,它是琐碎的易于计算所有分配满足的子句的平均数量,或者等效地对随机分配满足的预期子句数。 同样可以计算满足的子句数量的方差?我的意思是一个精确的计算,而不是估计。 一般,哪些时刻易于计算,哪个很难? 我更喜欢普通Maxsat的答案,但也对Max-3-Sat的特殊情况也有兴趣。 ...

6  当我们只有上限的期望时,Chernoff绑定  ( Chernoff bound when we only have upper bound of expectation ) 
如果$ x $是i.i.d的总和。随机变量在$ {0,1 } $和$ e [x] = mu $中占据价值,CHERNOFF绑定告诉我们 $$$$(x geq(1+ delta) mu) leq e ^ { - frac { delta ^ 2 mu} {3}} $$ 所有$ 0< delta...

1  有多少前缀代码我们可以找到给定的概率分发?  ( How many prefix code we can find for a given distribution of probability ) 
源发射5个信号S1,S2,S3,S4和S5,其概率如下:1 / 3,1 / 3,1 / 9,1 / 9,1 / 9,1 / 9。我们可以在= {a,b,c}上构建多少前缀代码?有多少种性能(效率)? ...

1  贝叶斯网络背景下的线性放松是什么? [关闭]  ( What is linear relaxation in the context of bayesian networks ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并阐明编辑此帖的问题。 关闭 6年前。 ...

3  设施位置问题  ( A facility location problem ) 
考虑以下情景。一个城镇中有n个地方的地方,其中占地平为$ l_i $的数量由$ p_i $,$ i in {1, ldots,n} $。我们需要以达到医院的成本最小化的方式在城镇周围放置K医院。 我们基本上努力 $$ min_o( sum_ {i = 1} ^ n p_i time c(d(l_i,o(l_i...

3  设定平等的确定性和随机通信复杂性  ( Deterministic and randomized communication complexity of set equality ) 
两个处理器$ a,b $ with输入$ a in {0,1 } ^ n $(以$ a $)和$ b in {0,1 } ^ n $ (以美元)想要决定是否$ a = b $。 $ a $不知道$ b $ ups的输入,反之亦然。 a可以发送消息$ m(a) in {0,1 } ^ n $ the $ b...

1  挑战:关闭哈希,线性探测,探头长度1  ( Challenge closing hash linear probing probe length 1 ) 
挑战说,有一个带有错误的哈希算法,如果它到达数组的末尾,则给出了错误,并且没有找到保存元素的空间, 它直接丢弃它(即,它不会尝试将其放在0,1,2 ...上的位置,因为它是正确的) 在散列表中使用闭合散列,线性探测,探头1。 在此测试的可能性是什么,我们发现实现n有一个错误,如果n = 27并且k = 42? 示...

3  返回具有N字符串长度k的随机子集,而仅在最多k上存储  ( Returning a random subset with length k of n strings while only storing at most ) 
这是问题。我写了一个读取stdin字符串的程序,并返回那些字符串的随机子集。提供给程序的唯一其他参数是子集的长度,$ k $。子集必须恰好包含从整个输入集随机均匀选择的$ k $ strings。 如果每个字符串存储在内存中,则很容易执行此操作。 (记忆成比例为n)。问题是如何仅在大多数$ k $字符串存储,并确保输...

20  追逐移动目标的算法  ( Algorithm to chase a moving target ) 
假设我们有一个Black-Box $ F $,我们可以查询和重置。当我们重置$ F $时,将状态$ f_s $ f $设置为随机从SET $$ {0,1,...,n - 1 } $$何处的统一选择的元素$修复,已知为ket $ f $。要查询$ F $$,从$$ {0,1,...,n - 1 } $$提供...

7  证明指纹  ( Prove fingerprinting ) 
让$ a neq b $是两个整数从间隔$ [1,2 ^ n]。$让$ p $是一个随机的素数,用1 le p le n ^ c。$证明这一点 $$ text {pr} _ {p in mathsf {primes}} {a Equiv b pmod {p} } le c ln(n)/(n ^ ...

-3  M元素随机样本同样可能...(CLRS 5.3-7)? [关闭]  ( M element random sample being equally likely clrs 5 3 7 ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并通过编辑此帖的问题。 关闭 6年前。 ...

2  动态卡游戏算法的复杂性  ( Complexity of dynamic card game algorithm ) 
将以下动态卡游戏与26个红牌的常规甲板和26个黑卡。经销商一个逐一地绘制了未经测试的卡,我们可以让他随时停下来。对于每个绘制的每张红牌,我们获得1美元,为每张黑卡丢失1美元。问题在于找到返回游戏预期值的算法。如果我们分别表示超过$ B $和$ r $分别在甲板上留下的黑色和红卡的数量,游戏的预期价值$ e(b,r)$...

2  最佳赌博,以最大限度地减少预期的时间达到目​​标收益  ( Optimal wagering to minimize expected time to reach a target payoff ) 
为简单起见,我们以启动量$ s = 1 $开始,我们希望达到目标金额$ t $。为此,我们顺序地下注一定的数量,然后赢得概率$ P $的那些金额,并失去概率1-P $(已知$ P $的数量。我们希望在最低预期的比赛中达到目标金额$ T $。在每个阶段,我们都可以下注不同的数量。为了使期望更简单地计算我们可以假设如果当...

1  是均匀位字符串的位xor和non_uniform位串均匀?  ( Is the bitwise xor of a uniform bit string and a non uniform bit string uniform ) 
具有两个位字符串 $ x,y y y y {0,1 rick } ^ n $ ,其中 $ x $ 但 $ y $ 不是。 是 $ z = x oplus y $ 统一? ...

33  菱形糟糕是多么的洗牌?  ( How asymptotically bad is naive shuffling ) 
众所周知,这种"天真" 通过将每个项目与另一个随机选择的一个单独交换的阵列进行洗牌,不正常运行: for (i=0..n-1) swap(A[i], A[random(n)]); 具体而言,由于在$ N $迭代中的每一个中,获得$ N $的选择之一(具有统一概率),通过计算有$ N ^ n $可能的"路...

3  使随机源均匀分布  ( Making random sources uniformly distributed ) 
如何构建输出位0和1的随机源,以$ prob(0)= prob(1)= 0.5 $。我们可以访问其他随机源$ s $,以$ a $或$ b $与独立概率$ prob(a)$和$ prob(b)= 1 - prob(a)$ overs。 如何调整作业的算法,并且不会消耗超过预期的数量 $(prob(a) cdot ...

3  贝叶斯网络的目的是什么?  ( What is the purpose of bayesian networks ) 
我已经看过很多关于贝叶斯网络的解释,但我根本无法在代码中围绕他们的使用。所以这是我的三部分问题。 我是我对贝叶斯网的定义吗?贝叶斯网络是一种(视觉上)描绘变量/事件链接的方式以及它们如何相互影响。可以将概率添加到每个节点中以使您更大的意义会发生什么。与AICASE AI相结合,贝叶斯网用于预测AI的行动并告知它应...

4  在线生成统一样本  ( Online generation of uniform samples ) 
源提供商品流$ x_1,x_2, dots $。在每步到$ n $我们想要保存一个随机样本$ s_n subseteq {(x_i,i)| 1 le i le n }尺寸$ k $,即$ s_n $应该是统一选择的来自所有$ tbinom {n} {k} $可能的样本。所以在每一步$ n ge k $我们...

2  在M / M / 1队列中,服务时间的指数分布是什么意思?  ( In an m m 1 queue what does exponential distribution of service time mean ) 
我正在阅读关于 99887665544330 我们假设新客户根据泊松分发到达,每个客户都需要一段时间到从指数分布中汲取的服务? 我了解基于泊松分布的到达率的意味着什么 - 如果平均每小时10次,你将有9次,6个非常不经常,11个常见等 - 但是是什么这是否意味着服务是指数级的? 这是否意味着,当您为更多客户服务时...

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia ) 
当两个RV的事件被设置时,我正在尝试实施条件概率分布。如果我尝试从真实或分类变量推断概念,以便为我设置令人困惑。在通常的场景中,对于某些分立的RVS, $ X,Y $ ,我们可以使用贝叶斯定理来计算两个"准时" 事件的条件概率: $$ p(y = y | x = x)= frac {p(x = x | y = y...

1  统一采样与约束  ( Uniform sampling with constraints ) 
假设一个人想要在有限的字母表上统一地样本一个给定长度的字符串,这是$ w $满足一组结构约束(例如 - "第三个字符必须等于第一个字符和最后一个字符必须等于第二个")。 显而易见的方法是统一样本$ W $,检查约束是否保持并返回它。但是,我正在处理有许多限制的情况,随机字符串满足它们的概率非常低。有没有办法从满足一组...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有