2
$\begingroup$

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?

  • 0
    @DilipSarwate, I wrote "those assumptions are not correct in the real world" because of that and because, even among $d_5$ through $d_{15}$, I don't know that numbers are chosen arbitrarily: issuers may have rules.2011-12-07

1 Answers 1

2

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$.

  • 0
    Thanks. +1. This very nicely confirms the second sentence of my last bullet point, which worried me a little. I was more worried about the first sentence of my last bullet point, though.2011-12-08