The up arrow on my keyboard died. One place where I often use it is when entering course grades.
Before if I had a bunch of graded tests for a class and need to enter them into my grading program I would simply click the blank for the student, enter the grade, then move up or down with the arrows to the student for next test in my pile.
Now I can move down with the down arrow but to go up the list I have to reach over to my mouse to click the correct spot which takes a bit longer.
My question is: for a class of size n, how many times should I expect to have to use my mouse to move up the list? (Assume the tests are in a completely random order.)
We need to consider every sequence of two students whose papers occur right after each other in the pile. If the second student's name is alphabetically behind the first name, there is no problem. If the first student's name is alphabetically following the other one, we need to use the mouse.
The interesting thing to notice is that, if there is a uniform distribution where every possible permutation of the pile is as likely, both orderings of the names of these two students are as likely, both occur with probability 1/2.
If there are n students, there are (n-1) pairs of consecutive papers in the pile. In total we can expect (n-1)/2 uses of the mouse.
Solution
