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.

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?

share|improve this question
    
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
2  
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 Gillé 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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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

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

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

\begin{equation} f(x) = (1+x)(1+x^3)(1+x^9) \end{equation}

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

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

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.

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.