Keep drawing integers from a random number generator (or a customized lottery machine) until you get a number that is smaller than the previous pick. If your run ends after three or fewer draws (including the last picked smaller number) then you pay $10. Otherwise, you receive $20. Will you accept this bet? Think about it.

Your instincts may tell you it’s a good bet. You need to pick at least two numbers before your run could possibly end. So it seems plausible that the average length of such draws would be larger than three. But, being a cautious person, you decide to carefully analyze the odds before putting your money where your gut is.

Consider a run of K integers i.e. the first K-1 are increasing and the Kth one is decreasing, with K > 1.How many ways can K unique integers be arranged in such a way?
K-1Why?
Place any of the not-largest K-1 of the numbers in the last position and place the remaining numbers in their unique increasing order in the first K-1 positions.How many total ways can K unique integers be arranged?
K! = K(K-1)(K-2)...1What's the probability of a run length of K?
(# ways of arranging K numbers such that the first K-1 are increasing and the Kth one is decreasing) / (total # of ways of arranging K numbers)
= (K-1) / K!|----------------|------------------|---------------------|
| Run Length (K) | Probability of K | Probability of <= K |
|----------------|------------------|---------------------|
| 2 | 1/2 | 1/2 = 0.5 |
| 3 | 1/3 | 5/6 = 0.83333... |
| 4 | 1/8 | 23/24 = 0.958333... |
| ... | ... | ... |
|----------------|------------------|---------------------| What's your expected return in the wager?
(probability of K > 3) x $20 - (probability of K <= 3) x $10
= (1/6) x $20 - (5/6) x $10
= -$5 What is the expected run length?
sum of probability-of-K-run x K for K = 2, 3, 4, ...
= sum of (K - 1) / K! x K
= sum of 1 / (K - 2)!
= 1/0! + 1/1! + 1/2! + 1/3! + ...
= e (Euler's constant)
= 2.718...This result holds for any infinite set that has elements that can be strictly ordered (e.g. real numbers between any two real numbers).One caveat: the above analysis assumed that all the drawn elements were unique and did not account for the possibility of duplicate picks. That's because the probability of a duplicate pick tends to 0 as the set of elements that we're picking from approaches infinity.
Why?
Probability of at least one duplicate in K picks out of a set of N unique elements
= 1 - N(N-1)...(N-K+1) / N^K = K(K-1)/(2N) + O(1/N^2)
-> 0 as N -> infinity

Your actual odds of winning are as low as 1 in 6, in what seemed like a pretty good bet at first glance. And, the expected run length, unexpectedly, is Euler’s constant! If you’d like to try your hand at this, head over to https://www.random.org/ and use the random number generator there to see what run lengths you get.

Rolling Restarts

Do these findings have anything to do with the real world or are they purely of theoretical interest? They actually showed up in a very real way in my work as a software engineer. In a nutshell, we were interested in analyzing the impact of rolling restarts of servers on the assignment of keys to those servers. Rolling restarts are common in distributed systems to upgrade all the servers to the latest version of the software on a periodic basis (e.g. weekly), without causing undue disruption in service. “Rolling” means only upgrade a small set of servers at a time (e.g. 1), before moving on to the next set of servers. “Key assignment” refers to the common pattern of assigning a key (e.g. a user) to one server (e.g. for caching user data). If the rolling restart is done one server at a time, and if each key is assigned to a server randomly, and if each key on an updating server is reassigned to another random server, then the expected number of reassignments of a key is e-1 or 1.718…

We were relieved that rolling restarts are much less disruptive than we had naively expected, with each key being reassigned fewer than two times on average. And we were also amused at this curious emergence of Euler’s number ‘e’ in a common pattern in real-world distributed software systems.

The calculation for key reassignments on a rolling restart is very similar to the one done for increasing draws. If the servers are labeled as integers, and the order of the integers is the rolling restart order, then the probability of K assignments is the probability of assigning the key (one after the other) to K-1 servers with increasing labels (which means each of those servers will be updated and the key will be reassigned), followed by a Kth server with a decreasing label (which means that the server was already updated and the key will be stable).