What is the formula I can use to estimate the difficulty in generating vanity Bitcoin addresses?
It is better to explain by example:
We need to find a vanity address with the prefix "1Love".
The minimum address with this prefix is "1Love1111...1111+ControlSum" and this corresponds to the number Xmin.
The maximum address with this prefix is "1Lovezzzz...zzzz+ControlSum" and this corresponds to the number Xmax.
("1" and "z" are the first and last character of the Base58 encoding used in the bitcoin addresses https://en.wikipedia.org/wiki/Base58)
Then the difficulty of finding such a vanity address is:
diff = (Total number of bitcoin addresses) / (Xmax - Xmin)
For the prefix consisting of the characters "1" there is a special case and complexity that must be considered differently.
The probabilities are detailed here:
"The difficult of finding a vanity address depends on its exact structure (leading letters and numbers) and how likely such an output is given the algorithms involved, which can consist of several pivots where the difficulty suddenly changes."
Difficulty can be quite easy or quite hard depending on the structure and length of the vanity portion of your address