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.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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$$

share|improve this answer
    
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

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.