k numbers can be arranged in k! ways, only one of which is a run. This reasoning shows that the probability that a sequence of k random numbers forms a run is 1/k!.
However, because runs are maximal, you also have to look at the (k + 1)th number too. If it's not greater than the k-th number, the (increasing) run has size k; otherwise the run has size (at least) k + 1. In other words, the probability 1/k! is too large because it includes runs of size k that are actually part of runs of size k + 1. To correct, subtract the probability of runs of size k + 1.
"But wait," you may be thinking to yourself, "this formula tells me that the probability of a run of size 1 is 0.5 (= 1 - 0.5 = 1/1 - 1/2 = 1/k! - 1/(k + 1)!). Every element is a run of size 1, so the probability should be 1."
Ah, but you're forgetting that runs should be maximal. A single number n is a (let's try decreasing this time) run only if it is followed by a number that is not less than n; otherwise n is part of a run of size at least 2. Because the numbers are random, the probability that the number after n is greater than n is 0.5.
This page last modified on 2 March 2005.