# Representing Ternary as Binary: Probability that the first $n$ bits are all zero

I'm using the ternary numeral system, i.e. numbers in base 3. There's a catch: The numbers I'm representing will never have a 2 as a digit. For instance, I use 0,1,10,11,100,101,110,111,... I.e. they look like binary digits, but they're really ternary numbers.

Now I'd like to know, for a random ternary number, in this form, of $m$ digits, what is the probability that the first (least significant) $n$ bits are all zero?

EXAMPLE

For $m=3$, we'd have the following numbers written out in base 3 (remember they only look like they're bits): 000,001,010,011,100,101,110,111. These correspond to the decimal values 0,1,3,4,9,10,12,13 respectively. So representing these in binary, they are 0,1,11,100,1001,1010,1100,1101 respectively. If I take $n=2$, I'd be finding the probability that the 2 least significant bits are all zero. Of the numbers in binary, 0,100, and 1100 have the 2 least significant bits as zero. So out of the 8 possible numbers that I have, 3 have this property. So the probability that I'm looking for is 3/8.

Now, I'm asking, for generalized $m$ and $n$ using this system, what are the probabilities?

-
Wait, so you want to know about the binary expansion of ternary expansions with no digit equal to $2$? – Alex Becker Mar 31 '11 at 17:00
@Alex: Yes. I believe that there could be a very simple relation here, I just can't see it yet. – Matt Groff Mar 31 '11 at 17:08
My instinct is that your random ternary numbers, when represented in binary, will look just like random numbers. In particular their probability of ending in $n$ zeros should be about $2^{-n}$. – Michael Lugo Mar 31 '11 at 18:01
The $n$ least significant bits of a binary number are zero iff the number is divisible by $2^n$. So your question is equivalent to counting the number of ternary numbers for $c \cdot 2^n \leq 3^{m}-1$ with $c \in \mathbb{N}_0$ and every digit is $0$ or $1$. – Marc Bury Mar 31 '11 at 19:30
Hmm...Proof that they are distributed close to randomly is more than acceptable. I think that difference calculus (summations) can give formulas, but it's getting complicated. Get a formula for bit i in number j of the corresponding binary value and call this f(i,j). Then, for number j, we can determine if the least significant bits are zero by taking the product of (1-bit) for the least significant bits, which gives 1 if all bits are 0 and 0 otherwise. Sum these products over the first 2^m numbers and that's the result. This seems a bit much, though. – Matt Groff Mar 31 '11 at 19:43

Let $X(m)$ be the $\mathbb{Z}_{2^n}$-valued random variable $\sum_{0\leq k<m} \varepsilon_k\ 3^k \pmod {2^n}$ where $(\varepsilon_k)$ are i.i.d with $\mathbb{P}(\varepsilon=0)=\mathbb{P}(\varepsilon=1)=1/2$.

You want a formula for $\mathbb{P}\left(X(m)=0\right)$. Writing $$\sum_{0\leq k<m} \varepsilon_k\ 3^k =\varepsilon_0+3 \sum_{0\leq k<m-1} \varepsilon_{k+1}\ 3^{k}$$ we see that $X(m)$ has the same distribution as $\varepsilon +3 X(m-1)$, where $\varepsilon$ and $X(m-1)$ are independent. This suggests the following approach.

Define a Markov chain on $\mathbb{Z}_{2^n}$ that starts at zero, and when in state $x$ randomly jumps to one of $3x$ or $3x+1$. The probability you want is the $(0,0)$th entry of $P^m$ where $P$ is the transition matrix of the chain. For instance, here is the transition matrix for $n=2$, that is, in the case when we are working modulo 4:

$$P=\pmatrix{1/2&1/2&0&0\cr 1/2&0&0&1/2\cr 0&0&1/2&1/2\cr 0&1/2&1/2&0}$$

And here is its third power

$$P^3=\pmatrix{3/8&3/8&1/8&1/8\cr 3/8&1/8&1/8&3/8\cr 1/8&1/8&3/8&3/8\cr 1/8&3/8&3/8&1/8}.$$

We see your calculated value of $3/8$ in the top left corner. By diagonalizing the matrix we find that, for $n=2$, $$\mathbb{P}(X(m)=0)={1\over 4}+{1\over 4} 2^{\lfloor {(1-m) /2} \rfloor}.$$

Back to the general case. Since $3$ is invertible modulo $2^n$, the Markov chain is doubly stochastic (its column sums are all equal to 1) and so has the uniform distribution on $\mathbb{Z}_{2^n}$ as its unique invariant distribution. In the long run, all states are equally likely.

In short, $\mathbb{P}(X(m)=0) \to 1/2^n$ as $m\to\infty$.

-

I'm taking a generating function approach here. The numbers you are considering are those whose ternary representation contains a total of $m$ digits and have only 0 or 1 as digits. The numbers that are allowed in your ternary representation are essentially the powers of $x$ in the following function

$$f(x) = (1+x)(1+x^3)(1+x^{3^2})\ldots(1+x^{3^{m-1}})$$

The total number of such numbers is simply $2^m$.

We want to count the number of such numbers which have zeros in the n least significant bits in the binary representation. A number $k$ will have n zeros in the least significant bits of its binary representation only if $k$ is divisible by $2^n$.

In order to count this, we can use a trick involving the $2^n -$th roots of unity. I'll illustrate with an example.

For $m = 3, n=2$, we start with

$$f(x) = (1+x)(1+x^3)(1+x^9)$$

The number of powers of $x$ with 2 zeros in the least significant digits in binary is the same as the number of powers of $x$ which are divisible by 4. Consider the $4^{th}$ roots of unity (I'll call them 1,$\omega$, $\omega^2$ and $\omega^3$). Then, the number of powers of $x$ which are divisible by 4 is

$$N = \frac{1}{4}(f(1)+f(\omega)+f(\omega^2)+f(\omega^3))$$

You get $N=3$ by evaluating the above expression and the probability is $\frac{3}{8}$. This method can be generalized to other values of $m$ and $n$ easily. This is essentially a mechanical approach that requires a reasonable amount of calculation to get the answer, but those calculations can be done easily using software like mathematica.

-