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?
 A: 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$. 
A: 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.
