Results 1 to 7 of 7

Math Help - Expected Value

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    Texas
    Posts
    5

    Expected Value

    Can someone help me with this? I'm having a hell of a time with expected value...

    Suppose that the probability that a number X is in the first half of a list of N distinct integers is 1/2. And the probability that it is in the second half of the list is 1/4. Find the average number of comparisons used by the linear search algorithm to find X.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Dec 2011
    Posts
    92
    Thanks
    7

    Re: Expected Value

    Is this a problem you came up with yourself? The probabilities should add up to one, and the wording is very ambiguous.

    Assuming a uniform distribution in the two halves, the expected value is \sum_{n=1}^{N/2}\frac{1}{N} +\sum_{n=N/2+1}^{N}\frac{1}{2N}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2012
    From
    Texas
    Posts
    5

    Re: Expected Value

    No it is a problem from my professor. Could you expand please? Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2011
    Posts
    92
    Thanks
    7

    Re: Expected Value

    I read it wrong. The probabilities for all events should add up to one, and I forgot that you also have the event where a number is not in the list (with the probability 1/4).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2012
    From
    Texas
    Posts
    5

    Re: Expected Value

    Could you show me how to solve it?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2011
    Posts
    92
    Thanks
    7

    Re: Expected Value

    It's pretty much a textbook example of the expected value for a discrete stochastic variable.

    Let X be the number of comparisons before you find the number you're looking for in a list of N distinct integers.

    P(X=k)=1/N if 1 \leq k \leq N/2
    P(X=k)=1/2N if N/2 < k \leq N
    P(X=k)=0 else

    The probabilities come from the assumption that the probability mass is distributed in a uniform manner (simply divide the provided probabilities with the number of integers in each half).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2012
    From
    lebanon
    Posts
    18

    Re: Expected Value

    You have three cases:
    case 1: found in first half case2:found in second half case3:not found
    In each case you should get best case and worst case scenario in order to reach the average case.
    case1: best case (found at position 1 --> 1 comparison) worst case (found at position N/2 -->N/2 comparisons)
    Average case (1+N/2)/2= (2+N)/4
    case2: best case (found at position N/2+1 --> N/2+1 comparisons) worst case (found at position N --> N comparisons)
    Average case (N/2+1+N)/2= (3N+2)/2
    case 3 (Not found --> N comparisons)
    Finally the average number of comparisons is : 1/2 *((N+2)/4) + 1/4 * ((3N+2)/2) + 1/4 * N
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Expected Value
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 25th 2011, 04:51 PM
  2. Expected value
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 10th 2010, 07:38 PM
  3. Expected Value
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 23rd 2010, 11:45 PM
  4. MLE of expected value of pdf e^-(x-a)
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: September 27th 2009, 03:21 AM
  5. expected value
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 16th 2009, 09:51 AM

Search Tags


/mathhelpforum @mathhelpforum