+ Reply to Thread
Results 1 to 2 of 2

Thread: Expectation of random variable

  1. #1
    Points: 4, Level: 1
    Level completed: 7%, Points required for next Level: 46

    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Expectation of random variable




    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

  2. #2
    TS Contributor
    Points: 22,410, Level: 93
    Level completed: 6%, Points required for next Level: 940

    Posts
    3,020
    Thanks
    12
    Thanked 565 Times in 537 Posts

    Re: Expectation of random variable


    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.

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats