probability of guessing a k-digit number sequentially from n trials

Question

I recently encountered the following problem. Assume that we need to guess a $k$-digit number. We guess it digit by digit and there are $n$ guesses in total. What is the probability of success?

Say, $k=5$, and $n=25$. We can spend, e.g., 9 trials guessing the first digit, then guess the second digit from the 3rd trial etc. But we cannot make more than 25 guesses in total.

I believe we should proceed as follows:

• guessed from 5 trials: $p=1/10^5$; -- we cannot make less than 5 trials when guessing step by step
• guessed from 6 trials: $p=1/10^4\cdot(1-1/10)\cdot 1/9\cdot 5$
• guessed from 7 trials: $p=1/10^3\cdot(1-1/10)^2\cdot 1/9^2\cdot \binom{5}{2}+1/10^4\cdot(1-1/10)\cdot(1-1/9)\cdot 1/8\cdot 5$, etc.

but I'm failing to generalize this scheme. And there is an additional problem that we have to set an upper bound to the number of trials at some point...

UPDATE (09.02): As @JMoravitz suggested, one can write an iterative scheme for computing the probability of guessing exactly $\kappa$ digits from $\eta$ trials, $f(\kappa,\eta)$. I believe that this scheme can be written as $$f(\kappa,\eta)=\frac{1}{10}\sum_{i=1}^{10}f(\kappa−1,\eta−i),$$ where we use the fact that the probability of guessing the digit from $1\le \kappa\le 10$ guesses is always the same: $$p(i=1)=\frac1{10},\quad p(i=2)=\frac{9}{10}\frac{1}{9}=\frac{1}{10},...$$ We also need to add boundary conditions $$\begin{cases}f(\kappa,\eta)=0,&\eta<\kappa\mbox{ (we cannot guess $\kappa$ digits from less than $\eta$ trials)},\\ f(1,\eta)=\frac{1}{10},&0<\eta\le 10\mbox{ (probabilities of guessing the first digit from $\eta$ trials)},\\ f(1,\eta)=0,&\eta=0\mbox{ or }\eta>10.\end{cases}$$ The final probability is to be found as the sum $$p^*=\sum_{i=k}^n f(k,i)=\sum_{i=5}^{25} f(5,i).$$ This scheme looks pretty neat and can be easily computed numerically.

However, I wonder if there is any chance to solve this problem analytically? Perhaps there exists a different approach?...

Answer 1

Let $\ G_i\ $ be the number of guesses taken to determine the $\ i^\text{th}\ $ digit. Then $\ G_1,G_2,\dots\ $ are independent discrete random variables, all uniformly distributed over the integers $\ 1,2,\dots,10\ $, and the total number of guesses taken to determine every one of $\ k\ $ digits is $\ \displaystyle T_k=\sum_{i=1}^kG_i\ $. The probability mass function $\ p_{T_k}\ $of $\ T_k\ $ is therefore the $\ k-$fold convolution of the uniform distribution over the integers $\ 1,2,\dots,10\ $: \begin{align} p_{T_j}(h)&=\sum_{i=1}^{10}\frac{p_{T_{j-1}}(h-i)}{10}\\ &=\sum_{i=\max(1,h-10(j-1))}^{\min(10,h+1-j)}\frac{p_{T_{j-1}}(h-i)}{10}\ , \end{align} because $\ p_{T_{j-1}}(s)=0\ $ for $\ s<j-1\ $ or $\ s> 10(j-1)\ $.

If you're allowed $\ n\ $ guesses to to get all $\ k\ $ digits correct, then your probability of success is $$ \sum_{i=1}^nT_k(i)=\sum_{i=k}^nT_k(i)\ . $$ One convenient way of obtaining $\ p_{T_k}\ $ is to use generating functions. The generating function $\ g_0(x)\ $ of the uniform distribution over the integers $\ 1,2,\dots,10\ $ is given by $$ g_0(x)=\frac{1}{10}\sum_{i=1}^{10}x^i\ , $$ and the generating function of the convolution of two probability mass functions is the product of their generating functions. The generating function $\ g_k(x)\ $ of $\ p_{T_k}\ $ is therefore given by $$ g_k(x)=g_0(x)^k=\frac{1}{10^k}\left(\sum_{i=1}^{10}x^i\right)^k\ . $$ The generating function of $\ p_{T_5}\ $ is \begin{align} \frac{1}{10^5}\big(x^{50}&+5x^{49}+15x^{48}+35x^{47}+70x^{46}+126x^{45}\\ &+210x^{44}+330x^{43}+495x^{42}+715x^{41}+996x^{40}\\ &+1340x^{39}+1745x^{38}+2205x^{37}+2710x^{36}+3246x^{35}\\ &+3795x^{34}+4335x^{33}+4840x^{32}+5280x^{31}+5631x^{30}\\ &+5875x^{29}+6000x^{28}+6000x^{27}+5875x^{26}+5631x^{25}\\ &+5280x^{24}+4840x^{23}+4335x^{22}+3795x^{21}+3246x^{20}\\ &+2710x^{19}+2205x^{18}+1745x^{17}+1340x^{16}+996x^{15}\\ &+715x^{14}+495x^{13}+330x^{12}+210x^{11}+126x^{10}\\ &+70x^9+35x^8+15x^7+5x^6+x^5\big)\ . \end{align} Therefore, the probability of determining $5$ digits with $25$ or fewer guesses is \begin{align} \frac{1}{10^5}\big(1&+5+15+35+70+126+210+330+495+715\\ &+996+1340+1745+2205+2710+3246\\ &+3795+4335+4840+5280+5631\big)\\ &=\frac{38125}{10^5}\ . \end{align}

Answer 2

May I try to offer an approach to have some estimation to this problem (and my apology in advance if what I am writing is trivial or wrong):

Let $X_i$ denote the number of guesses required to find the $i$ digit. Hence, lets denote $X = X_1+..+X_k$ as the total number of guesses. $X$ is sum of independent random variables.

It can be calculated that $\mathbb{E}X = 5.5k \; V[X] = 8.25k$

And if we denote $n = t + \mathbb{E}X$ ($t$ is not necessarily natural number, or you can take a floor of this equation) then we can have some estimation by Chevishev ineq.: $$\mathbb{P}(|X-\mathbb{E}X|>t)\leq \frac {8.25k}{t^2}$$

Then we can get some conclusions about the problem, for instance, that for large enough numbers if the number of guesses allowed is in order of $O(k^{0.5+\epsilon})$ then we get that $$\mathbb{P}(|X-\mathbb{E}X|>t)\leq \frac {8.25k}{(k^{0.5+\epsilon})^2}$$ is small as we wish, and hence we get good lower bound to the probability of success: $$1- \mathbb{P}(|X-\mathbb{E}X|>t) = \mathbb{P}(\mathbb{E}X - t\leq X\leq\mathbb{E}X+t = n) \leq \mathbb{P}(X\leq n)$$