It seems as though every Visa or Mastercard account number I've ever had (in the United States) has had at least two consecutive digits identical. I was wondering what the probability is that a particular account number will have at least two consecutive digits identical.
Assume the account number is $16$ digits long, totally ordered, with digits called $(d_i)_{i=1}^{16}$.
Let $$a_i=\left\{\begin{array}{rl}d_i&i \textrm{ is even}\\2d_i&i \textrm{ is odd and }2d_i\lt9\\2d_i-9&i \textrm{ is odd and }2d_i\gt9\end{array}\right.$$
Assume $d_1=4$, $d_2$ through $d_{15}$ are chosen arbitrarily, and $d_{16}$ is chosen so that $$\sum_{i=1}^{16}a_i\in10\mathbb Z.$$
(Fwiw, those assumptions are not correct in the real world, but they're based on real-world facts.)
My answer so far is this:
Consecutive integers are distinct iff all the following hold:
- For $2\le i\le15$, $d_i\ne d_{i-1}$ (probability $\frac9{10}$ each).
- Since the ten digits all appear as values of $a_i$ (for fixed $i$, as $d_i$ varies), we might as well assume, in computing $d_{16}$, that the $d_i$ are used in the sum, i.e., that $\sum_id_i\in10\mathbb Z$. But since $d_2,\ldots,d_{15}$ are with equal probability any digit, so is $d_{16}$, so the probability it's distinct from $d_{15}$ is just $\frac9{10}$ again.
So we get $1-.9^{15}\approx .79$.
However I'm very unsure about that last bullet point. Can someone make it more rigorous or correct it?
Best Answer
It looks fine to me. What you’re using is the fact that if the random variables $X$ and $Y$ are uniformly distributed in $\{0,1,\dots,n-1\}$, then so is the reduced sum $Z=(X+Y)\bmod n$, where $\bmod$ here denotes the binary operation. (In your case $n$ is of course $10$.)
To see this, you can observe that $X+Y$ itself takes values in the set $\{0,1,\dots,2n-2\}$, with the following probabilities:
$$\mathbb{P}[X+Y=k]=\begin{cases} \frac{k+1}{n^2},&k\le n-1\\\\\\ \frac{2n-1-k}{n^2},&k\ge n-1\;. \end{cases}$$
(Just count the number of ways that each sum can occur.)
But $Z=(X+Y)\bmod n=k$ iff $X+Y=k$ or $X+Y=k+n$, so
$$\mathbb{P}[Z=k]=\frac1{n^2}\bigg((k+1)+\big(2n-1-(k+n)\big)\bigg)=\frac1{n}\;,$$
i.e., $Z$ is uniformly distributed in $\{0,1,\dots,n-1\}$. By induction the same is true for any finite sum reduced modulo $n$.