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
$\displaystyle x_i = 1 \text{ if } a[i] < mn \text{ and } 0 \text{ otherwise(we will have two comparisons every time } x_i = 1)$
$\displaystyle y_j = 1 \text{ if } a[i] > mx \text{ and } 0 \text{ otherwise }$

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

$\displaystyle E[TotalComparisons] = 2E[X] + E[Y]$
$\displaystyle = 2\sum_{i = 1}^{n-1}E[x_i] + \sum_{j = 1}^{n-1}E[y_j]$
$\displaystyle =2\sum_{i = 1}^{n-1}(Pr(x_i) = 1) + \sum_{j = 1}^{n-1}(Pr(y_i) = 1)$
$\displaystyle =2\sum_{i = 1}^{n-1}\frac{1}{2} + \sum_{j = 1}^{n-1}\frac{1}{2}$
$\displaystyle =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.

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?

Quote:

---

Originally Posted by chiro

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.

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?

Quote:

---

Originally Posted by chiro

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?

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?

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

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.

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).

Quote:

---

Originally Posted by awkward

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))