expected number of tests

Question

I'm struggling with the following problem:

An electronic circuit has $X$ components. The circuit works only if all its components work. Suppose $Y$ components are defective. A component is randomly selected and tested; if defective, then it is replace by a component that works, next the circuit is checked again. If the circuit still not working this process is repeated again All circuit components are equally likely to be selected even if it has been previously tested. shows that the expected number of tests until the circuit work (for large $X$ and $Y$) is : $X(\log(Y)+\gamma)$

$\gamma $:= Euler's constant

Any hints please.

Answer 1

We assume there are $k$ components of which $d$ are defective. The probability that on any trial we find and fix a defective is $\frac{d}{k}$. So the number of trials until we fix the first defective has geometric distribution, parameter $\frac{d}{k}$, so expectation $\frac{k}{d}$.

Once we have fixed the first defective, there are $d-1$ left, so the mean additional waiting time until we find and fix the next is $\frac{k}{d-1}$. Continue. The expected waiting time until we have found and fixed all the defectives is $$k\left(1+\frac{1}{2}+\cdots+\frac{1}{d}\right)$$ (we reversed the order of summation to make things look nicer).

So the expectation is $kH(d)$, where $H(d)$ is the $d$-th harmonic number. Please see Wikipedia for estimates of $H(n)$. The main term is $\ln n$. A better estimate is $\ln n+\gamma$, where $\gamma\approx 0.577$ is the Euler-Mascheroni constant (not $e$).

Remark: For a more standard related problem, please see the Coupon Collector's Problem.

Answer 2

Let's use $p,q$ instead of $X,Y$ (in probability we usually reserve capital letters for random variables, and I want to use $x,y$ for something else). Now we can use a common trick: define a function $f(x,y)$ where we want to compute $f(p,q)$. Then use the total expectation formula to derive a recurrence relationship for $f$.

In this case we have:

$$f(x,0)=1$$

because if there are no defective components, then you test once and then it works. That's the easy part. The harder part is:

$$f(x,y)=\frac{y}{x} \left ( f(x,y-1) + 1 \right ) + \left ( 1-\frac{y}{x} \right ) \left ( f(x,y) +1 \right ) \quad y \geq 1$$

because if there are currently $y$ defective components then you find and replace one of them with probability $\frac{y}{x}$. Otherwise you find a working component and nothing changes. The $+1$ is there to account for the fact that this iteration that we just did took a step, whether we found a defective component or not.

You can simplify and then solve this recurrence explicitly in terms of a sum; the question then reduces to understanding the asymptotics of this sum.

Answer 3

Consider how many tests are needed to replace one defect. The expected number is evidently $$\frac{Y}{X}+2\left(1-\frac{Y}{X}\right)\frac{Y}{X}+3\left(1-\frac{Y}{X}\right)^2\frac{Y}{X}+4\left(1-\frac{Y}{X}\right)^3\frac{Y}{X}+\dots \ \ (*)$$ because we make a successful replacement after $n$ failures for some $n=0,1,2,3,\dots$.

Using the standard result $1+2\lambda+3\lambda^2+\dots=\frac{1}{(1-\lambda)^2}$ we see that $(*)$ is just $$\frac{X}{Y}$$ Now having made one successful replacement the expected time to the next is $\frac{X}{Y-1}$. It takes longer because we test slightly more components that are not defective. Continuing, the expected number of tests to replace all defective components is $$\frac{X}{Y}+\frac{X}{Y-1}+\frac{X}{Y-2}+\dots+\frac{X}{2}+\frac{X}{1}=X\left(1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{Y}\right)$$

Now another standard result is that $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{Y}\approx\ln Y+\gamma$ where $\gamma$ is the Euler gamma constant $\approx0.57721$.

So we have finally that the expected number of tests is approx $X\ln Y+\gamma$ for large $Y$ (and hence large $X$).