1 Assume we are sorting n distinct values We say that the in

1. Assume we are sorting n distinct values. We say that the input is random if each permutation is equally likely. Donald Trump (who happens be taking this course in his spare time) suggests an alternative definition: An input is random if, for each pair of elements x, y, half the time x is before y (so that half the time y is before x). It is clear that if each permutation is equally likely then the list is random in the sense of Donald Trump. We might wonder if the converse holds. In other words, if the list is random in the sense of Donald Trump, is each permutation equally likely? It is plausable that the converse holds for some values of n and not others. For what values of n does the converse hold? Justify your answer.

Solution

The Donald Trump\'s definition is false. The idea of randomness is that if {x,y} are equally likely, on a new draw x is as likely to show as y irrespective of whether x showed more earlier or y. The converse does not hold for any values of n.