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
    Wait, so you want to know about the binary expansion of ternary expansions with no digit equal to $2$?2011-03-31
  • 0
    @Alex: Yes. I believe that there could be a very simple relation here, I just can't see it yet.2011-03-31
  • 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}$.2011-03-31
  • 0
    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$.2011-03-31
  • 0
    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.2011-03-31
  • 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

You want a formula for $\mathbb{P}\left(X(m)=0\right)$. Writing $$\sum_{0\leq k

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.