According to the procedure HIRE-ASSISTANCE, n candidates are interviewed and assigned a ranks from 1 to n. The procedure hires a candidate i who is better than the candidate j interviewed before candidate i. (that is , the rank of candidate i is better than the rank of candidate j ).

Thus, the following conditions must be satisfied, in order to hire exactly twice in HIRE-ASSISTANCE.

• A candidate 1 must acquire the rank. That is, no candidate up to candidate i is better than candidate 1 and thus candidate 1 is hired. and

• The candidate i+1 must acquire the rank n. That is, no candidate interviewed after candidate i+1 should not be better than candidate i+1.

Finding probability to hire twice:

• Suppose denotes the event where candidate 1 obtained a rank i. Hence, the probability of event where candidate 1 got rank i or got hired will be as follows:

(Probability for hiring one candidate out of n candidates), for any

value of i.

• Suppose, the event where candidates 2, 3,…,i consists a rank lower than the rank obtained by the candidate 1, be G.

• After the event has occurred, the event G will also occur if the best candidate is interviewed first among the remaining candidates, whose ranks are

Thus,

• Suppose A denotes an event where HIRE-ASSISTANT hires exactly twice. The events are known as disjoint, then

Now, simplify the above using distributive property,

• Now,

……(1)

Now, apply the following conditional probability formula to solve the

above equation(1):

• Now, replace the value of in the equation (1), then

Where, denotes the nth harmonic number.

Therefore the probability in order to hire exactly twice by HIRE-ASSISTANT is .

Indirect random variable

Suppose that the sample space is S = {1, 2,..., n}

Let X be a random variable that equals the number of customers that get back their own hat and let X_i be the indicator random variable associated with the event in which the i^th customer gets back his own hat.

Thus,

and

As the hat-check person gives the hats back to the customers in a random order, each customer has a probability of 1/n of getting back his own hat. Thus

By using lemma “Given a sample space S and an event A in the sample space S, Let. Then.”

Since , calculate as follows.

This means that on an average, one customer can get back his own hat.

Suppose an array of distinct numbers is denoted as. Now, according to the definition of inversion, a pairis known as an inversion of, if and.

Suppose that be an indicator random variable for the event inversion. That is for .

Consider the probability of getting first number is bigger than the second number in the set of given two numbers. In this case, the probability is given as,

Now, by Lemma 5.1

Here,, because or

Computing expected number of inversions of an array of n distinct numbers:

• Suppose that the random variable denotes the total number of inverted pairs in the array.

Thus ,

……(1)

• Since we require expected number of inversion, apply the expectation of the both side of equation (1).

Now, apply the linearity of expectation

……(2)

• Now, replace the value of in equation (2),

• Thus,

Hence, from the above, the expected number of inverted pair in an array of n distinct numbers is .