Chances of $X$ digits in a number being odd?

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.

-
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

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.

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

-

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

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

-