# Probability of two random numbers to have same oddity

I was watching a lecture in Coursera. And there, they used this result that
the probability of two random numbers to have the same oddity is $$\mathit{\frac12}$$.

I understood that "oddity" means the number of $$2$$s in the both random number.
That is,

Let $$a = 2^md$$, and $$b = 2^nf$$, where $$d, f$$ are odd numbers and $$m,n, d, f \in \mathbb Z^+$$. What is the probability that $$m$$ and $$n$$ are the same?

If anyone wants to check the original source then here is the link to the video (at time $$19:07$$).

Here are the weekly notes provided by the course. Turn to page $$4$$, first paragraph, lines $$9-10$$

Edit:
$$a,b \in \{1,2,..N\}$$ whrere $$N\in \mathbb Z^+$$

• Do you mean "parity" ? – Peter Dec 29 '19 at 20:07
• @Peter are they same? I mean Parity is whether a number is odd or even. But here mementioned Oddity is number of twos in the number. – Saptarshi Sahoo Dec 29 '19 at 20:13
• OK, sorry, but I still do not understand : Do you mean the number of digits $2$ in both the random numbers ? Also : Which range do you assume ? If there is no bound, the number of digits $2$ is not bounded either. Not sure whether in this case, the question makes sense. – Peter Dec 29 '19 at 20:15
• Yes number of digit two in both random number. Like lets take two random number n=2^as and m = 2^bq, s,q are odd numbers . what is the probability that a=b. – Saptarshi Sahoo Dec 29 '19 at 20:21
• Direct quote. do not paraphrase and give context. This needs to be fixed if wrong. and which course, I can barely find a thing it could be. – user645636 Dec 29 '19 at 20:24

I think you're misunderstanding the video. (I'm not surprised; it's a bit hard to understand.)

He's talking about the “worst case” $$k=l=1$$, in which we have $$mr_1=2s$$ and $$nr_2=2s_1$$ (with $$s$$, $$s_1$$ odd). So there's only one factor of $$2$$ in either $$m$$ or $$r_1$$, and only one factor of $$2$$ in either $$n$$ or $$r_2$$. He then asks, for this worst case, not in general, what the probability is that $$r_1$$ and $$r_2$$ have the same number of factors of $$2$$. He talks about these numbers as “random” without specifying a distribution for them. This is rather questionable. But on the assumption that $$m$$, $$r_1$$, $$n$$ and $$r_2$$ are a priori all equally and independently likely to contain a factor of $$2$$, there are $$4$$ equally likely possibilities given that either $$m$$ or $$r_1$$ and either $$n$$ or $$r_2$$ contains a factor of $$2$$. In $$2$$ of these $$4$$ possibilities, $$r_1$$ and $$r_2$$ have the same number of factors of $$2$$ (either $$0$$ or $$1$$), and in the other two they don't (one has one factor of two and the other has none). Thus, in this worst case, the probability for $$r_1$$ and $$r_2$$ to have the same number of factors of $$2$$ is $$\frac12$$.

URL has shown in another answer that if the question were posed in general, not in this particular case, the answer (again under reasonable assumptions about the distribution) would be $$\frac13$$.

• see my edited question. I missed the range of $a$ and $b$ before. – Saptarshi Sahoo Dec 30 '19 at 6:56

We don’t really use the term “oddity” to refer to what you’re talking about. A more formal term might be the “$$2$$-adic valuation”, denoted $$\nu_2(n)$$: this is the exponent of the greatest power of $$2$$ that divides $$n$$.

Furthermore, talking about a “random integer” doesn’t actually makes sense without further specification, as there’s no uniform distribution on the natural numbers. Nevertheless, we can talk about the behavior of random numbers from $$1$$ to $$N$$, as $$N$$ gets large.

Your result is wrong by the way, and this is quite easy to verify: two numbers having the same $$\nu_2$$ is a stronger condition than having the same parity, which occurs with limiting probability $$\frac12$$. But it doesn’t take too much work to fix it. Let $$P(N,k)= \frac{\lfloor\frac Nk\rfloor}N$$ be the probability of a number from $$1$$ to $$N$$ being a multiple of $$k$$. The probability of two numbers from $$1$$ to $$N$$ having the same $$\nu_2$$ will therefore be $$\sum_{k=0}^\infty \left(P\left(N,2^k\right)-P\left(N,2^{k+1}\right)\right)^2,$$ that is, the probability of both numbers having a $$\nu_2$$ of $$0$$, plus the probability of both numbers having a $$\nu_2$$ of $$1$$, and so on.

Notice also that $$\lim_{N\to\infty}P(N,k)=\frac1k.$$ This allows us to calculate our limiting probability, as $$\lim_{N\to\infty}\sum_{k=0}^\infty \left(P\left(N,2^k\right)-P\left(N,2^{k+1}\right)\right)^2=\sum_{k=0}^\infty \frac1{4^{k+1}}=\boxed{\frac13}.$$

• But they have given answer 1/2 – Saptarshi Sahoo Dec 29 '19 at 21:29
• @UzumakiSaptarshi $\frac12$ can’t possibly be the answer to the problem you describe: see my remark. – URL Dec 29 '19 at 21:31
• see my edited question. I missed it before. – Saptarshi Sahoo Dec 30 '19 at 6:55
• @UzumakiSaptarshi I think my answer still holds. If you want to talk about a specific $N$, you can simply not consider the last step, and plug the formula for $P\left(N,2^k\right)$ directly. – URL Dec 30 '19 at 6:57