Results 1 to 10 of 10
Like Tree2Thanks
  • 1 Post By chiro
  • 1 Post By awkward

Math Help - Expected number of comparisons in an algorithm

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Expected number of comparisons in an algorithm

    I have a question(and possible solution) for an algorithms course. I covered probability in two seperate discrete math courses so I'm hoping this is the proper forum for this post...

    Given the following algorithm, provide an exact calculation for the expected number of total comparisons made by the algorithm when the given array contains a random permutation of the numbers 0,1,...,n-1 (they are all distinct)

    input: a[0,....,n-1]
    output: (max, min) pair

    max_min(a)
    ........mx = a[0]
    ........ mn = a[0]
    ................for i = 1 to length(a) do
    ........................if a[i] > mx:
    ................................mx = a[i]
    ........................else if a[i] < mn:
    ................................mn = a[i]
    return(mx,mn)

    Define two indicator random variables
    x_i = 1 \text{ if } a[i] < mn \text{ and } 0 \text{ otherwise(we will have two comparisons every time } x_i = 1)
    y_j = 1 \text{ if } a[i] > mx \text{ and } 0 \text{ otherwise }

    Pr(x_i = 1) = \frac{1}{2} \text{ and } Pr(y_j = 1) = \frac{1}{2}
    Define two more random variables
    Y = \text{ number of 1 comparisons}
    X = \text{ number of 2 comparisons}

    E[TotalComparisons] = 2E[X] + E[Y]
    = 2\sum_{i = 1}^{n-1}E[x_i] + \sum_{j = 1}^{n-1}E[y_j]
    =2\sum_{i = 1}^{n-1}(Pr(x_i) = 1)  + \sum_{j = 1}^{n-1}(Pr(y_i) = 1)
    =2\sum_{i = 1}^{n-1}\frac{1}{2} + \sum_{j = 1}^{n-1}\frac{1}{2}
    =n -1 + \frac{1}{2}(n-1) = \frac{3n-2}{2}

    Not sure if this is right. I wanted to see if I am on the right track or in the general area of obtaining a solution. Any advice would be appreciated.
    Last edited by restin84; October 12th 2012 at 09:52 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,185
    Thanks
    772

    Re: Expected number of comparisons in an algorithm

    Hey restin84.

    I see what you have done for 2*E[X], but just as a point, you might want to consider that the distribution X should have an outcome of 2 when x_i = 1 and not 1 so that the 2 is on the inside of the expression and not on the outside.

    It might seem pedantic, but the random variable corresponding to 2 comparisons will have the distribution {2 when x_i = 1, and 0 when x_i = 0}. Algebraically, this example is the same but if you do a later problem where you make assumptions like the above, there is a tendency to screw up.

    The setup looks good.

    Just one question though: are you trying to find the expected number of "minimum" comparisons that need to be made rather than the actual number?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Expected number of comparisons in an algorithm

    Quote Originally Posted by chiro View Post

    Just one question though: are you trying to find the expected number of "minimum" comparisons that need to be made rather than the actual number?
    I am trying to find the total number of comparisons. I'm using the reasoning that when the first condition in the loop is met(a[i] > mx) there is only one comparison and when the second condition is met (a[i] < mn) there will be two comparisons because the first one has to take place in order to make the second.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,185
    Thanks
    772

    Re: Expected number of comparisons in an algorithm

    In your code you have a loop that does two comparisons regardless of what goes on. The loop as you have written it will always do two comparisons per iteration.

    Could you perhaps detail your loop so it shows the conditional nesting of the comparisons that correspond to your distribution?
    Thanks from restin84
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Expected number of comparisons in an algorithm

    Quote Originally Posted by chiro View Post
    In your code you have a loop that does two comparisons regardless of what goes on. The loop as you have written it will always do two comparisons per iteration.
    Shoot. It should have read "else if". I made the proper correction. Sorry, I checked over a couple times and I guess I failed to notice that. Do you think my answer is still appropriate?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,185
    Thanks
    772

    Re: Expected number of comparisons in an algorithm

    In this case, you have a dependent variable. If X is the random variable for the first comparison, then Y = 2*(1 - X).

    The other thing to take into account is the distribution of the numbers in your set: if you assume that they are uniform (or anything else for that matter), then this is going to change the way the whole thing is calculated (i.e. the probabilities won't be 1/2, but they'll vary depending on what values you got before).

    So if you want the number of comparisons given this model, then you have E[X+Y] = E[X] + E[2*(1-X)] = 2 - E[X] for a single trial. If you have n-1 of these you get E[Z] = E[(n-1)(X+Y)] = (n-1)*(2 - E[X]) = = 2*(n-1) - (n-1)*E[X].

    So for your model you have probabilities of 1/2 going either way (branch or don't branch on this condition), but if the numbers are uniformly distributed, then comparing say any number against 9 is a lot different to comparing it against 5 (both for less than or greater than).

    Do you want to take this into account?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Expected number of comparisons in an algorithm

    Well the question says that I am given a random permutation of the number 0,1,...,n-1. Does this mean that I have a uniform distribution?

    I'm not quite sure why Y = 2*(1-X) in your last post We are saying [total number of one comparisions] = 2*(1-[total number of two comparisons])? Why are we saying this?

    My original reasoning...
    one comparisions:
    what is the probability that a[i] > mx or what is the probability that y_i = 1. a[i] is either higher or lower than mx therefore the probability that y_i = 1 is 1/2(with similar reasoning for x_i) I guess this doesn't work but I don't quite understand why. I've always struggled with Probability
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,185
    Thanks
    772

    Re: Expected number of comparisons in an algorithm

    Basically the reason is because if you get a successful comparison in X you don't do one in Y and vice-versa.

    So if X is a successful comparison (i.e. X = 1) then there are no comparisons for Y (1 - X) but if there is not a successful comparison for X (X = 0) then Y gets a successful comparison.

    If X = 0, then you get two comparisons 0 + 2*(1 - X) = 2*(1 - 0) = 2 and if X = 1 you get one comparison which is 1 + 2*(1 - 1) = 1.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Expected number of comparisons in an algorithm

    Hi,

    Here is an observation that you may find helpful.

    The tricky point about this algorithm is the test "a[i] > mx". Let's fix i and ask the question, "What is the probability that a[i] > mx, given that a[] initially contains a random permutation of 0, 1, ..., n-1?"

    Inspection of the algorithm shows that a[i] > mx exactly when a[i] is the largest value seen so far, i.e. a[i] is the maximum of a[0], a[1], a[2], ... , a[i]. So what's the probability? Well, when i=1, the probability that a[1] is greater than a[0] is 1/2. When i=2, the probability that a[2] is the largest of a[0], a[1], and a[2] is 1/3, because each of a[0], a[1], and a[2] is equally likely to be the largest. And in general, the probability that a[i] is the maximum of a[0], a[1], a[2], ..., a[i] is 1/(i+1).

    So the probability that a[i] > mx is 1/(i+1).
    Thanks from restin84
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Expected number of comparisons in an algorithm

    Quote Originally Posted by awkward View Post
    Hi,

    Here is an observation that you may find helpful.

    The tricky point about this algorithm is the test "a[i] > mx". Let's fix i and ask the question, "What is the probability that a[i] > mx, given that a[] initially contains a random permutation of 0, 1, ..., n-1?"

    Inspection of the algorithm shows that a[i] > mx exactly when a[i] is the largest value seen so far, i.e. a[i] is the maximum of a[0], a[1], a[2], ... , a[i]. So what's the probability? Well, when i=1, the probability that a[1] is greater than a[0] is 1/2. When i=2, the probability that a[2] is the largest of a[0], a[1], and a[2] is 1/3, because each of a[0], a[1], and a[2] is equally likely to be the largest. And in general, the probability that a[i] is the maximum of a[0], a[1], a[2], ..., a[i] is 1/(i+1).

    So the probability that a[i] > mx is 1/(i+1).
    So would this relate back to what chiro was getting at? If the probability that a[i] > mx is 1/(i+1) then the probability that a[i] < mn is 1-(1\(i+1))
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. find the expected number
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 25th 2011, 09:16 PM
  2. expected number of coupons
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 18th 2011, 03:11 AM
  3. Expected number of collisions
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: December 1st 2009, 08:42 AM
  4. Expected number of matches
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: August 19th 2008, 06:00 PM
  5. Number distribution algorithm
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 19th 2008, 05:56 PM

Search Tags


/mathhelpforum @mathhelpforum