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.

Please excuse me for asking questions like this while knowing essentially nothing about probability, but I'd really like to find out what the chances are of $X$ odd digits being present in a number consisting of $N$ digits, where $N$ is greater than or equal to $X$.

It doesn't sound like a really tough problem to solve (sorry if it's actually really hard!), so I would very much really appreciate a very basic, low-level explanation.

Thank you for your time!

share|improve this question
1  
Exactly $x$ digits are odd? Also, you should always indicate what you have tried and work with some simple examples. For instance, can you find the probably that a number with $n$ digits contains at least one odd digit? With exactly one odd digit? Doing this for the $n \in \{1, 2, 3, 4, 5\}$ might help. –  Joshua Shane Liberman Dec 16 '11 at 21:21

4 Answers 4

up vote 0 down vote accepted

There might be some theoretical problems that I will skip. Let's analyse numbers from the interval [0,1). Basically, you can think of a number as a list of numbers between 0 and 9. For example 0,25 is a list consisting of 2 and 5, and 0,913 is a list of 9, 1 and 3. So a random number is a random list. You want the first digit to be odd: there are 5 odd digits (1,3,5,7,9) and 5 even so the chance that there is one (or more) odd digit is $\frac{1}{2}$. If you want to have exactly one odd digit then you want one odd and the next even: so it is $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$. If you want two odd digits, then you want the first to be odd, the second to be odd and the third to be even. So you get $(\frac{1}{2})^3=\frac{1}{8}$. In general you get $(\frac{1}{2})^{X+1}$.

Well, if you are talking about integers and want exactly X digits out of D to be odd (what you probably mean) than @RobertIsrael's answer is what you need. Let me explain his result, because you wanted the answer to be easy. ${d \choose x}$ is the number of different choices of $x$ numbers out of $d$ numbers. Here it means choices of $x$ odd digits out of the whole number. So in so many ways a number can satisfy your condition ($x$ digits odd out of $d$). Let's compute the chance that a number satisfies your condition in a particular "way". Then the result will be multiplication of the number of ways and the chance for each way.

Such a choice says exactly which digits should be odd and which should be even. If we forget about the first digit, there is chance of $1/2$ that a particular digit is odd (or even), so if we multiply those chances, we get $2^{-d+1}$ as Robert wrote. If we allowed leading zero, then the result would be ${d \choose x}2^{-d}$.

But what about zero? It was chosen among $x$ odd digits with probability $\frac{x}{d}$. If $x=1$ then the probability is obviously $\frac{1}{d}$, and it can be multiplied if $x$ is bigger. So if it is chosen, it has to get value 1,3,5,7 or 9 out of 9 possible (leading 0 is forbidden). So we get $\frac{x}{d}\cdot\frac{5}{9}$. If it is not chosen (with probability $1-\frac{x}{d}=\frac{d-x}{d}$, then it has to be 2,4,6 or 8 (and there are again 9 possibilities), so we get $\frac{d-x}{d} \cdot \frac{4}{9}$. By adding $\frac{x}{d}\cdot\frac{5}{9}$ and $\frac{d-x}{d} \cdot \frac{4}{9}$, we get $\frac{x+4d}{9d}$ as it is written in Robert's post.

share|improve this answer
    
Shouldn't the length of such as list be a variable in the general formula? It seems more likely that a number consisting of 12 digits has 4 odd numbers than a number consisting of only 5 digits. In both cases, the chance of that happening would be 1 in 32 according to your formula though (1/2)^(4+1). –  Chris Dec 16 '11 at 21:48
    
I thought about an infinite list and wanted X first digits to be odd. Sorry, that was not what you meant as I can see now. –  savick01 Dec 16 '11 at 21:52
    
Thank you very much for the explanation of his formula! –  Chris Dec 16 '11 at 21:57

Given a $d$-digit positive integer ($d>1$), and assuming a uniform probability distribution over all integers of that length, you can calculate the probability $P_d(x)$ that exactly $x$ digits are odd. The first digit is odd with probability $5/9$ (since it cannot be $0$), and each subsequent digit is odd with probability $1/2$, and each digit is an independent random variable. If the first digit is odd, then we need $x-1$ of the remaining $d-1$ digits to be odd; otherwise, we need $x$ of the remaining $d-1$ digits to be odd. The result is $$ \begin{eqnarray} P_d(x) &=& \frac{5}{9}{{d-1}\choose{x-1}}\left(\frac{1}{2}\right)^{d-1} + \frac{4}{9}{{d-1}\choose{x}}\left(\frac{1}{2}\right)^{d-1} \\ &=&\frac{1}{9\cdot2^{d-1}}\left(\frac{5(d-1)!}{(x-1)!(d-x)!} + \frac{4(d-1)!}{x!(d-x-1)!}\right) \\ &=&\frac{(d-1)!}{9\cdot2^{d-1}}\frac{5x + 4(d-x)}{x!(d-x)!} \\ &=& \frac{8+2(x/d)}{9}{d\choose{x}}\left(\frac{1}{2}\right)^{d}. \end{eqnarray} $$ Here the prefactor is a correction to the probability that exactly $x$ of $d$ flipped coins turn up heads, i.e., it accounts for the fact that the first digit can't be $0$. As you can see, this pushes the distribution slightly to the right; the expected number of odd digits is just over $d/2$.

If you instead want to know the probability $Q_d(x)$ that at least $x$ digits are odd, then simply sum over the exact values from $x$ to $d$: $$Q_d(x) = \sum_{y=x}^{d}P_d(y) = 1-\sum_{y=0}^{x-1}P_d(y).$$

share|improve this answer

There is no uniform probability distribution on an infinite set of integers, so the question as stated doesn't make sense. What you can say, though, is something like this: if you choose a random nonnegative integer of exactly $d$ digits (leading 0's not allowed), the probability that exactly $x$ of those digits are odd is ${d \choose x} \frac{x+4d}{9d} 2^{d-1}$.

