Suppose you have an array of n numbers 1,2,...,n. They can be in any order in th

Question

Suppose you have an array of n numbers 1,2,...,n. They can be in any order in the array and each order is equally likely. Suppose you get a random ordering of the numbers in the array.

(a) What is the probability that the numbers are ordered (ascending or descending)?

(b) What is the probability that all the numbers in the first half of the array are smaller than all the numbers in the second half of the array? (Assume n is even)

(c) Given that all the numbers in the first half of the array are smaller than all the numbers in the second half of the array (n is still even), what is the probability that the first number in the array is the smallest?

(d) Let E be the event that the first number in the array is the smallest and let F be the event that the last number in the array is the largest. Are E and F independent?

(e) Suppose a program contains a loop that iterates from the first number in the array until it finds a number less than it (inclusively). What is the maximum number of iterations this loop can have? What is the probability of this happening, assuming all inputs are equally likely?

Please answer all to get full points.

Explanation / Answer

There are 'n' numbers in the array.

So arrangement of 'n' numbers can be done in n! ways.

a) Probability that the numbers are in ascending or descending order = 2/n! [As there are two possible favourable arrangements and there are n! possible arrangements]

b) As numbers in the first half of the array are smaller they can be arranged among themselves in (n/2)! ways
Similarly numbers in the second half of the array can also be arranged among themselves in (n/2)! ways.

So favourable number of arrangements = (n/2)! * (n/2)!
Required probability = Favourable number of arrangements / Total number of arrangements = [(n/2)!*(n/2)!]/n!

c) Now if the first number in the array is smallest than the remaining (n-1) numbers in the first half of the array can be arranged among themselves in [(n-1)/2]! ways.
Similarly numbers in the second half of the array can also be arranged among themselves in (n/2)! ways.

So favourable number of arrangements = (n-1/2)! * (n/2)!
Required probability = Favourable number of arrangements / Total number of arrangements = [(n-1/2)!*(n/2)!]/n!

d) Yes E and F are independent.

e) The maximum number of iterations of the loop can be (n-1) that is the entire size of the array.
Probability = 1/(n-1)!

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.