Collecting Verification Codes (1)

• Introduction
• Problem Statement
• Solution
  • Solution 1
  • Solution 2
• Conclusion

Introduction

When I try to log into my university’s SSO system, it gives me a two-digit verification code that I must select on my cellphone. For instance, in the images below, the website (on the left) shows the number 25, and I would tap 25 on my phone (on the right). Now, I’m curious about how many attempts I would need to make to see all possible 100 codes.

Problem Statement

Let $S$ be a finite set of size $N$. At the beginning, a set $F$ is initialized to be an empty set. For each step, a random element $r$ is chosen at uniformly random from $S$ and put to $F$, i.e., $F\leftarrow F\cup \{r\}$. Then, what is the expected number of steps to reach $S=F$?

Now, take your time to solve this problem! (Hint: it is easy.)

Solution

Solution 1

For fixed $N$, suppose there are $n$ elements should be chosen to reach $S=F$. In other words, $n=|S\setminus F|$. Now, let $a_n$ be the expected number of additional steps at the moment. We let $a_0=0$.

Then, we have $n/N$ probability of getting a new fresh number and $1-n/N$ probability of getting a number that has been chosen before. Thus, noticing that we need this one step to choose an element, we have the following recursive formula:

$$a_n=1+\frac{n}{N}\cdot a_{n-1}+(1-\frac{n}{N})\cdot a_n$$

Rearranging, we get

$$a_n=a_{n-1}+\frac{N}{n}\text{.}$$

Equation $\text{(???)}$ directly gives

$$a_n=N\cdot \sum _{i=1}^n\frac{1}{i}=N\cdot H_n$$

where $H_n$ is the $n$-th harmonic number.

In particular, we have $a_N=N\cdot H_N$. (In fact, this solution needs more verification that each $a_i$ exists but I omit.)

Solution 2

For fixed $N$, let $X_i$ be a random variable for the number of steps until the next element which has not been chosen before when there are $i$ elements not chosen. Then, we immediately get $\mathbb{E}[X_i]=N/i$. Then, $X$, the random variable for the number of steps to reach $F=S$ equals $\sum _{i=1}^N{X}_i$; by linearity, we get

$$\mathbb{E}[X]=\sum _{i=1}^N\mathbb{E}[X_i]=N\cdot \sum _{i=1}^N\frac{1}{i}=N\cdot H_N\text{.}$$

Conclusion

Hence, as $100\cdot H_{100}\approx 518.74$, I shall expect about 519 log-in tries to observe all 100 numbers.