Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter Abbeel et al. sums up the procedure with an example which I present below, but with an explicit auxiliary variable (i.e. I added the variable $k$).
Consider a mixture of Gaussians where $i$ indexes the Gaussian from which the data $x$ is sampled; $p(x\vert i) = \mathcal{N}(x|\mu_i, \sigma^2_i)$. Assume, although possibly intractable, the true posterior $p(i \vert x, k)$ is available from which it is possible to sample and encode values $i$, where $k \sim p(k)$ is some auxiliary information used to sample $i$. Note that $k$ is used solely in the process of selecting $i$, therefore $k \rightarrow i \rightarrow x$ forms a Markov chain and $p(x \vert i, k) = p(x \vert i)$
Given a data point $x$ to compress, bits-back coding then proceeds to

Sample $k$ from $p(k)$
Sample $i$ from $p(i \vert x, k)$
Encode $i$ with a prior $p(i)$, resulting in code-length $\log_2(1/p(i))$
Encode $x$ with $p(x \vert i)$, resulting in code-length $\log_2(1/p(x \vert i))$
Although $i$ was encoded with $p(i)$, given that we know $p(i \vert x, k)$, it is possible to get &quot;bits back&quot; (hence the name) by reconstructing $k$.

My goal is to understand this concretely, since most tutorials I've found stop here and never actually give an example. Hence, consider the following:
Say there are 4 modes (Gaussians) of the mixture represented by $i \in \{0, 1, 2, 3\}$ and $k \in \{0, 1\}$. For a given point $x_o$, assume the given values for $p(i \vert x_o, k)$ and $p(i)$, as well as the code used to represent them from a binary alphabet, are the following:
$$\begin{array}{c|c|c} 
i &amp; p(i) &amp; \text{code-word} \\ \hline
0 &amp; 1/4  &amp; 00 \\
1 &amp; 1/4  &amp; 01 \\
2 &amp; 1/4  &amp; 10 \\
3 &amp; 1/4  &amp; 11 \\
\end{array}$$
$$\begin{array}{c|c|c} 
k &amp;i &amp; p(i \vert x_o, k) \\ \hline
0 &amp; 0 &amp; 1/2 \\
0 &amp; 1 &amp; 1/4 \\
0 &amp; 2 &amp; 1/4 \\
0 &amp; 3 &amp;   0 \\
1 &amp; 0 &amp;   0 \\
1 &amp; 1 &amp; 1/2 \\
1 &amp; 2 &amp; 1/4 \\
1 &amp; 3 &amp; 1/4 
\end{array}$$
I've conveniently made the symbols I.I.D. with dyadic probability mass functions, therefore making traditional Huffman Coding optimal.
On the receiving end, if $i=0$, surely $k=0$ since $p(i=0 | x_o, k=1) = 0$. Similarly, $i=3$ implies $k=1$. In general:
$$\begin{array}{c|c|c} 
i &amp; p(k=0 \vert x_o, i) &amp; p(k=1 \vert x_o, i) \\ \hline
0 &amp;   1 &amp;   0 \\
1 &amp; 1/3 &amp; 2/3 \\
2 &amp; 1/2 &amp; 1/2 \\
3 &amp; 0 &amp; 1 
\end{array}$$
Therefore, we are able to recover $k$ to some extent.
I have 2 questions:

is this the bits-back coding scheme or am I missing something?
For $i=0$ and $i=3$ we can recover $k$, but for $i \in \{1, 2\}$ all we have are the probabilities over $k$. How do we get these bits-back?
Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic).
To recover the original bits-back argument, we would need to pick a value $i_k$ for each possible value of $k$ and force $p(i=i_k \vert x, k)=1$ and 0 if $i \neq i_k$. Naturally, we would need to extend the support of $k$ to the same of $i$. In this particular example, $k \in \{0, 1, 2, 3\}$