6
$\begingroup$

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?

  • 0
    For $n=1$ the probability is $1/2$, for $n=2$ it seems to be $1/4 + 1/2^{\lceil m/2 \rceil +1}$ which is not random but converges on $1/4$, and it gets more complicated for larger n. $2^{-n}$ looks plausible as a limit for all $m$.2011-03-31

2 Answers 2

4

Let $X(m)$ be the $\mathbb{Z}_{2^n}$-valued random variable $\sum_{0\leq k 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 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$.

2

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.