Representación ternaria como binario: probabilidad de que los primeros bits de $n$ son cero

Question

Estoy usando el ternario sistema de numeración, es decir, los números en la base 3. Hay un problema: Los números que estoy representando nunca tendrá un 2 como un dígito. Por ejemplo, yo uso 0,1,10,11,100,101,110,111,... I. e. se ven como dígitos binarios, pero en realidad ternario números.

Ahora me gustaría saber, por un azar del número ternario, en esta forma, de $m$ dígitos, ¿cuál es la probabilidad de que la primera (menos significativo) $n$ bits son cero?

EJEMPLO

Para $m=3$, tendríamos los siguientes números escritos en la base 3 (recuerda que sólo se ven como son bits): 000,001,010,011,100,101,110,111. Estos corresponden a los valores decimales 0,1,3,4,9,10,12,13 respectivamente. Por lo representan en binario, son 0,1,11,100,1001,1010,1100,1101 respectivamente. Si me tome $n=2$, me gustaría hallar la probabilidad de que los 2 bits menos significativos son todos cero. De los números en binario, 0,100, y 1100 tiene los 2 bits menos significativos como cero. Así que de los 8 posibles números que tengo, 3 tienen esta propiedad. Por lo que la probabilidad de que estoy buscando es de 3/8.

Ahora, yo estoy pidiendo, para generalizada $m$ $n$ el uso de este sistema, ¿cuáles son las probabilidades?

Answer 1

Me estoy tomando una generación de función de enfoque aquí. Los números que están considerando son aquellos cuya ternario representación contiene un total de $m$ dígitos y sólo 0 o 1 como dígitos. Los números que están permitidos en su ternario representación son esencialmente los poderes de $x$ en la siguiente función

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

El número total de dichos números es simplemente $2^m$.

Queremos contar el número de números que tienen ceros en los n bits menos significativos en la representación binaria. Un número $k$ se tiene n ceros en los bits menos significativos de su representación binaria sólo si $k$ es divisible por $2^n$.

Con el fin de contar esto, podemos usar un truco que involucra la $2^n -$th raíces de la unidad. Voy a ilustrar con un ejemplo.

Para $m = 3, n=2$, comenzamos con

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

El número de facultades de $x$ con 2 ceros en los dígitos menos significativos en binario es el mismo que el número de facultades de $x$ que son divisibles por 4. Considere la posibilidad de la $4^{th}$ raíces de la unidad (yo les llamo 1,$\omega$, $\omega^2$ y $\omega^3$). Entonces, el número de facultades de $x$ que son divisibles por 4 es

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

Consigue $N=3$ por la evaluación de la expresión anterior y la probabilidad es $\frac{3}{8}$. Este método se puede generalizar a otros valores de $m$ $n$ fácilmente. Esta es, esencialmente, de un modo mecánico que requiere una cantidad razonable de cálculo para obtener la respuesta, pero los cálculos se pueden hacer fácilmente utilizando programas como mathematica.

Answer 2

Deje $X(m)$ $\mathbb{Z}_{2^n}$valores de variable aleatoria $\sum_{0\leq k<m} \varepsilon_k\ 3^k \pmod {2^n}$ donde $(\varepsilon_k)$ son yo.yo.d con $\mathbb{P}(\varepsilon=0)=\mathbb{P}(\varepsilon=1)=1/2$.

Quieres una fórmula para $\mathbb{P}\left(X(m)=0\right)$. Escrito $$\sum_{0\leq k<m} \varepsilon_k\ 3^k =\varepsilon_0+3 \sum_{0\leq k<m-1} \varepsilon_{k+1}\ 3^{k}$$ vemos que $X(m)$ tiene la misma distribución que $\varepsilon +3 X(m-1)$, donde $\varepsilon$ $X(m-1)$ son independientes. Esto sugiere el siguiente enfoque.

Definir una cadena de Markov en $\mathbb{Z}_{2^n}$ que comienza en cero, y cuando en el estado de $x$ al azar salta a uno de $3x$ o $3x+1$. La probabilidad de que usted desea es el $(0,0)$th entrada de $P^m$ donde $P$ es la matriz de transición de la cadena. Por ejemplo, aquí es la matriz de transición para $n=2$, es decir, en el caso de que cuando estamos trabajando 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}$$

Y aquí es su tercera potencia

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

Vemos su valor calculado de $3/8$ en la esquina superior izquierda. Por diagonalizing la matriz nos encontramos con que, por $n=2$, $$\mathbb{P}(X(m)=0)={1\over 4}+{1\over 4} 2^{\lfloor {(1-m) /2} \rfloor}.$$

De vuelta al caso general. Desde $3$ es invertible modulo $2^n$, la cadena de Markov es doblemente estocástico (su columna de sumas son todos iguales a 1) y por lo tanto tiene la distribución uniforme en $\mathbb{Z}_{2^n}$ como su único invariante de distribución. En el largo plazo, todos los estados son igualmente probables.

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