# Expected value - removing digits from a number

Recently I have come across an interesting probability problem:

Let $P$ denote an $n$-digit number, i.e. $P = \sum\limits_{i=0}^{n-1}10^ic_i$ where $c_i \in \lbrace 0, \dots, 9 \rbrace$. Now we are going to reduce this number, namely we will remove each digit independently with probability $p$. The task is to calculate the expected value of the number being obtained. (If every digit gets removed, we treat the resulting number as a $0$).

Quite honestly, I don't really know how to tackle this. The difficult part here is certainly the shift of the more significant digits to the right, which occurs whenever a digit is removed. Any idea as to how to solve this problem?

-
So are the $c_{i}$ given in advance (so your expectation will be in terms of the $c_{i}$)? –  Daniel Littlewood Jan 23 '13 at 20:47
Well, yes. The possible result could be along the lines of $\sum_{i=0}^{n-1}c_if(i)$ for some funtion $f$. –  Quintofron Jan 23 '13 at 20:50
Do you close it up? If you remove the $2$ from $123$ are you left with $103$ or $13$? –  Ross Millikan Jan 23 '13 at 20:50
$13$. I literally erase digits from the given number (that's what I meant when I mentioned the shift). Otherwise the problem would be much easier. –  Quintofron Jan 23 '13 at 20:52
I think I've figured out the formula. It is instructive to look first at the example where only one of the $c_i$ is non-zero, since you essentially get the sum of the expected values over these cases –  Thomas Andrews Jan 23 '13 at 22:05

Let $Y_i$ denote the indicator function of the fact that $c_i$ appears in $P$. The sequence $(Y_i)$ is i.i.d. Bernoulli with parameter $1-p$. If $c_i$ contributes, it does so as $c_i{10}^{Y_0+\cdots+Y_{i-1}}$ hence $$P=\sum_{i=0}^{n-1}c_iY_i{10}^{Y_0+\cdots+Y_{i-1}},$$ and $$\mathbb E(P)=\sum_{i=0}^{n-1}c_i\mathbb E(Y_0)\mathbb E({10}^{Y_0})^i.$$ Since $\mathbb E({10}^{Y_0})=p+(1-p)10=10-9p$ and $\mathbb E(Y_0)=1-p$, one gets $$\mathbb E(P)=(1-p)\sum_{i=0}^{n-1}c_i(10-9p)^i.$$

-
Thank you for showing me this clean solution. :) –  Quintofron Jan 23 '13 at 22:41

Let $p_{ij}$ be the probability that the original $i$th digit goes to the $j$th digit. Then the expected value of the $j$th digit after the removal process is is: $e_j=\sum_{i\geq j} p_{ij} c_i$. The total expected value is $\sum_{j} e_j 10^j$.

Now, what is $p_{ij}$? If $i<j$, $p_{ij}=0$. If $i\geq j$, then $p_{ij}=\binom i j p^{i-j}(1-p)^{j+1}$. This is the probability that $i-j$ of the coefficients from $0,...,i-1$ get removed, times the probability that the $i$th coefficient is not removed.

So the total result is:

$$\sum_{j=0}^{n-1} 10^j \sum_{i=j}^{n-1} \binom i j p^{i-j}(1-p)^{j+1} c_i= \\ (1-p)\sum_{i=0}^{n-1} c_i \sum_{j=0}^{i} \binom i j p^{i-j} \left(10(1-p)\right)^{i-j} =\\ (1-p)\sum_{i=0}^{n-1} c_i (p+10(1-p))^i =\\ (1-p)\sum_{i=0}^{n-1} c_i (10-9p)^i$$

You can actually look at just values with one non-zero digit in the $i$th place, and compute the expected value after this operation on that, and sum. So if your starting number is $c10^k$ the expected value is $c(1-p)(10-9p)^k$

Actually, if $q=1-p$ is the probability of a digit remaining, the formula seems a bit nicer:

$$q\sum_{i=0}^{n-1} c_i (1+9q)^i$$

-
I was just about to say you meant "probability of $i-j$ (instead of $j$) being removed", but I see you've already edited this (the respective binomial coefficient is equal to $\binom{i}{j}$ anyway, so it doesn't matter). I must say the number of edits you have made to this post since I started reading it is insane! :D The problem doesn't seem as difficult once you hit on the idea of $p_{ij}$. Thank you for your answer. :) –  Quintofron Jan 23 '13 at 22:11
Thanks. Initially, I forgot the $j+1$ - the added condition that the $i$th digit need to remain. I figured that out when I saw that $p=1$ didn't result in zero. :) –  Thomas Andrews Jan 23 '13 at 22:15