Runs of letters and digits in passwords
If a password of length n is made up of lower case letters and digits, with each symbol appearing with equal probability, how many times would you expect to shift between letters and digits when typing the password? If you're typing the password on a mobile device, how many times would you change between alphabetic to numeric entry modes?
This page shows how to compute the expected number of runs in a sequence of binary outcomes when the two outcomes have probabilities p and 1-p. The number we're after is one less than this, because the first run does not requiring changing input modes. The expected number of input mode changes is
= 2(n - 1)p(1 - p).
In our case we can take p = 26/36. It doesn't matter whether p represents the probability of a letter or a digit because is symmetric in p and 1-p.
For moderately large n, the number of mode changes is approximately proportional to n. So for a password of n characters we should expect approximately
2 * 26/36 * 10/36 n 0.4 n
mode changes.
The variance in the number of mode changes is
^2 = 2pq(2n - 3 - 2pq (3n - 5))
which for large n is approximately
4npq(1 - 3pq).
In our case this reduces to
4 * 26/36 * 10/36 * (1 - 3 * 26/36 * 10/36) n 0.32 n.
The standard deviation is the square root of variance, which is approximately
0.57 n
in our example.
So typing a password of n characters will often require around
0.4 n 0.57 n
mode changes.
For example, typing a 20-character password would often require between 5 and 11 input mode changes.
Related postPostscriptVariations on this problem come up fairly often. For example, yesterday I needed to create a spreadsheet with a permutation of the numbers 1 through 26. I had a spreadsheet with a column containing a permutation of the numbers 1 through 100, and so I copied it and deleted the rows with numbers greater than 26. The math above shows that on average you'd expect to change from a run of rows to keep to a run of rows to delete about 38 times.
The post Runs of letters and digits in passwords first appeared on John D. Cook.