This post is a digression. It’s not about constructing mathematical models of real world phenomena. It’s about sequences of numbers like the famous Fibonacci sequence and the Android pattern unlock screen shown here.
The rationale for a graphical pattern instead of a numeric PIN is clear. Humans are much better at remembering patterns than strings of digits. But is the pattern as secure? Other issues aside, such as traceability of fingerprint smudges that allows an attacker to recover the pattern, are there as many patterns as there are numeric PINs of the same length?
Well that’s where understanding recursion relations is useful. A recursion relation defines a sequence of numbers by a relationship between and all preceding sequence members. For example the Fibonacci sequence is defined via
Depending on the type of recursion relation (whether it is linear, for example), there are a variety of methods for solving them. Let’s use the power of recursion to find the number of possible Android unlock patterns that connect dots.
To make the problem seemingly more complicated (but really simpler) let’s separately compute the number of patterns that start at the center, side and corner of the 3×3 grid of dots. Let’s call those numbers and The total number of unlock patterns is
Because there are 4 corner and 4 side dots in the 3×3 grid.
Let’s now derive a recursion relation for and The first step in the program is to note that when the pattern consists of only one dot (that would not be a very secure pattern) we trivially get and
Now let’s imagine that we managed to compute and for some We can then quickly compute noticing that the very first link that is made from the center dot can only go to a side dot (4 possible ways) or to a corner dot (also in 4 possible directions). Therefore
When starting from the side dot, there are 4 ways to get to a corner dot, one way to get to the center dot and 2 ways to get to other side dots, therefore
And finally when starting from a corner dot, there are 4 ways to get to a side dot and one way to get to the center dot, thus
The above three relationships can be summarized as
using matrix notation by defining a vector and a matrix
Hang on tight, we are almost there. The simple recursion relation (1) means that we can obtain the numbers of patterns connecting N dots from those for N-1 dots by just applying the matrix A. Applying this reasoning recursively we arrive at
I won’t bore you with the rest of the calculation which is quite routine. As my eccentric math tutor used to say: “After this point it’s just algebra!”
Here is the result of the calculation:
|N||Number of patterns connecting N dots||Number of numeric PINs of N digits|
Clearly, the number of patterns grows slower than the number of numeric PINs. This may not matter, however, if patterns are easier to remember and therefore one can comfortably have a longer pattern.
The only sure way to determine whether it is indeed easier to remember patterns, is through careful experiments with human subjects. Until such data are available, all statements memorability and security of patterns vs PIN’s are pure speculation…
The restriction that a dot cannot be used more than once in a pattern *dramatically* reduces the number of allowed patterns. Please see comments for the true number of unlock patterns.