# Expectation of random variable

#### mystery

##### New Member
Hey guys,

I have stumbled upon this problem, and I've tried solving it by looking at it as a Binomial distribution, but i just don't see the right connection.

Is my initial impression wrong or not ? I would appreciate any pointers on the given tasks. Thanks

Code:
There are 2*N computers. On them a program A or B is installed.
We check the computers till we have N computers with version A or version B(this number of checks is denoted with K). But from those K
computers we don't remember which of them have version A or B appropriately. So we check again.

Let X be the random variable which will denote the number of computers I have to check in order to find N suitable ones(of version A or version B).

Find the expected value of X, E(X) = ?

Example:

n = 3 k = 4

In this case we have eiher 3 computers with A & 1 computer with B, or
1 computer with A & 3 computers with B.

First we have to check the first two computers, and checking this will give us:

- 2(A) + 0(B) 25%
- 2(B) + 0(A) 25%
- 1(A) + 1(B) 50% In this case we have to check the third computer also, so we are certain of the version.

2     3
X:  (               )
0.5   0.5

EX = 2*0.5 + 3*0.5 = 1+1.5 = 2.5

#### BGM

##### TS Contributor
This question looks interesting.

Note that from the specification we have $$n \leq k \leq 2n-1$$, since we have $$n$$ and $$k - n$$ of computers of the two different versions, and once we sampled there are $$n$$ computers of 1 version, we will stop. So we must have $$k - n < n$$ (pigeonhole principle) and hence the bound.

In order to make sure which version of computer is more, you will need to check that there are more than $$k - n$$ computer of that version. So we have $$X \geq k - n + 1$$ and similarly, by pigeonhole principle, $$X \leq 2(k - n) + 1$$. i.e. The support of $$X$$ is

$$\{k - n + 1, k - n + 2, \ldots, 2(k - n) + 1\}$$

If you are able to determine the version on the $$x$$-th check, it means that you have checked $$k - n$$ computers of a certain version in the previous $$x - 1$$ checks, and have that version again on the $$x$$-th check. So the probability mass function of $$X$$ is given by

$$\Pr\{X = x\} = \frac {\displaystyle \binom {n} {k - n} \binom {k - n} {x - 1 - k + n}} {\displaystyle \binom {k} {x - 1}} \times \frac {2n - k} {k - x + 1}$$

where $$x \in \{k - n + 1, k - n + 2, \ldots, 2(k - n) + 1\}$$ as stated earlier.