Expectation of random variable

#1
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
#2
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.