share|improve this answer
    
Thank you for your reply, but I fail to see what's wrong with my question, "infinite set of integers'? The (X or more) mentioned in my question is actually predefined, but is always a number equal to or greater than X. I think that's the same situation you made of it, right? –  Chris Dec 16 '11 at 21:40

The problem as posed does not have an answer. But a closely related problem does.

We modify the problem to specify that we choose an $n$-digit number at random, for fixed $n$. First we find how many $n$-digit integers there are. The first digit can be anything but $0$, so there are $9$ choices for the first digit. For every choice of first digit, there are $10$ choices for second digit, and for every choice of first digit and second digit, there are $10$ choices for the third digit, and so on for a total of $9\cdot 10^{n-1}$ choices. A simpler way of getting at the same thing is to note that we are, for say $n=5$, looking at the numbers from $10000$ to $99999$ inclusive, and there are $99999-10000+1$ of these, which is $90000$. The same idea works for more digits.

All these numbers are equally likely. Now we ask how many of our numbers have exactly $x$ odd digits.
The analysis is a little different for $n=x$ than for $n>x$, so we first deal with the case $n=x$. All digits must then be odd. There are $5$ choices for the first digit, and for each choice there are $5$ choices for the second digit, and so on, for a total of $5^x$. The required probability is then $$\frac{5^x}{9\cdot 10^{x-1}}.$$ There is a fair bit of cancellation, and the probability simplifies to $5/(9\cdot 2^{x-1})$. Not really surprising! The probability that the first digit is odd is $5/9$, and once we are past the first digit, the probability that any subsequent digit is odd is $1/2$.

Next we look at the case $n>x$. Maybe (i) the first digit is odd or (ii) maybe it is even.

In case (i), we must choose where the remaining $x-1$ odd digits will be. This can be done in $\binom{n-1}{x-1}$ ways. Now that we have decided on the locations of the odd digit, we must choose which odd digits we will use. That can be done in $5^x$ ways. Finally, we must fill up the remaining $n-x$ places with even digits. This can be done in $5^{n-x}$ ways, for a total of $$\binom{n-1}{x-1}5^x5^{n-x}=\binom{n-1}{x-1}5^{n}$$ ways.

In case (ii), we must choose where the $x$ odd digits will go, from the $n-1$ places available. There are $\binom{n-1}{x}$ ways to do the choosing. Now there are $5^x$ ways of deciding which odd digits we use. For the even digits, we have $4$ choices at the first place, and $5$ choices at the remaining $n-x-1$ places. Thus the number of choices for case (ii) is $$\binom{n-1}{x}5^x5^{n-x-1}\cdot 4=\binom{n-1}{x}5^{n-1}\cdot 4.$$ Add up. The total number of choices is $$\binom{n-1}{x-1}5^{n}+\binom{n-1}{x}5^{n-1}\cdot 4.$$ Divide by $9\cdot 10^{n-1}$ for the probability. A good deal of further simplification can be done.

Comment: The problem as stated (the number has $x$ or more digits, nothing else specified) cannot be solved, for there is no probability distribution that assigns equal probabilities to all numbers with $x$ or more digits. We could use the idea above to solve the problem for randomly chosen numbers with between $m$ and $n$ digits, where $x \le m \le n$.

share|improve this answer

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.