Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
In (US) credit cards, the first four digits usually identify the bank that issues the card, and these may well have repeated digits. Some of my cards do, and some don't, have repeated digits among the first four. –  Dilip Sarwate Dec 7 '11 at 3:09
    
@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. –  msh210 Dec 7 '11 at 6:17

1 Answer 1

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

share|improve this answer
    
A linear $(n,k)$ code over a finite field $\mathbb F_q$ is a $k$-dimensional subspace of $\mathbb F_q^n$, and for any given coordinate, either all the $q^k$ codewords have value $0$, or for each $x \in \mathbb F_q$, exactly $q^{k-1}$ codewords have value $x$. Here, we have a ring $\mathbb F_10$ and a similar result holds; all the codewords have equal distribution in any coordinate. –  Dilip Sarwate Dec 7 '11 at 13:34
    
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. –  msh210 Dec 8 '11 at 15:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.