Probability of two random numbers to have same oddity

Question

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^+$

Answer 1

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

Answer 2

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