Suppose we have a deck of index cards marked 1 through n that has been thoroughl
ID: 3195623 • Letter: S
Question
Suppose we have a deck of index cards marked 1 through n that has been thoroughly shuffled. One way to sort this deck is to pick out the smallest cards in order first, starting with 1, until you reach the end of the deck, and then return to the beginning and repeat the process. For example, if we had the following order:
4, 1, 6, 2, 3, 5
we would start by picking out 1, 2, and 3, then go back to the beginning and pick out 4 and 5, and then finally go back to the beginning and pick out 6, so in total we would have to go back to the beginning of the deck two times. Notice that the times when we have to go back to the beginning of the deck are precisely when i + 1 comes before i, for any integer i.
Using indicator random variables and linearity of expectation, find the expected number of times we have to go back to the beginning of the deck.
Explanation / Answer
Expected value of a discrete random variable is R defined as following. Suppose R can take value r1with probability p1, value r2 with probability p2, and so on, up to value rk with probability pk. Then the expectation of this random variable R is defined as