1

Unequal Error Protection Querying Policies for the
Noisy 20 Questions Problem
Hye Won Chung, Brian M. Sadler, Lizhong Zheng and Alfred O. Hero

arXiv:1606.09233v2 [] 28 Sep 2017

Abstract
In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy
20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random
variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block
and the noisy responses are modeled as the output of a binary symmetric channel the 20 questions problem can be mapped to an
equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP
superposition coding is introduced whose estimation error decreases with an exponential rate of convergence that is significantly
better than that of the UEP repetition coding introduced by Variani et al., [2]. With the proposed querying strategy, the rate of
exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme where queries are sequentially
designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block
codes employing equal error protection.
Index Terms
Noisy 20 questions problem, estimation, superposition coding, unequal error protection, error exponents.

I. I NTRODUCTION
Consider a noisy 20 questions game between a player and an oracle. The objective of the player is to estimate the value
of a continuous target variable X ∼ unif[0, 1]. The player asks binary queries to the oracle who knows the value of X, and
receives a noisy version of the oracle’s correct answers transmitted through a binary symmetric channel with flipping probability
 ∈ (0, 1/2), denoted BSC(). The central question addressed here is: What is the optimal sequence of queries to estimate the
value of X with a minimum estimation error at a fixed number of querying? This general setup of noisy 20 questions game
and the optimal query design problem is of broad interest, arising in various areas, including active learning [3], [4], optimal
sensing [5] and experimental design [6], [7], with diverse applications. For example, a target localization problem in a sensor
network [8] can be modeled as a noisy 20 questions game where a player (agency) aims to locate a target by receiving query
responses from sensors probing the region of interest.
The problem of optimal query design for the noisy 20 questions game can be categorized into two main approaches, adaptive
vs. non-adaptive designs. In each approach, the sequence of queries is designed by a controller that may either use feedback
(adaptive 20 questions) or operate open-loop (non-adaptive 20 questions) to formulate the sequence of questions. For the
adaptive case, the controller uses noisy answers to previous questions to determine the next question posed to the oracle. For
the non-adaptive case, on the other hand, the controller designs the sequence of queries ahead of time without access to future
answers of the oracle. In general, the use of feedback in the adaptive design provides an information advantage, allowing a
better error rate of convergence, but at the cost of higher query design complexity and the need for a feedback channel.
Previous studies on optimal query design for the noisy 20 questions problem often sought to design queries that acquire
observations minimizing the posterior uncertainty of the target variable, where uncertainty was quantified by the Shannon
entropy [9], [3], [10], [8]. In these works, the utility of observation is quantified by the expected reduction of the entropy
due to the observation. This reduction is equivalent to the increase in mutual information between the target variable and the
observation. For adaptive sequential querying, greedy successive-entropy-minimization policies [10], [11] have been extensively
investigated.
When the mutual information is used to quantify the utility of observations, any two observations that increase the mutual
information by the same amount are considered to be equally valuable, regardless of how much these observations reduce
the estimation error. However, when estimation accuracy is important, queries maximizing the mutual information may not
generate observations of equal importance. For example, when the queries are on the coefficients in the dyadic expansion of
a target variable X the queries on the most significant bits (MSBs) of X may acquire more valuable observation than those
on the least significant bits (LSBs) in terms of reducing the estimation error. For estimation of X, the important question is
then how to design queries that acquire observations valuable in reducing the estimation error.
In the noisy 20 questions game, estimates on the coefficients in dyadic expansion of the target variable, which are based
on the received noisy answers from the oracle, may contain errors. Since the errors in MSBs cause a higher estimation error
Hye Won Chung (hwchung@kaist.ac.kr) is with the School of Electrical Engineering at KAIST in South Korea. Brian M. Sadler
(brian.m.sadler6.civ@mail.mil) is with the US Army Research Laboratory. Lizhong Zheng (lizhong@mit.edu) is with the EECS department at MIT. Alfred O.
Hero (hero@eecs.umich.edu) is with the EECS department at the University of Michigan. This research was supported in part by ARO grants W911NF-111-0391 and W911NF-15-1-0479. This research was presented in part at 2016 IEEE International Symposium on Information Theory in Barcelona, Spain [1].

2

than do the errors in LSBs, it is desirable to provide unequal error protection (UEP) for MSBs vs. LSBs in order to minimize
the estimation error with a limited number of queries. In this paper, we provide such a non-adaptive UEP querying policy for
state estimation in the context of the noisy 20 questions problem.
To develop the UEP querying policy, we exploit a close connection between the problem of optimal query design in
the noisy 20 questions problem and the problem of channel coding for the classical information-transmission problem. Let
M = {0, . . . , 2k − 1} denote the set of 2k possible states of the target variable X, determined by the first k bits in its
dyadic expansion. A binary query partitions the set M into two disjoint subsets, one of which contains the true state of
X. For adaptive sequential querying, the partition is random, depending on the answers to the previous queries, whereas for
non-adaptive querying, the partition is deterministic and determined in advance. By considering the true state of the target
variable as a message transmitted from the oracle to the player and the oracle’s binary answer bits to the sequence of queries
as a codeword, the query design problem can be mapped to an equivalent problem of channel coding. Specifically, the query
design problem reduces to the channel coding with feedback for the adaptive case and to channel coding without feedback for
the non-adaptive case.
The equivalence between the query design problem and the channel-coding problem allows us to apply UEP channel coding
methods to design a UEP querying strategy. Unequal-error-protection querying accounts for the fact that for estimation of a
target variable, the errors in the most significant bits (MSBs) are much more costly than the errors in the least significant bits
(LSBs).
One way to provide unequal error protection is repetition coding. In repetition coding, each bit is repeatedly transmitted
multiple times, the number of repetitions varying in accordance with the desired level of unequal error protection. Such a
UEP repetition coding approach to the noisy 20 questions√problem was considered in [2]. It was shown that the mean squared
error (MSE) of this approach decreases exponentially in N where N is the number of queries. The square root of N rate is
smaller than the linear in N exponential rate of decrease achievable by the bisection-based adaptive 20 questions strategy [12]
that corresponds to Horstein’s coding scheme for a BSC() with perfect feedback [13].
The main contribution of this paper is to provide a new non-adaptive querying strategy based on superposition coding [14]
that can provide UEP and achieve better MSE convergence rate than that of repetition coding in [2]. The proposed superposition
coding strategy provides UEP for two levels of priority, i.e., a strictly better error protection for MSBs than that√for LSBs. We
show that the proposed querying strategy achieves the MSE that decreases exponentially in N , as contrasted to N , matching
the error rate of the adaptive 20 questions strategy [12]. Furthermore, this strategy achieves a better scale factor in the MSE
exponent as compared to that of random block codes employing equal error protection.
The rest of this paper is organized as follows. In Section II, we review the mathematical formulation for the noisy 20 questions
problem for state estimation. We highlight the connection between the query design and the channel-coding problems both for
adaptive sequential querying and for non-adaptive block querying. For query performance measures, the MSE and quantized
MSE are considered. The different importances of the first k bits in the dyadic expansion of the target variable are quantified
for these performance measures. In Section III, we review three well-known querying policies including the adaptive bisection
policy [13], non-adaptive UEP repetition policy [2], and non-adaptive block querying based on random block coding [15].
In Sections III-A, we show that the bisection policy is the optimal myopic policy among successive-entropy-minimization
policies in reducing the minimum MSE of the target variable (Proposition 1). In Sections III-B and III-C, two representative
non-adaptive policies are presented and compared in terms of UEP property and coding gain. We introduce a new non-adaptive
querying policy based on superposition coding in Section IV. We show that block querying based on superposition coding
provides higher level of error protection for MSBs than for LSBs. We then establish that the proposed non-adaptive block
querying strategy achieves a better quantized-MSE exponent (Theorem 1) and better MSE exponent (Corollary 1) than those
of random block coding. In Section V, performance of all four policies discussed in this paper are compared by analyzing
the achievable error rates of convergence for the estimation errors in the number N of queries. Finally, conclusions and future
directions are discussed in Section VI. After presenting each result, we provide a brief discussion but defer the technical details
of the proofs to the Appendices.
A. Notations
Capital letters will represent random variables and lower case letters will represent specific realizations of those random variables. The statistical expectation operator and the indicator operator will be denoted by E[] and 1(), respectively.
For a continuous
R
random variable X distributed as p(x), x ∈ R, the differential entropy h(X) is defined as h(X) = −Pp(x) ln p(x)dx. For a
discrete random variable Y with distribution p(y), y ∈ Y, the entropy H(Y ) is defined as H(Y ) = − y∈Y p(y) ln p(y). The
entropy of a binary random variable Z distributed as Bernoulli(α), 0 ≤ α ≤ 1, is denoted HB (a) = −a ln a − (1 − a) ln(1 − a).
The Kullback-Leibler divergence between two Bernoulli distributions Bernoulli(α) and Bernoulli(β) is denoted DB (αkβ) :=
1−α
α ln α
β + (1 − α) ln 1−β . The star ∗ operator is defined as α ∗  := α(1 − ) + (1 − α) for α,  ∈ R.
The normalized Gilbert-Varshamov distance γGV (R) ∈ [0, 1/2] is the value γGV (R) that gives DB (γGV (R)k1/2) = R. The
−1
inverse of the normalized Gilbert-Varshamov distance is denoted γGV
(α) for 0 ≤ α ≤ 1/2.
N
Bold face z or z1 denotes the length-N binary sequence (z1 z2 . . . zN ) where zt is the t-th bit of z. The Hamming weight of z
is equal to the cardinality of the set {t ∈ [1 : N ] : zt = 1} and is denoted as wH (z). The bit-wise XOR operation is symbolized

3

encoder
w/ feedback
X

oracle

Qi
controller

Zi channel
pY |Z

Yi

player

X̂N

Y1i−1

<adaptive sequential querying>
encoder
w/o feedback
X

oracle

Z1N

QN
1

N
channel Y1
pY |Z

player

X̂N

controller
<non-adaptive block querying>
Fig. 1. Noisy 20 questions problem between an oracle and a player over a BSC(). The controller generates questions using feedback (adaptive sequential
querying) or operating open-loop (non-adaptive block querying). For adaptive sequential querying, the controller generates queries Qi adaptively based on
past answers Y1i−1 , whereas for non-adaptive block querying the controller generates a length-N block of queries QN
1 = (Q1 , . . . , QN ) non-adaptively as
a single block. The oracle gives the correct answer Zi to the query Qi about the target variable X. The player receives a noisy version Yi of the oracle’s
answer Zi transmitted through a BSC(), and outputs an estimate X̂N based on the received answers Y1N = (Y1 , . . . , YN ).

by ⊕ and the bit-wise XOR of two binary sequences x and y is written as x ⊕ y. The Hamming distance between two binary
sequences x and y is the cardinality of the set {t ∈ [1 : N ] : xt 6= yt } and is denoted as dH (x, y) := |{t ∈ [1 : N ] : xt 6= yt }|.
. ˙
. Nd
˙ N d denotes
˙ as follows: 1) aN =
We will use the notation =, ≤,
and ≥
e
denotes d = lim inf N →∞ lnNaN . 2) aN ≤e
ln aN
ln aN
Nd
˙
denotes d ≤ lim inf N →∞ N .
d ≥ lim inf N →∞ N . 3) aN ≥e
II. P ROBLEM S TATEMENT: N OISY 20 Q UESTIONS FOR E STIMATION OF A TARGET VARIABLE
We consider an estimation problem for a target variable in the context of a noisy 20 questions game between a player and an
oracle who communicate over a channel. The objective of the player is to estimate the value of a target variable, X ∼ unif[0, 1]
by posing a sequence of binary queries to the oracle and receiving noisy answers. To estimate X, the player asks the oracle
whether X is located within some sub-region Q ⊂ [0, 1], which may be connected or non-connected, and receives a noisy
binary answer Y ∈ {0, 1} based on the correct answer Z(X) = 1(X ∈ Q) with error probability  ∈ [0, 1/2). The oracle
always provides a correct binary answer Z(X) = 1(X ∈ Q) to the player’s query. The channel through which the oracle’s
binary answer is transmitted to the player is modeled as a binary symmetric channel, BSC().
The player asks a sequence of N questions in the form of a sequence of querying regions (Q1 , Q2 , . . . , QN ). The oracle
provides correct answers (Z1 , Z2 , . . . , ZN ) to the queries about the target variable X, and the player receives a noisy version
(Y1 , Y2 , . . . YN ) of the oracle’s answers transmitted through N uses of the BSC(). Based on these answers, the player calculates
an estimate X̂N of X. For a given cost function c(x, x̂N ) between the true value x and the estimate x̂N , the player’s goal
is to find the optimal sequence of querying regions (Q1 , Q2 , . . . , QN ) and the estimator X̂N (Y1 , . . . , YN ) that minimize the
expected cost function. That is, the player aims to achieve
min
(Q1 ,Q2 ,...,QN ),X̂N (·)

E[c(X, X̂N )]

(1)

where the expectation is taken over the joint distribution of (X, Y1 , Y2 , . . . , YN ).
Note that the joint distribution of (X, Y1 , Y2 , . . . , YN ) depends on the querying regions (Q1 , Q2 , . . . , QN ).
The sequence of questions is designed by a controller that may either use feedback (adaptive sequential querying) or operate
open-loop (non-adaptive block querying) as depicted in Fig. 1. Depending on whether the questions are designed with or
without the benefit of feedback, the optimal querying strategy and the corresponding performance can vary. In the next section,
we highlight differences between adaptive sequential querying and non-adaptive block querying and show a connection between
the noisy 20 questions problem and the channel-coding problem.
A. Adaptive vs. Non-adaptive Querying Strategies and Associated Channel-Coding Problems
In the adaptive case, the i-th querying region Qi can be updated based on past answers Y1i−1 := (Y1 , . . . , Yi−1 ) to previous
queries. For this case, the controller uses the updated posterior distribution p(x|y1i−1 ) of X to design the next query, i.e., the

4

region Qi . For example, consider the case when the i-th querying region Qi is designed to equalize the probabilities of X
belonging to Qi and of X not belonging to Qi , respectively, for given collected answers Y1i−1 = y1i−1 :
Pr(X ∈ Qi |Y1i−1 = y1i−1 ) = Pr(X ∈
/ Qi |Y1i−1 = y1i−1 ) = 1/2.

(2)

Since the channel input (the oracle’s binary answer) Zi (X) is an indicator random variable of the event {X ∈ Qi }, for the
choice of Qi satisfying (2) the corresponding channel input Zi follows the distribution
Pr(Zi = 0|Y1i−1 = y1i−1 ) = Pr(Zi = 1|Y1i−1 = y1i−1 ) = 1/2,

(3)

which is an optimal input distribution for the BSC() in maximizing the mutual information. Specifically, the corresponding
mutual information between the oracle’s i-th binary answer Zi and the channel output Yi given previous answers Y1i−1 = y1i−1
is
I(Zi ; Yi |Y1i−1 = y1i−1 ) = C
(4)
where
C := ln 2 − (− ln  − (1 − ) ln(1 − )).

(5)

To summarize, in adaptive sequential querying the channel input Zi (X) = 1(X ∈ Qi ) depends on the previous channel outputs
Y1i−1 , since the querying region Qi depends on Y1i−1 . As depicted in the upper figure of Fig. 1, the combined operation of
the controller and the oracle can be thought of as an encoder in a feedback communication system. Therefore, there is a
one-to-one mapping between designing an adaptive sequential-querying strategy and designing a sequential channel encoder
with noiseless feedback.
In the non-adaptive case the querying regions QN
1 := (Q1 , . . . , QN ) are specified in advance, before observing any of the
answers from the oracle. Assume that the controller generates queries on the first k bits in the dyadic expansion of X ≈
0.B1 . . . Bk , Bi ∈ {0, 1} for i = 1, . . . , k. The resolution
Pk parameter k may depend on the number of queries N . Discovering
(B1 , . . . , Bk ) is equivalent to finding the index M = i=1 Bi 2k−i ∈ {0, . . . , 2k −1} of the interval IM := [M 2−k , (M +1)2−k )
that contains X. Here the domain [0, 1] of X is uniformly quantized into 2k disjoint sub-intervals {I0 , . . . , I2k −1 } of length
2−k . If the oracle’s answer Zi to the question Qi can be transmitted to the player without noise, i.e.,  = 0, then by querying
each coefficient of the dyadic expansion of X from the MSB to the LSB, the player can discover the N most significant bits
(B1 , . . . , BN ) of X without error. However, in the case of a noisy channel, the player needs to ask redundant questions in
order to accurately estimate the k most significant bits of X for some k < N .
Non-adaptive block querying can be mapped to an equivalent problem of length-N block channel coding over a BSC().
The rate of the block code is defined as R = (k ln 2)/N (nats/channel use) for the resolution of k bits of X. Designing a
block of questions (Q1 , . . . , QN ) to discover the index M of the sub-interval IM containing X can be thought of as designing
a length-N and rate-R block code, or, more specifically, defining an encoding map f : {0, . . . , 2k − 1} → {0, 1}N , to reliably
transmit one of the 2k messages through N uses of the channel with channel coding rate R = (k ln 2)/N .
A block of questions specifies the encoding map f : {1, . . . , 2k } → {0, 1}N , and vice versa. The one-to-one mapping
between the two is described as follows. Define sub-intervals Im := [m2−k , (m + 1)2−k ) for m ∈ {0, . . . , 2k − 1}. We restrict
the querying region Qi to be the union of a subset of the quantized intervals {I0 , . . . , I2k −1 }. In other words, we fix the
(m)
(m)
(m)
maximum resolution of the querying interval as 2−k . Let zi
denote the i-th bit of the codeword f (m) = (z1 , . . . , zN )
(m)
for a message m given an encoding map f : {0, . . . , 2k − 1} → {0, 1}N . Note that the bit zi is the oracle’s binary answer
(m)
to the query Qi indicating whether x ∈ Qi when x ∈ Im . Therefore, the bit zi equals 1 if and only if Im ⊂ Qi , i.e.,
(m)

zi

= 1(Im ⊂ Qi ).

(6)

On the other hand, when the encoding map f (·) is specified, the associated i-th querying region Qi becomes the union of the
(m0 )
sub-intervals {Im0 } for message m0 ’s such that the i-th answer bit zi
equals 1, i.e.,
[
Qi =
Im0 .
(7)
(m0 )

{m0 :zi

=1}

Given the block of questions (Q1 , . . . , QN ), for an index m such that x ∈ Im the oracle transmits the corresponding length-N
binary answer bits f (m) through N uses of the BSC(), and the player tries to decode the message m given a noisy version
of the codeword.
Thus both adaptive sequential querying and non-adaptive block querying can be mapped to associated channel-coding
problems in information transmission through a noisy channel, with and without feedback, respectively. However, different
from information-transmission problems where the goal is to achieve reliable communications at some positive rate 0 < R ≤ C
for capacity C of the channel, the objective of the noisy 20 questions problem for state estimation is to minimize estimation
error E[c(X, X̂N )]. In the next section, we introduce two different types of estimation errors that will be considered in this
paper and discuss what kind of properties are desired for channel coding to minimize these estimation errors.

5

X̂N | > 2

1(|X

k

/2)

|X

X̂N |2

cq (X, X̂N )

X

X̂N

Fig. 2. Plot of three different cost functions: |X − X̂N |2 for the MSE, cq (X, X̂N ) for the quantized MSE and 1(M̂ 6= M ) = 1(|X − X̂N | > 2−k /2)
for the block-decoding-error probability when the resolution parameter k = 3.

B. Estimation Errors: Mean Squared Error and Quantized Mean Squared Error
We consider two types of estimation errors. The first is the mean squared error (MSE) E[|X − X̂N |2 ] where X̂N is the
estimate of X after N queries. The second is the quantized MSE E[cq (X, X̂N )] where the quantized cost function cq (X, X̂N )
with 2k levels is a stepwise function defined as
cq (X, X̂N ) = (d2−k )2 , when
2−k
2−k
< |X − X̂N | ≤ d2−k +
,
2
2
for d ∈ {0, . . . , 2k − 1},

d2−k −

(8)

for X, X̂N ∈ [0, 1]. We consider this cost function when the objective of the problem is to estimate the value of X up to the
first k bits (B1 , . . . , Bk ) in the dyadic expansion of X.
Let (B̂1 , . . . , B̂k ) denote the estimate of (B1 , . . . , Bk ) and let
M̂ =

k
X

B̂i 2k−i

(9)

i=1

denote the estimate of the message M =
as

Pk

i=1

Bi 2k−i . We define the decoding-error distance d(M, M̂ ) between M and M̂

d(M, M̂ ) := |M − M̂ | =

k
X
i=1

(Bi − B̂i )2k−i .

(10)

By defining the finite-resolution estimator X̂N,finite as
X̂N,finite := M̂ 2−k + 2−k /2,

(11)

the quantized MSE cq (X, X̂N ) with X̂N = X̂N,finite can be written in terms of the decoding-error distance as
cq (X, X̂N,finite ) = 2−2k (d(M, M̂ ))2 .

(12)

Note that the quantized MSE equals 0 when the player correctly decodes the message M . The error increases proportionally
to the square of the decoding-error distance. On the other hand, in information-transmission problems where the cost function
is 1(M̂ 6= M ), decoding error is claimed when M̂ 6= M , i.e., when d(M, M̂ ) 6= 0, and the cost of incorrect decoding
is the same for every M̂ 6= M regardless of the decoding-error distance d(M, M̂ ). This difference in the cost functions
makes the desired channel-coding strategy for state-estimation problem different from that of the information-transmission
problem. Fig. 2 shows the three different cost functions, |X − X̂N |2 for the MSE, cq (X, X̂N ) for the quantized MSE and
1(M̂ 6= M ) = 1(|X − X̂N | > 2−k /2) for the block-decoding-error probability when the resolution parameter k = 3.
The quantized MSE E[cq (X, X̂N )] approximates the MSE E[|X − X̂N |2 ]. In particular, with the finite-resolution estimator
X̂N = X̂N,finite , the MSE E[|X − X̂N,finite |2 ] can be written as a sum of the quantized MSE E[cq (X, X̂N,finite )] and the error
from finite resolution,
E[|X − X̂N,finite |2 ] = E[cq (X, X̂N,finite )] + c2−2k ,
(13)

6

for some constant 0 < c ≤ 1/4. This can be shown by writing the difference between the two expected errors as a sum of
errors conditioned on the decoding-error distance d(M, M̂ ) = d for d ∈ {0, . . . , 2k − 1},
E[|X − X̂N,finite |2 ] − E[cq (X, X̂N,finite )]
=

k
2X
−1 

Pr(d(M, M̂ ) = d)E

d=0

h

|X − X̂N,finite |2 − d2 2−2k



d(M, M̂ ) = d

i

.

(14)

For d = 0, the conditional expectation in (14) is bounded above by 2−2k /4. Given that X ∼ unif[0, 1], conditioned on
d(M, M̂ ) = d for d ∈ {1, . . . , 2k − 1}, |X − X̂N,finite | is uniformly distributed over [d2−k − 2−k /2, d2−k + 2−k /2). Thus
i

h
1 −2k
E |X − X̂N,finite |2 − d2 2−2k d(M, M̂ ) = d =
2
.
(15)
12
Therefore, the difference between the MSE and quantized MSE is bounded above by a scale factor of 2−2k as in (13).
Consider the case when the resolution k bits of the estimator X̂N,finite increases linearly in the number of queries N as
∗
∗
k = N R/ ln 2 for some fixed positive rate R > 0. Let EMSE,policy
(R) and Eq,policy
(R) denote the best achievable exponentially
decreasing rates of the MSE and of the quantized MSE in N at a fixed rate R, respectively, for some policy, i.e.,
− ln E[|X − X̂N,finite |2 ]
,
N →∞
N
− ln E[cq (X, X̂N,finite )]
∗
.
Eq,policy
(R) := lim inf
N →∞
N

∗
EMSE,policy
(R) := lim inf

(16)
(17)

Then the equality in (13) implies that for large N , the exponential convergence rate of the MSE E[|X − X̂N,finite |2 ] in N is
dominated by the minimum between the exponentially decreasing rate of the quantized MSE and 2R, i.e.,
∗
∗
EMSE,policy
(R) = min{Eq,policy
(R), 2R}.

(18)

∗
Eq,policy
(R)

For sufficiently large R > 0 where
≤ 2R, the MSE exponent is identical to the quantized-MSE exponent. In this
∗
paper, we analyze performance of a querying policy by first calculating the best achievable quantized-MSE exponent Eq,policy
(R)
at a fixed rate R > 0 for querying resolution of k = N R/ ln 2 bits. Once the quantized-MSE exponent is calculated for every
R > 0, by using (18) we calculate the resulting MSE exponent.
We next show how the MSE and the quantized MSE can be bounded below and above in terms of the block-decoding-error
events {M̂ 6= M } or bit-decoding-error events {B̂i 6= Bi }, i ∈ {1, . . . , k}. The block-decoding error {M̂ 6= M } occurs when
any of Bi ’s are incorrectly decoded. For a given cost function c(x, x̂N ), the expected estimation error can be written in terms
of block-decoding events {M̂ = M } and {M̂ 6= M } as
E[c(X, X̂N )] = Pr(M̂ 6= M )E[c(X, X̂N ) M̂ 6= M ] + Pr(M̂ = M )E[c(X, X̂N ) M̂ = M ].

(19)

With the finite-resolution estimator X̂N,finite = M̂ e−N R + e−N R /2, the MSE and the quantized MSE can be bounded above
as
E[|X − X̂N,finite |2 ] ≤ Pr(M̂ 6= M ) + (e−N R /2)2 ,

E[cq (X, X̂N,finite )] ≤ Pr(M̂ 6= M ),

(20)
(21)

by using E[|X − X̂N,finite |2 |M̂ = M ] ≤ (e−N R /2)2 and E[cq (X, X̂N,finite )|M̂ = M ] = 0, respectively. The achievable exponent
of the MSE in (20) is determined by trade-offs between the exponentially decreasing rate of Pr(M̂ 6= M ) at a fixed rate R and
the exponent 2R. On the other hand, in (21), the achievable exponent of the quantized MSE is determined by the exponentially
decreasing rate of Pr(M̂ 6= M ) in N at a fixed rate R.
Tighter bounds on the two estimation errors can be found by expanding the errors in terms of the bit-decoding events. For
a cost function c(x, x̂N ), the expected cost can be written as
E[c(X, X̂N )] =

k 
X
i=1

+


Pr(B̂i 6= Bi , B̂1i−1 = B1i−1 )E[c(X, X̂N ) B̂i 6= Bi , B̂1i−1 = B1i−1 ]

Pr(B̂1k

=

B1k )E[c(X, X̂N )

B̂1k

=

(22)

B1k ]

where the number of information bits is k = N R/ ln 2. Note that conditioned on the event {B̂i 6= Bi , B̂1i−1 = B1i−1 }, both
the cost functions |X − X̂N,finite |2 and cq (X, X̂N,finite ) are bounded above by 2−2(i−1) . Thus, we have
E[|X − X̂N,finite |2 B̂i 6= Bi , B̂1i−1 = B1i−1 ] ≤ 2−2(i−1) ,
E[cq (X, X̂N,finite ) B̂i 6= Bi , B̂1i−1 = B1i−1 ] ≤ 2−2(i−1) .

(23)

7

From these bounds and (22), we can upper bound the MSE as,
E[|X − X̂N,finite |2 ] ≤

k
X
i=1

Pr(B̂i 6= Bi )2−2(i−1) + 2−2k ,

(24)

and the quantized MSE as
E[cq (X, X̂N,finite )] ≤

k
X
i=1

Pr(B̂i 6= Bi )2−2(i−1) .

(25)

These bounds show how differently each bit-error probability contributes to the estimation errors. In the upper bounds on the
MSE (24) and on the quantized MSE (25), we can see that the weights on the bit-error probabilities decrease exponentially in
i as the bit position i increases corresponding to lower significance. In order to minimize the upper bounds on the MSE and on
the quantized MSE for a fixed number of querying N , we need to design a querying strategy (or the associated channel coding)
that can provide unequal error protection depending on the bit positions. This property differentiates a good channel-coding
strategy for state estimation from that for information transmission. In classical information-transmission problems where the
cost function is 1(M̂ 6= M ), any bit error event {B̂i 6= Bi } results in the same cost. Therefore, the optimal coding strategy to
minimize the expected cost function E[1(M̂ 6= M )], which equals the block-decoding-error probability Pr(M̂ 6= M ), provides
equal error protection for all the information bits. In the state-estimation problem, on the other hand, the optimal coding
strategy should provide unequal error protection on information bits {B1 , . . . , Bk } depending on the bit positions.
III. R EVIEW OF T HREE D IFFERENT Q UERYING S TRATEGIES
In this section, we review three well-known querying policies including the adaptive bisection policy [13], the nonadaptive UEP repetition policy [2], and the non-adaptive block-querying policy based on random block coding [15] in
Sections III-A, III-B, and III-C, respectively. The performance of these policies are analyzed by the best achievable quantizedMSE exponent defined in (17) with the finite-resolution estimator X̂N,finite (11).
A. Adaptive Bisection Policy
For adaptive sequential querying, greedy successive entropy minimization of a target variable is often proposed as a way to
design a querying strategy for estimation of the target variable [8], [10]. Successive-entropy-minimization strategies select a
binary query that maximally reduces the remaining uncertainty of the target variable at each round. This can be accomplished
by choosing a querying region Qi that balances the probability of the event {X ∈ Qi } and the probability of the event
{X ∈
/ Qi }, given past answers y1i−1 , i.e.,
(26)
Pr(X ∈ Qi |Y1i−1 = y1i−1 ) = Pr(X ∈
/ Qi |Y1i−1 = y1i−1 ) = 1/2.
R
The uncertainty of the target variable is quantified by the differential entropy h(X) := − p(x) ln p(x)dx where X ∼ p(x),
and the expected reduction of the uncertainty by the i-th querying equals
h(X|Y1i−1 = y1i−1 ) − h(X|Yi , Y1i−1 = y1i−1 )

(27)

where Yi is the noisy observation of the oracle’s answer Zi = 1(X ∈ Qi ) transmitted through a BSC(). For Qi satisfying (26),
the expected reduction of the uncertainty in (27) is equal to C := maxYi I(X; Yi |Y1i−1 = y1i−1 ) = HB (1/2) − HB () where
I(X; Yi |Y1i−1 = y1i−1 ) is the conditional mutual information between X and Yi given Y1i−1 = y1i−1 . After N rounds of
querying, successive-entropy-minimization strategies reduce the entropy of X by N C. From the elementary bound
h(X) − h(X|Y1N ) ≤ max I(X; Y N ) = N C,
YN

(28)

we can see that the successive-entropy-minimization policy achieves the maximum possible entropy reduction of X for N uses
of the BSC().
The bisection policy, which is also called Horstein’s coding scheme [13], is one example of the successive-entropyminimization policies. This policy asks whether X lies to the left or right of the median of the updated posterior distribution at
each round. The left figure of Fig. 3 illustrates the bisection policy for the first two rounds of querying. At the first round, the
value of X is uniformly distributed over [0, 1] and the median of the prior distribution equals 1/2. Thus, the player asks whether
X belongs to the right half of the region of interest [0, 1] by choosing Q1 = [1/2, 1], i.e., the player tries to extract the most
significant bit of X. Given the observed answer Y1 ∈ {0, 1}, the player updates the posterior distribution p(x|y1 ) of X, and
then chooses Q2 ⊂ [0, 1] that bisects the posterior distribution such that Pr(X ∈ Q2 |Y1 = y1 ) = 1/2, i.e., it queries whether
X lies to the right of the median of the posterior distribution p(x|y1 ). Depending on the answer Y1 to the previous query,
the updated posterior distribution p(x|y1 ) and the median of the distribution change, so that the second querying region Q2
changes as a function of the answer to the previous query. At each round, the player keeps updating the posterior distribution

8

Bisection policy
(adaptive)

Dyadic policy
(non-adaptive)

p(x)

p(x)

1

0
Y1 = 0

x
Y1 = 1

p(x|y1 )

p(x|y1 )

1

0

0

1

0
Y1 = 0

Y1 = 1

p(x|y1 )

1

0

x

p(x|y1 )

1

0

1

Fig. 3. Illustration of two successive-entropy-minimization policies, adaptive bisection policy and non-adaptive dyadic policy, for the first two rounds. The
shaded regions correspond to the posterior distribution over the querying region Qi at the i-th round. The bisection policy designs Qi to be right region of
the median of the posterior distribution, while the dyadic policy assigns Qi to be the region that corresponds to the i-th bit Bi of the binary expansion of
X being equal to 1. The querying region Qi of the bisection policy changes depending on the received answers Y1i−1 of the previous queries, while that of
the dyadic policy does not change on Y1i−1 . For both the querying strategies, the shaded areas take 1/2 of the posterior distribution.

p(x|y1i−1 ) of the target variable given collected answers and designs the querying region Qi to be right of the median of the
updated p(x|y1i−1 ).
The bisection policy is known to work well in practice, but there are few available theoretical guarantees for the performance of this policy. Here we demonstrate that among successive-entropy-minimization policies satisfying (26) for every
i ∈ {1, . . . , N } the bisection policy maximally reduces the conditional variance of X at each round. More specially, we show
that the bisection policy chooses Qi that maximizes the predicted variance reduction at the i-th round given the answers y1i−1
of the previous rounds, i.e.,

(29)
max Var(X|Y1i−1 = y1i−1 ) − E[Var(X|Yi , Y1i−1 = y1i−1 )] .
Qi

The predicted variance reduction depends on the choice of the querying region Qi since the posterior distribution p(x|yi , y1i−1 )
is a function of Qi . The minimum-mean-square-error (MMSE) estimator X̂N,MMSE = E[X|Y1N = y1N ] minimizes the MSE
and makes it equal to the conditional variance of X given Y1N ,
min E[|X − X̂N |2 ] = E[(X − X̂N,MMSE )2 ] = E[Var(X|Y1N )].

(30)

X̂N

Therefore, the bisection policy, which maximizes the predicted one-step variance reduction in (29), is the optimal myopic
(greedy) policy in reducing the MSE at each round given the previous answers. But this does not necessarily mean that the
bisection policy is the globally optimal policy in minimizing the MSE for a fixed number of querying.
Proposition 1: Among successive-entropy-minimization policies, which choose the i-th querying region Qi satisfying Pr(X ∈
Qi |Y1i−1 = y1i−1 ) = Pr(X ∈
/ Qi |Y1i−1 = y1i−1 ) = 1/2 given previous answers y1i−1 , the bisection policy maximizes the
predicted one-step variance reduction (29) at each round.
Proof: Appendix A
Remark 1: In the proof of Proposition 1 in Appendix A, we show that the predicted variance reduction of X due to the i-th
query Qi is a function of not only {Pr(X ∈ Qi |Y1i−1 = y1i−1 ), Pr(X ∈
/ Qi |Y1i−1 = y1i−1 )} but also {E[X|X ∈ Qi , Y1i−1 =
i−1
i−1
i−1
y1 ], E[X|X ∈
/ Qi , Y1
= y1 ]}. Successive-entropy-minimization policies select Qi that makes Pr(X ∈ Qi |Y1i−1 =
i−1
y1 ) = 1/2 but do not care about the corresponding conditional expectations {E[X|X ∈ Qi , Y1i−1 = y1i−1 ], E[X|X ∈
/
Qi , Y1i−1 = y1i−1 ]}, which also governs the conditional variance of X. What we show in Proposition 1 is that the choice
of the querying region Qi from the bisection policy results in the selection of {E[X|X ∈ Qi , Y1i−1 = y1i−1 ], E[X|X ∈
/
Qi , Y1i−1 = y1i−1 ]} that maximizes the predicted variance reduction among all the possible querying regions Qi satisfying
Pr(X ∈ Qi |Y1i−1 = y1i−1 ) = 1/2. More discussions on successive-entropy-minimization policies and the proof of Proposition 1
are provided in Appendix A.
In this paper, we are particularly interested in the error rates of convergence achievable with the bisection policy. Even
though the error rate for the bisection policy is very hard to analyze and not known in general, a slight modification of
the bisection policy proposed by Burnashev and Zigangirov in [12], and called the BZ algorithm, is analyzable. The BZ
algorithm works very similarly to the bisection policy, except that the boundary of the querying regions is not equal to
the median of the posterior distribution. Rather, the BZ boundary is chosen among a set of uniformly quantized thresholds
T = {0, 2−k , 2(2−k ), . . . , 2k (2−k )} with resolution 2−k . More specifically, the threshold is chosen by sampling between the
two points in the set T that are closest to the median of the posterior distribution. Let M denote the true index of the interval

9

IM = [M 2−k , (M + 1)2−k ) where the target variable X belongs. After N rounds of querying with the BZ algorithm, the
controller finds the sub-interval IM̂ = [M̂ 2−k , (M̂ + 1)2−k ) where the posterior probability of {X ∈ IM̂ } is maximized and
defines such a M̂ as the estimate of M . In [12], [5], it is shown that the probability of the error event {M̂ 6= M } with the
BZ algorithm decreases exponentially in N as



√
−N − ln 1/2+ (1−)
Pr(M̂ 6= M ) ≤ 2k e
(31)
for a fixed k. When we consider a sequence of BZ algorithms with different resolutions {2−k } where k scales as k = RN/ ln 2
for a fixed rate R > 0, the probability of decoding error {M̂ 6= M } is bounded above by




√
−N − ln 1/2+ (1−) −R
Pr(M̂ 6= M ) ≤ e
.
(32)
Since the quantized MSE can be bounded above by the block-decoding-error probability as shown in (21), the quantized-MSE
exponent defined in (17) is bounded below by the exponent on the right hand side of (32).
Lemma 1 (Quantized-MSE exponent with BZ algorithm): The best achievable quantized-MSE exponent with the BZ algorithm,
∗
denoted Eq,BZ
(R), is bounded below as


p
∗
(33)
Eq,BZ
(R) ≥ Eq,BZ (R) := − ln 1/2 + (1 − ) − R
when the resolution of the querying region scales as k = N R/ ln 2 bits for a fixed rate R > 0.
B. Non-Adaptive Unequal-Error-Protection Repetition Querying
Different from the adaptive policy where the updated posterior distribution p(x|y1i−1 ) is available to the controller for the
design of the i-th querying region Qi , for the non-adaptive policy a block of queries is determined independently of previous
answers from the oracle. Our objective is to design a block of queries to estimate X up to the first k bits in the binary
expansion of X ≈ 0.B1 B2 . . . Bk with the minimum estimation error E[c(X, X̂N )] for a given cost function c(X, X̂N ).
We first point out that even for the non-adaptive case, there exists a block of queries (Q1 , . . . , QN ) that does not depend
on Y1N but still meets the condition (26) of successive-entropy-minimization policies for every Y1N ∈ {0, 1}N . Such a policy
is the dyadic policy [10] and works as follows: The dyadic policy queries the coefficients in the dyadic expansion of X ≈
0.B1 B2 . . . BN from B1 to BN one at a time over N rounds of querying. The right figure of Fig. 3 illustrates the procedure
of the dyadic policy. At the first round, as does the bisection policy, the dyadic policy queries the MSB B1 . At the second
round, regardless of Y1 ∈ {0, 1} it queries the second MSB B2 by choosing Q2 to be Q2 = [1/4, 2/4] ∪ [3/4, 1], which is the
region of X where B2 = 1. The player continues the procedure of asking about Bi at the i-th round for i = 1, . . . , N . Since
the prior distribution of X is uniform over [0, 1], the quantized bits {Bi } are i.i.d. with Bernoulli(1/2). Moreover, since the
channel outputs Y1i−1 ∈ {0, 1}i−1 contain information only about B1i−1 but not about Bi , the events {Bi = 1} and {Bi = 0}
are independent of Y1i−1 . Therefore, the dyadic policy satisfies the condition (26) for every y1i−1 ∈ {0, 1}i−1 and achieves the
maximum reduction (28) of the conditional entropy.
Even though the dyadic policy maximally reduces the uncertainty of X measured by the entropy, this policy fails to make
the estimation error converge to 0 even when N → ∞. This is because, in the BSC(), with  ∈ (0, 1/2) probability the player
receives an incorrect value for the information bit Bi . Since each bit Bi is queried only once by the dyadic policy, if the player
receives an incorrect answer for some bit Bi there is no way to recover from this error. Therefore, the estimation error of the
dyadic policy does not converge to 0.
To correctly estimate (B1 , . . . , Bk ) through N uses of the noisy BSC(), the player needs to design a block of queries
(Q1 , . . . , QN ) with some redundancy, or equivalently design a block code with encoding map f : {0, . . . , 2k − 1} → {0, 1}N
to guarantee a reliable transmission of the information bits (B1 , . . . , Bk ). As pointed out earlier, the decoding error of each Bi
has different effect on the estimation error. The different importances of Bi ’s can be quantified by the different weights on the
bit error probabilities Pr(B̂i 6= Bi ) in the upper bounds (24) and (25) on the MSE and on the quantized MSE, respectively.
For non-adaptive block querying, in order to minimize the estimation error with a limited number N of queries it is desirable
to provide different levels of error protection.
One way to provide unequal error protection is to repeat the query on the information bits multiple times, the number
of repetitions varying in accordance with the desired level of error protection. Such a UEP repetition coding approach was
considered in [2]. For this policy, the controller queries each information bit Bi in the dyadic expansion of X ≈ 0.B1 . . . Bk
repeatedly Ni times P
and the oracle sends the uncoded bit Bi repeatedly by Ni uses of the BSC(). The total number of channel
k
uses is restricted to i=1 Ni = N where k is the resolution of the quantification of X.
Note that this repetition-coding policy cannot achieve the maximum entropy reduction (28) of the target variable X, which
is achievable only when the player keeps asking the most informative query at each round. The repeated queries on Bi
successively reduce the uncertainty of Bi , and the bit error probability of Bi decreases exponentially in the number of repeated
queries, Ni . The minimum bit-error probability of Bi is achievable with a simple majority-voting algorithm, which claims the

10

estimate B̂i to be the more frequently received binary value at the Ni channel outputs. This simple algorithm is equivalent to
maximum-likelihood (ML) decoding for Bi .
Lemma 2: When the oracle sends a binary bit Bi ∼ Bernoulli(1/2) repeatedly Ni (≥ 1) times through a BSC(), the best
achievable bit-error probability with the majority-voting algorithm decreases exponentially in Ni as
e−1/(3Ni ) −Ni DB (1/2k)
√
e
≤ Pr(B̂i 6= Bi ) ≤ e−Ni DB (1/2k) .
2πNi

(34)

Proof: Appendix B.
By assigning different numbers of repetitions (N1 , N2 , . . . Nk ) for each information bit Bi we can provide unequal error
protection for the information bits. The remaining issue is the optimal solution for the number of repetitions (N1 , N2 , . . . , Nk )
that minimize the estimation error where k is the total number of queried information bits. These should be selected to minimize
the upper bound on the MSE E[|X − X̂N,finite |2 ] in (24) or the upper bound on the quantized MSE E[cq (X, X̂N )] in (25). Since
the weight 2−2(i−1) on Pr(B̂i 6= Bi ) decreases exponentially in i and Pr(B̂i 6= Bi ) decreases exponentially in Ni as shown
in (34), the optimal Ni∗Pthat minimizes the upper bounds should decrease linearly in i from MSB to LSB. This condition
k
then implies that N = i=1 Ni∗ = O(k 2 ). Therefore, the
√ number of information bits that are queried by the optimal UEP
repetition coding increases in N on the order of k = O( N ), and the√corresponding rate R = k/N goes to 0 as N → ∞.
The resulting MSE and quantized MSE decrease exponentially only as N .
By using the similar arguments, in [2] it was shown that
√ with the UEP repetition coding, the MSE minimized over all
choices of (N1 , . . . , Nk ) and k decreases exponentially in N but not faster than that
c1 e−c2

√

N

≤

min

(N1 ,...,Nk ),k

E[|X − X̂N,finite |2 ] ≤ c3 e−c4

√

N

,

(35)

for some positive constants c1 , c2 , c3 , c4 > 0. Therefore, compared to the adaptive bisection-based policy, whose estimation
error decreases exponentially in N , the UEP repetition coding achieves a quadratically worse exponential rate of converenge.
Moreover, the UEP repetition coding gives a MSE exponent (16) and quantized-MSE exponent (17) that is equal to zero at
any positive rate R > 0 where k = N R/ ln 2 bits.
Lemma 3: With the UEP repetition coding, the best achievable MSE exponent and the quantized-MSE exponent are
∗
∗
EMSE,repetition
(R) = Eq,repetition
(R) = 0

(36)

at any positive rate R > 0.
For non-adaptive block querying, in order to improve the error rates of convergence we need to use more sophisticated
codes that can efficiently encode k = O(N ) information bits in a length-N codeword while guaranteeing reliable transmission
of those k = O(N ) bits. For this purpose, we consider a non-adaptive block querying based on random block coding in the
following section.
C. Non-Adaptive Block Querying Based on Random Block Coding
In this section, we introduce a non-adaptive block-querying strategy based on random block coding [15]. The encoding
map f : {0, . . . , eN R − 1} → {0, 1}N of the random block codes of rate R independently generates length-N codewords
(m)
(m)
z(m) = (z1 , . . . , zN ) := f (m) each of which is composed of i.i.d. symbols of Bernoulli(1/2) distribution. The player and
the oracle agree on the encoding map, which in turn specifies a block of queries (Q1 , . . . , QN ). Fig. 4 illustrates the one-to-one
mapping between the codebook and the block of queries. For a given block code with codewords {z(m) }, m ∈ {0, . . . , eN R −1},
where the querying resolution is k = N R/ ln 2 bits, the corresponding i-th querying region Qi becomes the union of the intervals
(m0 )
Im0 = [m0 2−k , (m0 + 1)2−k ) of m0 ’s such that the i-th answer bit zi
= 1.
When the value of the target variable X belongs to the sub-interval Im , the oracle transmits the length-N answer bits
(m)
(m)
z(m) = (z1 , . . . , zN ) to the block of queries (Q1 , . . . , QN ) by N uses of the BSC(). The length-N channel-output
sequence that the player receives is denoted by y = z(m) ⊕ n where n is the noise sequence composed of i.i.d. symbols
with Bernoulli() distribution. Given the channel-output sequence y, the player finds an estimate m̂ of m that maximizes the
likelihood (ML decoder)
m̂ = arg max pN (y|z(m) )
(37)
m
N

QN

where p (y|z) = i=1 pY |Z (yi |zi ) and pY |Z (y|z) is the transition probability of the BSC(). Define the set of y’s that
are mapped to the message m0 by the ML decoder as Ym0 for m0 ∈ {0, . . . , eN R − 1}. Since the message M is uniformly
distributed over {0, . . . , eN R − 1} for X ∼ unif[0, 1], the average decoding-error probability is
Pr(M̂ 6= M ) =

R
eN
X−1

m=0

e−N R

X
y∈Y
/ m

pN (y|z(m) ).

(38)

11

N
0
1
1
0
0
0
1
0
1

random block code
f : {0, . . . , 2k 1} ⇥ {0, 1}N

p(x)

k

···
···
···
···
···
···
···
···
···

~ i.i.d. Bern(1/2)
2k

p(x|y1N )

p(x|y1 )

y1

02

1
1
0
1
0
0
0
0
1

1

x

y2

02

k

1

···

yN

x

02

k

1

x

Fig. 4. Non-adaptive block querying based on random block coding with encoder f : {0, . . . , 2k − 1} → {0, 1}N . The i-th querying region (shade region)
is the union of the sub-intervals Im0 = [m0 2−k , (m0 + 1)2−k ) for messages m0 for which the associated codeword has bit 1 at the i-th position. Since every
symbol of every codeword are i.i.d. with Bernoulli(1/2), at each querying about a half of the sub-intervals belong to the querying region. As the querying
progresses, if the posterior probability of the event {x ∈ Im } for the correct message m becomes higher than those of the other incorrect messages, the
player can correctly decode the index m of the sub-interval where the value x of the target variable belongs.

We review previous results on analyzing the exponentially decreasing rate of Pr(M̂ 6= M ) for random block codes with the
ML decoding, and use it to analyze the best achievable quantized-MSE exponent (17) with the random block codes.
For the random block codes of rate R, define the best achievable error exponent for the block-decoding-error probability
Pr(M̂ 6= M ) as
− ln Pr(M̂ 6= M )
Er (R) := lim inf
.
(39)
N →∞
N
For a BSC() with the optimal input distribution Bernoulli(1/2), Forney’s analysis [16] provides a closed form solution for
Er (R),
(
E0 (1/2, ) − R, 0 ≤ R < Rcrit (),
Er (R) =
(40)
DB (γGV (R)k), Rcrit () ≤ R ≤ C,
p
√ √
where E0 (a, b) = −√ln(1−2a(1−a)( b− 1 − b)2 ) and thus E0 (1/2, ) = − ln(1/2+ (1 − )), Rcrit () = DB (γcrit ()k1/2)
with γcrit () = √+√1− , C = HB (1/2) − HB (), and γGV (R) is the normalized Gilbert-Varshamov distance, defined such
that DB (γGV (R)k1/2) = R. The exponent Er (R) is a decreasing function of the rate R. As shown in [17] (pp. 147-149), for
a very noisy channel ( ≈ 0.5) the error exponent in (40) can be approximated as
(
C
− R,
0 ≤ R < C4 ,
√ 2 C
(41)
Er (R) ≈ 2√
( C − R) , 4 ≤ R ≤ C.
From the upper bound in (21) we obtain the bound on the quantized MSE:
˙ −N Er (R) .
E[cq (X, X̂N,finite )]≤e

(42)

Therefore, Er (R) is the achievable quantized-MSE exponent. Moreover, we can also show that the exponent Er (R) is not just
an achievable quantized-MSE exponent but the best achievable quantized-MSE exponent with the random block coding. In
Lemma 4, we prove this result by using fact that the random block codes provide equal error protection for every information bit,
which makes the exponent of every bit-decoding-error probability equal to the exponent of the block-decoding-error probability,
i.e.,
.
(43)
Pr(Bi 6= Bi ) = Pr(M̂ 6= M ), ∀i ∈ {1, . . . , k = N R/ ln 2}.
∗
Lemma 4: The best achievable quantized-MSE exponent Eq,rc
(R) with the non-adaptive block-querying strategy based on
random block codes of rate R is equal to
∗
Eq,rc
(R) = Er (R)
(44)

for the random-coding exponent Er (R) defined in (40).
Proof: Appendix C.
√
Compared to the UEP repetition coding that achieves MSE and the quantized MSE decreasing exponentially only in N ,
the block querying based on random block coding achieves the estimation errors exponentially decreasing in N , matching the
error rates of the adaptive bisection policy. However, the random block coding is not a MSE-optimal non-adaptive policy since
it does not take into account the different contributions of decoding error of each information bit to the MSE. In the next
section, we introduce a new non-adaptive block querying strategy based on superposition coding, which employs both coding
gain and unequal error protection.

12

IV. N ON -A DAPTIVE B LOCK Q UERYING BASED ON S UPERPOSITION C ODING
Superposition coding [14] was originally developed as a channel-coding scheme for communications over a degraded
broadcast channel where one receiver is statistically stronger than the other so that the stronger receiver can always recover the
weaker receiver’s message as well as its own message. The weaker receiver’s message is thus treated as a public message and
the stronger receiver’s message as a private message. Since the public message should be decodable not only to the stronger
receiver but also to the weaker receiver, a better error protection is required for the public message than for the private message.
Superposition-coding scheme provides a higher level of error protection for the public message than for the private message.
In this section, we use this superposition-coding principles to develop a non-adaptive block-querying strategy that provides
better error protection for MSBs than for LSBs in the dyadic expansion of the target variable X ≈ 0.B1 B2 . . . Bk . Not only
does the proposed strategy provide unequal error protection for MSBs vs. LSBs, but it also achieves reliable communications
for k = N R/ ln 2 information bits at any fixed rate 0 < R ≤ C where C is the capacity of a given channel. By unequally
distributing a fixed amount of querying resource to the MSBs and LSBs of the target variable, the UEP querying strategy
achieves better MSE convergence rates than that of the querying strategy based on random block coding, which distributes the
querying resource equally to all the queried information bits.
We first partition the information bits (B1 , . . . , Bk ) into two sub-groups, a group containing the first k1 < k bits of
X (B1 , . . . , Bk1 ) and the other group containing the remaining k2 := k − k1 bits of X (Bk1 +1 , . . . , Bk1 +k2 ). The group
of MSBs (B1 , . . . , Bk1 ) determines the more important partial message M1 ∈ {0, . . . , 2k1 − 1}, while the group of LSBs
(Bk1 +1 , . . . , Bk1 +k2 ) determines the less important partial message M2 ∈ {0, . . . , 2k2 − 1}. Denote the rates of M1 (MSBs)
and of M2 (LSBs) by R1 = (k1 ln 2)/N and R2 = (k2 ln 2)/N , respectively.
Upon transmission of M = (M1 , M2 ) of total rate R = R1 + R2 , the quantized MSE E[cq (X, X̂N )] can be expressed in
terms of the decoding events of the two partial messages (M1 , M2 ) as
E[cq (X, X̂N )]
= Pr(M̂1 6= M1 )E[cq (X, X̂N )|M̂1 6= M1 ]


+ Pr(M̂1 = M1 , M̂2 6= M2 )E[cq (X, X̂N )|M̂1 = M1 , M̂2 =
6 M2 ]


+ Pr(M̂1 = M1 , M̂2 = M2 )E[cq (X, X̂N )|M̂1 = M1 , M̂2 = M2 ] .

(45)

When the partial message M1 , which is composed of the N R1 -most significant bits of X, can be correctly decoded, the
quantized MSE associated with the finite-resolution estimator X̂N = X̂N,finite in (11) can be bounded above by e−2N R1 . By
using this bound and the fact that E[cq (X, X̂N )|M̂1 = M1 , M̂2 = M2 ] = 0, the quantized MSE can be bounded above as
E[cq (X, X̂N,finite )] ≤ Pr(M̂1 6= M1 ) + Pr(M̂2 6= M2 |M̂1 = M1 )e−2N R1

(46)

for R1 < R. By the weight e−2N R1 on Pr(M̂2 6= M2 |M̂1 = M1 ), the decoding error of the partial message M2 (LSBs),
conditioned on the correctly decoded M1 (MSBs), contributes less to the estimation error, than does the decoding error of M1
(MSBs).
When we use random block coding, which provides equal error protection for every information bit of the message M , the
best achievable decoding-error probabilities for the partial message M1 (MSBs) and for M2 (LSBs) conditioned on the correct
estimate M̂1 = M1 are
.
Pr(M̂1 6= M1 ) = e−N Er (R1 +R2 ) ,
(47)
.
Pr(M̂2 6= M2 |M̂1 = M1 ) = e−N Er (R2 )
where Er (R) is the error exponent of the random block coding at rate R, defined in (40). Since Er (R) is a decreasing function
in the rate R and thus Er (R1 + R2 ) < Er (R2 ) for R1 > 0, the decoding-error probability Pr(M̂1 6= M1 ) of the partial message
M1 decreases in a slower rate than does the conditional decoding-error probability Pr(M̂2 6= M2 |M̂1 = M1 ) of the partial
message M2 . Therefore, the exponentially decreasing rate of the quantized MSE in (46) is dominated by the exponentially
∗
decreasing rate of Pr(M̂1 6= M1 ), and as demonstrated in Lemma 4, the best achievable quantized-MSE exponent Eq,rc
(R)
with the random block coding is equal to Er (R) for R = R1 + R2 .
To improve the quantized-MSE exponent compared to that of random block coding, we need to design a UEP coding
scheme that can provide higher level of error protection for M1 (MSBs) to achieve a better exponentially decreasing rate of
Pr(M̂1 6= M1 ) than that of the random block coding in (47). In this section, we provide such a UEP coding scheme based on
superposition-coding principles. By using the improved convergence rates of Pr(M̂1 6= M1 ), we demonstrate that the proposed
UEP coding scheme achieves a strictly positive gain in the exponentially decreasing rate of the quantized MSE E[cq (X, X̂N )]
for high rate regimes of R > 0.

13

{0, 1}N

Random Coding

{0, 1}N

UEP Coding

Fig. 5. The distributions of codewords (each color dot) in the output space {0, 1}N for random block coding and for UEP coding with two levels of error
protection. To better protect the color information of the codewords, which represents the MSBs of the message of the codewords, the same color codewords
should be clustered together. However, this clustering makes it harder to decode the correct codeword among the same color codewords, i.e., harder to decode
the LSBs of the message.

{0, 1}N

satellite
codeword
z(m1 ,m2 )
cloud
center
u(m1 )

v(m2 )

u(m1 )

z(m1 ,m2 )

Superposition coding
Fig. 6. Superposition coding with two levels of priority, where the first partial codeword u(m1 ) encodes the MSBs of the message (color information of the
codewords) and the second partial codeword v(m2 ) encodes the LSBs of the message.

A. Encoding of Superposition Codes and the Associated Non-Adaptive Block Querying
In Fig. 5, we illustrate the codeword distributions of random block coding and of desired UEP coding with two levels of
error protection, where the MSBs of the message are protected with a higher priority than are the LSBs of the message. Each
color dot is a codeword, and the shell around it is the decoding region for M = (M1 , M2 ) in the output space {0, 1}N . Here
the partial message M1 (MSBs) is represented by the color of the codeword. Codewords with the same color have the same
partial message M1 (MSBs), while their M2 ’s (LSBs) are different. For the random block coding, the same color codewords are
uniformly distributed in {0, 1}N . When a noise vector corrupts the transmitted codeword beyond the correct decoding region,
the decoded codeword may not have the same color as that of the transmitted codeword, since the codewords are uniformly
distributed regardless of their colors and there are eN R1 different colors of the codewords. On the other hand, if the same color
codewords are concentrated together as shown in the right figure, even if the channel noise corrupts the transmitted codeword,
the color information will have higher probability of being correctly decoded. However, the probability of M2 being correctly
decoded given a correct estimate for M̂1 = M1 will be lower for the UEP coding, since the codewords of the same color are
closer to each other and thus harder to be distinguished. We next construct codes that satisfy such a geometric property to
provide two levels of unequal error protection by using superposition-coding principles.
Superposition codes are constructed by superimposing two types of random block codes generated by different distributions.
The first type of random block codes of length N and rate R1 is composed of eN R1 binary length-N codewords, {u(m1 ) },
m1 ∈ {0, . . . , eN R1 − 1}, which encode the more important partial message m1 (MSBs). The symbols of every codeword
are chosen independently at random with Bernoulli(1/2) distribution. We call these partial codewords “cloud centers” in
the output space {0, 1}N . The second type of random block codes of length N and rate R2 is composed of codewords
{v(m2 ) }, m2 ∈ {0, . . . , eN R2 − 1}, and it encodes the less important partial message m2 (LSBs). Every symbol of every
codeword in {v(m2 ) } is independent and identically distributed with Bernoulli(α) distribution for a fixed α ∈ (0, 1/2). This
parameter α determines the distribution of codewords in superposition coding. The codeword z(m1 ,m2 ) for the total message
(m1 , m2 ) is designed by the bit-wise XOR of the two partial codewords u(m1 ) and v(m2 ) . The superposition codes Cs of rate
R = R1 + R2 are thus composed of {z(m1 ,m2 ) } for messages (m1 , m2 ) ∈ {0, . . . , eN R1 − 1} × {0, . . . , eN R2 − 1}, where
z(m1 ,m2 ) = u(m1 ) ⊕ v(m2 ) . The set of codewords {z(m1 ,m2 ) } for a fixed m1 is called “satellite codewords” for the respective
cloud center u(m1 ) . There are eN R2 satellite codewords around each cloud center u(m1 ) . Fig. 6 illustrates the distribution of
codewords with superposition coding.
Note that when α = 1/2 the distribution of the codewords in the superposition codes Cs becomes the same as that of

14

random block coding

UEP coding

p(x|y1N )

p(x|y1N )

correct m1 region

02

correct m1 region

x

k

1
2

02

x

k

k1

1
2

k1

Fig. 7. Illustration of the typical posterior distributions of X after N rounds of querying for random block coding (left) and for UEP coding with two levels
of error protection (right). Consider the case where the posterior probability of X in the correct m1 region is higher for the UEP coding than it is for the
random block coding but the peaks within the correct m1 region are smoother for the UEP coding. For such a case, the UEP coding provides better error
protection for m1 but worse error protection for m2 given the correct m̂1 = m1 than does the random block coding.

random block codes that are composed of eN (R1 +R2 ) independent and identically distributed codewords where every symbol
of every codeword is chosen independently at random with Bernoulli(1/2) distribution. Therefore, the random block codes
with independent codewords of i.i.d. symbols of Beronoulli(1/2) distribution are a special case of the superposition codes. In
contrast to the case of α = 1/2, where every codeword is independent, for superposition codes with α ∈ (0, 1/2) the satellite
codewords {z(m1 ,m2 ) }, m2 ∈ {0, . . . , eN R2 − 1}, for a fixed m1 (the same color codewords), are mutually dependent. Since
the typical Hamming weight of v(m2 ) is N α, the typical distance between a satellite codeword z(m1 ,m2 ) = u(m1 ) ⊕ v(m2 )
and its cloud center u(m1 ) is N α. As α decreases from 1/2 to 0, the satellite codewords become more and more concentrated
around its cloud center. Therefore, the superposition codes satisfy the desired geometric property for unequal error protection
with two levels of error protection. The parameter α ∈ (0, 1/2) determines how much the satellite codewords are concentrated
around its cloud center, which determines the trade-offs between decoding-error probabilities of M1 and of M2 .
There exists a one-to-one mapping between the length-N superposition codewords {z(m1 ,m2 ) } and the corresponding block
of querying regions (Q1 , . . . , QN ). The block of querying regions (Q1 , . . . , QN ) associated with the superposition codewords
{z(m1 ,m2 ) = u(m1 ) ⊕ v(m2 ) }, m1 ∈ {0, . . . , 2k1 − 1}, m2 ∈ {0, . . . , 2k2 − 1}, can be represented in terms of the sub-intervals
Im1 := [m1 2−k1 , (m1 +1)2−k1 ) of length 2−k1 and another set of sub-intervals Im1 ,m2 := [m1 2−k1 +m2 2−(k1 +k2 ) , m1 2−k1 +
(m2 + 1)2−(k1 +k2 ) ) of length 2−(k1 +k2 ) as:
[
Qi =
Im1 ,m2
(m1 ,m2 )
=1

(m1 ,m2 ):zi





=

[

(m )
m1 :ui 1 =1

(m )





Im1 ∩ 


[



 
Im1 ,m2  ∪ 

(m )
m2 :vi 2 =0

[

(m )
m1 :ui 1 =0

Im1 ∩

∪

(m2 )

m2 :vi


!!

Im1 ,m2


(48)

=1

(m )

where ui 1 and vi 2 are the i-th bit of the partial codeword u(m1 ) and that of the partial codeword v(m1 ) , respectively. For a
(m )
partial message m1 whose i-th bit ui 1 of the codeword u(m1 ) equals 1, about (1 − α)-fraction of the sub-intervals {Im1 ,m2 }
(m )
(m )
within the Im1 are included in Qi since vi 2 is i.i.d. with Bernoulli(α), α ∈ (0, 1/2). On the other hand, if ui 1 = 0 for
some m1 , about α-fraction of the sub-intervals {Im1 ,m2 } within the Im1 are included in Qi . Therefore, different from block
querying based on random block coding, where each sub-interval of {Im1 ,m2 : m1 ∈ {0, . . . , 2k1 −1}, m2 ∈ {0, . . . , 2k2 −1}} is
independently included in Qi with probability 1/2, for block querying based on superposition coding the events {Im1 ,m2 ⊂ Qi }
(0 ≤ m2 ≤ 2k2 − 1) for a fixed m1 depend on each other.
Fig. 7 illustrates how the posterior distribution of X after N rounds of querying with the UEP coding (right figure) will
appear as compared to that of the random block coding (left figure). Given the channel outputs y1N , if the posterior probability
over X ∈ [m01 2−k1 , (m01 + 1)2−k1 ) is largest for the correct m01 = m1 among all m01 ∈ {0, . . . , 2k1 − 1}, then the partial
message m1 can be correctly decoded by the optimal ML decoding for the partial message m1 . If the posterior probability
associated with the correct m1 region is larger for the UEP coding than it is for the random block coding, one obtains an
improvement in the decoding-error probability Pr(M̂1 6= M1 ) of the partial message M1 . However, this improvement might
come at the cost of degraded Pr(M̂2 6= M2 |M̂1 = M1 ) due to the geometric structure of codewords with the UEP coding.
B. Decoding of Superposition Codes and the Analysis of Error Exponents for Decoding-Error Probabilities
In this section, we show that the non-adaptive block querying based on the superposition coding achieves an improved error
exponent for the decoding-error probability Pr(M̂1 6= M1 ) of the more important partial message M1 (MSBs) as compared
to that of non-adaptive block querying based on random block coding. This improvement occurs when R1 , the rate of M1
(MSBs), is sufficiently small and R2 < C2 (α) := HB (α ∗ ) − HB (), the rate of M2 (LSBs), is sufficiently larger, where

15

α ∗  = α(1 − ) + (1 − α) and α is the parameter that determines the distribution of the superposition codes as explained in
Section IV-A.
Denote the maximum achievable error exponents of Pr(M̂1 6= M1 ) and of Pr(M̂2 6= M2 |M̂1 = M1 ) with the superposition
coding of rates (R1 , R2 ) by
− ln Pr(M̂1 6= M1 )
,
N →∞
N
(49)
− ln Pr(M̂2 6= M2 |M̂1 = M1 )
∗
.
ELSBs (R2 , α) = lim inf
N →∞
N
We analyze these exponents and compare those to the best achievable decoding-error exponents (47) of the random block
codes.
∗
∗
There have been many previous works [18], [19], [20] to analyze the error exponents EMSBs
(R1 , R2 , α) and ELSBs
(R2 , α)
∗
of superposition codes. A lower bound on ELSBs (R2 , α) can be calculated by directly applying the Gallager’s error-exponent
analysis for a discrete memoryless channel with random block codes, where codewords are independent and composed of i.i.d.
∗
symbols having Bernoulli(α) distribution [20]. On the other hand, the analysis of EMSBs
(R1 , R2 , α) is much more complicated,
since in order to find the most probable M1 (MSBs, or the color of the transmitted codeword) it involves comparisons between
sums of likelihoods of exponentially many satellite codewords in Fig. 6, which are mutually dependent. The optimal maximumlikelihood (ML) decoding for the partial message M1 finds m̂1 such that
!


X
N
(m1 ,m2 )
m̂1 = arg max
p
y|z
(50)
∗
EMSBs
(R1 , R2 , α) = lim inf

m1

m2

QN
where y is the length-N channel-output sequence for the input codeword z(m1 ,m2 ) , pN (y|z) = i=1 pY |Z (yi |zi ) and pY |Z (y|z)
∗
is the transition probability of the BSC(). Even though there exist a few lower bounds on EMSBs
(R1 , R2 , α) and some bounds
∗
(R1 , R2 , α).
are shown to be numerically tighter than the others, there has been no simple closed form solution for EMSBs
∗
Since our goal is not to exactly calculate the error exponent EMSBs (R1 , R2 , α) of Pr(M̂1 6= M1 ) but to prove gains in this
error exponent from the UEP superposition coding, we consider two well-known sub-optimal decoding rules that provide
∗
lower bounds on EMSBs
(R1 , R2 , α). We show that these lower bounds are already greater than the optimal error exponent
Er (R1 + R2 ) of the random block codes.
The first sub-optimal decoding rule we consider is joint-maximum-likelihood (JML) decoding for m = (m1 , m2 ). Given the
received word y = z(m1 ,m2 ) ⊕ n, which is a noisy version of the transmitted codeword z(m1 ,m2 ) added by a length-N noise
word n composed of i.i.d. symbols of Bernoulli() distribution, this decoding rule finds the most probable (m̂1 , m̂2 ) such that


(m̂1 , m̂2 ) = arg max pN y|z(m1 ,m2 ) .
(51)
(m1 ,m2 )

Note that this decoding rule minimizes the probability of block-decoding error (M̂1 , M̂2 ) 6= (M1 , M2 ) but not the probability
of the partial-decoding error M̂1 6= M1 , so that this is a sub-optimal decoding rule for M1 . The decoding error of M1 happens
only when M̂1 6= M1 , regardless of whether or not M̂2 = M2 . Let EMSBs,JML (R1 , R2 , α) denote the best achievable error
exponent of Pr(M̂1 6= M1 ) with the JML decoding rule. In Lemma 5, we show that EMSBs,JML (R1 , R2 , α) ≥ Er (R1 + R2 )
for every (R1 , R2 ), regardless of the choice of α ∈ (0, 1/2). This implies that the superposition codes provide a better, or at
least as good, error protection for the partial message M1 than does the random block codes for every (R1 , R2 ), independent
of the choice of α ∈ (0, 1/2).
The second sub-optimal decoding rule we consider is successive-cancellation
(SC) decoding. To decode m̂1 , this decoding
 (m )
1
rule focuses only on the geometry of the partial codewords
u
,
m
∈
{0,
.
.
. , eN R1 − 1}, (cloud centers in Fig. 6) while
1
 (m ,m )
1
2
. More specifically, this decoding rule behaves as if one of
ignoring the true structure of the overall codewords z
{u(m1 ) } is transmitted and the received word y is corrupted by a noise word v(m2 ) ⊕ n. Note that u(m1 ) , v(m2 ) , and n are
independent of each other, and every symbol of the partial codeword v(m2 ) is i.i.d. with Bernoulli(α) and every symbol of the
noise word n is i.i.d. with Bernoulli(). Therefore, the new noise word v(m2 ) ⊕ n is modeled as a sequence of i.i.d. symbols
following Bernoulli(α ∗ ) distribution where α ∗  = α(1 − ) + (1 − α). Denoting by qY |U (y|u) the transition probability
QN
of the BSC(α ∗ ) and defining q N (y|u) = i=1 qY |U (yi |ui ), this sub-optimal decoding rule produces an estimate m̂1 of m1
such that


m̂1 = arg max q N y|u(m1 )
(52)
m1

for a given channel output sequence y. After decoding m1 and having the estimate m̂1 , the SC decoding rule subtracts u(m̂1)
from y and finds the estimate m̂2 for the partial message m2 (LSBs) that maximizes the likelihood of pN y ⊕ u(m̂1 ) |v(m2 )


m̂2 = arg max pN y ⊕ u(m̂1 ) |v(m2 ) .
(53)
m2

16

Let EMSBs,SC (R1 , α) and ELSBs,SC (R2 , α) denote the best achievable error exponents of Pr(M̂1 6= M1 ) and of Pr(M̂2 6=
M2 |M̂1 = M1 ), respectively, with the SC decoding rule. Forney’s analysis [16] yields the exponentially-tight error exponent
EMSBs,SC (R1 , R2 , α) for Pr(M̂1 6= M1 ) with the SC decoding rule:
(
E0 (1/2, α ∗ ) − R1 , 0 ≤ R1 ≤ Rcrit (α ∗ ),
(54)
EMSBs,SC (R1 , α) =
DB (γGV (R1 )kα ∗ ), Rcrit (α ∗ ) < R1 ≤ C − C2 (α).
√
Here γGV ∈ [0, 1/2] is the Gilbert-Varshamov distance
satisfying DB (γGV (R)k1/2) = R, E0 (a, b) = − ln(1 − 2a(1 − a)( b −
p
√
1 − b)2 ) and thus E0 (1/2, α ∗ ) = − ln(1/2 + (α ∗√)(1 − (α ∗ ))), C = HB (1/2) − HB (), C2 (α) = HB (α ∗ ) − HB (),
√
Rcrit (α∗) = DB (γcrit (α∗)k1/2) for γcrit (α∗) = √α∗+α∗
. For a given α ∈ (0, 1/2), the error exponent ELSBs,SC (R2 , α)
1−α∗

of Pr(M̂2 6= M2 |M̂1 = M1 ) can be shown to be positive for every 0 ≤ R2 < C2 (α).
∗
The following lemma summarizes two lower bounds on the error exponent EMSBs
(R1 , R2 , α) (49) achievable with the
sub-optimal JML decoding and with the sub-optimal SC decoding, respectively.
Lemma 5: Superposition coding provides a better, or at least as good, error protection for the partial message M1 (MSBs of
the message) than does the random block coding for every pair of rates (R1 , R2 ) of the partial messages (M1 , M2 ), regardless
of the choice of the parameter α ∈ (0, 1/2) of the superposition coding. With joint-maximum-likelihood (JML) decoding for
superposition codes, the error exponent EMSBs,JML (R1 , R2 ) of Pr(M̂1 6= M1 ), which is greater than or equal to Er (R), is
achievable, i.e.,
∗
EMSBs
(R1 , R2 , α) ≥ EMSBs,JML (R1 , R2 ) ≥ Er (R1 + R2 ).
(55)
Moreover, for a sufficiently small R1 > 0 and sufficiently large R2 < C2 (α) = HB (α ∗ ) − HB (), a strictly positive gain in
the error exponent can be achieved using successive-cancellation (SC) decoding rule, i.e.,
∗
EMSBs
(R1 , R2 , α) ≥ EMSBs,SC (R1 , α) > Er (R1 + R2 )

(56)

where EMSBs,SC (R1 , α) is the best achievable decoding-error exponent for M1 using the SC decoding rule.
Proof: Appendix D.
For a very noisy BSC(), we can further demonstrate that, when we choose the rate R2 of the partial message M2 (LSBs)
equal to the maximum possible rate C2 (α) to guarantee Pr(M̂2 6= M2 |M̂1 = M1 ) → 0 as N → ∞, the superposition coding
provides a strictly positive gain in the error exponent of Pr(M̂1 6= M1 ) as compared to that of the random block coding, for
∗
the entire regime of R1 ∈ [0, C − C2 (α)) where EMSBs
(R1 , R2 , α) is positive.
Lemma 6: For a very noisy BSC() where  = 0.5 − δ for a sufficiently small δ > 0, assume a fixed α ∈ (0, 1/2) and the
∗
rate R2 = C2 (α). Then the best achievable error exponent EMSBs
(R1 , R2 , α) of Pr(M̂1 6= M1 ) for superposition coding is
strictly larger than the best achievable error exponent Er (R1 + R2 ) of random block coding for every R1 ∈ [0, C − C2 (α)). In
particular, with successive cancellation (SC) decoding rule we can achieve an error exponent EMSBs,SC (R1 , α) that is strictly
larger than Er (R1 + R2 ),
∗
EMSBs
(R1 , R2 , α) ≥ EMSBs,SC (R1 , α) > Er (R1 + R2 ),
(57)
for every R1 ∈ [0, C − C2 (α)).
Proof: Appendix E.
In Fig 8, we provide a plot of the error exponent Er (R1 + R2 ) of random block coding (solid line) and the error exponent
EMSBs,SC (R1 , α) of superposition coding with successive-cancellation decoding (dash-dot line) over R = R1 + R2 for a
BSC(0.45) with a fixed α = 0.11 and R2 = C2 (α). The plot for EMSBs,SC (R1 , α) starts from R = C2 (α) at which R1 = 0.
It is shown that EMSBs,SC (R1 , α) is larger than Er (R1 + R2 ) for every R1 ∈ [0, C − C2 (α)).
Lemma 5 and 6 demonstrate that even with the sub-optimal decoding rules (either JML or SC rule) the superposing coding
can provide a better error protection for the MSBs of the transmitted message than does the random block coding. In the next
section, we use this result to show that the superposition coding achieves strictly positive gains in the exponentially decreasing
rates of quantized MSE and MSE.
C. Gains in the quantized-MSE exponent and MSE Exponent from Superposition Coding
By using the improvement in the decoding-error exponent of M1 (MSBs) from superposition coding, we next demonstrate a gain in the exponentially decreasing rate of the quantized MSE E[cq (X, X̂N,finite )] for the quantized cost function
∗
cq (X, X̂N,finite ) (12) of resolution k = N R/ ln 2 bits for a fixed rate R > 0. Define Eq,spc
(R) the best achievable exponentially
decreasing rate of E[cq (X, X̂N,finite )] with the non-adaptive block querying based on the superposition coding (SPC) of rate
R:
− ln E[cq (X, X̂N,finite )]
∗
Eq,spc
(R) = lim inf
.
(58)
N →∞
N
As shown in (46), the quantized MSE is bounded above by
E[cq (X, X̂N,finite )] ≤ Pr(M̂1 6= M1 ) + Pr(M̂2 6= M2 |M̂1 = M1 )e−2N R1 ,

(59)

17

Er (R)
EMSBs,SC (R1 , ↵) at R2 = C2 (↵)

C2 (↵)

Fig. 8. A plot of decoding-error exponents of the more important partial message M1 (MSBs) for random block coding, Er (R1 + R2 ) (solid line), and
for superposition coding with successive-cancellation decoding, EMSBs,SC (R1 , α) (dash-dot line), where  = 0.45 and α = 0.11. When the rate R2 of the
less important partial message M2 (LSBs) equals C2 (α), which is the maximum rate to guarantee Pr(M̂2 6= M2 |M̂1 = M1 ) → 0 as N → ∞, for every
R1 ∈ [0, C − C2 (α)) the error exponent EMSBs,SC (R1 , α) of superposition coding is larger than the error exponent Er (R1 + R2 ) of random block coding.

and the exponentially decreasing rate of the quantized MSE is dominated either by the error exponent of Pr(M̂1 6= M1 ) or
by the error exponent of Pr(M̂2 6= M2 |M̂1 = M1 ) plus 2R1 . For random block coding, the exponentially decreasing rate
Er (R) of Pr(M̂1 6= M1 ) is smaller than that of Pr(M̂2 6= M2 |M̂1 = M1 ), so that the random block coding achieves the
∗
quantized-MSE exponent Eq,rc
(R) equal to Er (R), as demonstrated in Lemma 4.
In Lemma 5 and 6, we showed that the superposition coding achieves a better error exponent of Pr(M̂1 6= M1 ) by
providing higher-level error protection for M1 (MSBs) than does the random block coding. But this improvement comes with
∗
(R) with
degraded error protection for M2 (LSBs). Therefore, to analyze the best achievable quantized-MSE exponent Eq,spc
the superposition coding, we need to consider the trade-offs in the levels of error protection for M1 (MSBs) and for M2 (LSBs),
which can be controlled by the choice of the respective rates (R1 , R2 ) of the two partial messages, under the constraint of the
total rate R1 + R2 = R, and the choice of the distribution parameter α ∈ (0, 1/2) of the superposition coding. From (59), the
∗
best achievable quantized-MSE exponent Eq,spc
(R) is bounded below by
∗
Eq,spc
(R) ≥

max

{(R1 ,R2 ,α):
R1 +R2 =R,
α∈(0,1/2)}

∗
∗
min{EMSBs
(R1 , R2 , α), ELSBs
(R2 , α) + 2R1 },

(60)

∗
∗
where EMSBs
(R1 , R2 , α) and ELSBs
(R2 , α) are the best achievable error exponents of Pr(M̂1 6= M1 ) and of Pr(M̂2 6=
M2 |M̂1 = M1 ), respectively, with the superposition coding, as defined in (49).
For a given α ∈ (0, 1/2), when we choose the rate R2 of the partial message M2 (LSBs) equal to C2 (α) = HB (α∗)−HB (),
which is the maximum possible rate of M2 to guarantee Pr(M̂2 6= M2 |M̂1 = M1 ) → 0 as N → ∞, the resulting error exponent
∗
∗
ELSBs
(R2 , α) equals 0. This particular choice of R2 = C2 (α) provides a lower bound on Eq,spc
(R) such that
∗
Eq,spc
(R) ≥

max

{α:α∈(0,1/2)}

∗
min{EMSBs
(R − C2 (α), C2 (α), α), 2(R − C2 (α))}.

(61)

The optimization in the right-hand side is about finding the optimal value of the distribution parameter α ∈ (0, 1/2) of the
superposition coding.
∗
In the theorem below, we prove that for a very noisy BSC() the quantized-MSE exponent Eq,spc
(R) is strictly larger than
that of random block coding, i.e.,
∗
∗
Eq,spc
(R) > Eq,rc
(R) = Er (R),
(62)
at high-rate regimes of R ∈ (E0 (1/2, )/3, C), by solving the optimization in the right-hand side of (61) and proving that
∗
this lower bound is greater than the best achievable quantized-MSE exponent Eq,rc
(R) of random block coding. To prove this
theorem, we use Lemma 6 where we showed that for a very noisy BSC() successive-cancellation decoding for superposition
coding provides a strictly positive gain in the error exponent of M1 (MSBs) at every rate R1 ∈ (0, C − C2 (α)) of M1 (MSBs)
when the rate R2 of M2 (LSBs) is fixed as R2 = C2 (α).
Theorem 1: For a very noisy BSC() with  = 0.5 − δ for a sufficiently small δ > 0, the best achievable quantized∗
∗
MSE exponent Eq,spc
(R) of superposition coding is strictly larger than the best achievable quantized-MSE
exponent Eq,rc
(R)
p
of random block coding for every rate R ∈ (E0 (1/2, )/3, C) where E0 (1/2, ) = − ln(1/2 + (1 − )) ≈ C/6 and

18

2R
E⇤q,rc (R) = Er (R)
Eq,spc (R)

∗ (R) = E (R), E
∗
Fig. 9. A plot of Eq,rc
r
q,spc (R), and 2R for a BSC() with  = 0.45 where Eq,rc (R) is the best achievable quantized-MSE exponent
∗
(R) with superposition coding. For any
with random block coding and Eq,spc (R) is a lower bound on the best achievable quantized-MSE exponent Eq,spc
R ∈ (E0 (1/2, )/3, /C), there exists a gain in the achievable quantized-MSE exponent from superposition coding compared to that of random block coding.

C = HB (1/2) − HB (). In particular, successive-cancellation (SC) decoding for superposition coding achieves the quantized∗
(R) for R ∈ (E0 (1/2, )/3, C), i.e.,
MSE exponent Eq,spc (R) that is strictly larger than Eq,rc
∗
∗
Eq,spc
(R) ≥ Eq,spc (R) > Eq,rc
(R) = Er (R),

(63)

Eq,spc (R) = EMSBs,SC (R − C2 (α∗ ), α∗ )

(64)

where
for EMSBs,SC (R1 , α) in (54), C2 (α) = HB (α ∗ ) − HB () and α∗ ∈ (0, 1/2) satisfying R = C2 (α) + E0 (1/2,α∗)
.
3
Proof: Appendix G
In Fig 9, we provide a plot of Eq,spc (R) in (64) (dash-dot line), which is a lower bound on the best achievable quantized-MSE
∗
∗
(R) in (44) (solid line), which is the best achievable quantized-MSE
(R) with superposition coding, and Eq,rc
exponent Eq,spc
exponent with random block coding, with the line 2R (dashed line). Here we consider a BSC() with  = 0.45. We can observe
that the achievable quantized-MSE exponent Eq,spc (R) with superposition coding is strictly larger than the best achievable
∗
quantized-MSE exponent Eq,rc
(R) with random block coding, at every rate R ∈ (E0 (1/2, )/3, C), as stated in Theorem 1.
We next consider the achievable MSE E[|X − X̂N,finite |2 ] with the superposition coding and demonstrate a gain in the MSE
exponent in the high-rate regimes as compared to that of the random∗ block coding. As shown in (13) and (18) the MSE can be
.
written as a sum of the quantized MSE E[cq (X, X̂N,finite )] = e−N Eq,policy (R) and the estimation error from the finite-resolution
estimator X̂N,finite as
∗
∗
.
.
E[|X − X̂N,finite |2 ] = e−N Eq,policy (R) + e−N 2R = e−N min{Eq,policy (R),2R} .

(65)

∗
∗
As shown in (18), the MSE exponent EMSE,policy
(R) and the quantized-MSE exponent Eq,policy
(R) at a fixed rate R > 0 are
related as
∗
∗
EMSE,policy
(R) = min{Eq,policy
(R), 2R}.
(66)
∗
When Eq,policy
(R) > 2R, the MSE exponent at a fixed rate R is limited by the quantization error from the finite-resolution
∗
estimator of rate R. When Eq,policy
(R) ≤ 2R, on the other hand, the MSE exponent is governed by the quantized-MSE
exponent, which depends on the error exponents of decoding-error probabilities of the two partial messages (M1 , M2 ) of rates
(R1 , R2 ) where R1 + R2 = R.
∗
∗
For random block coding, since the quantized-MSE exponent Eq,rc
(R) is equal to Er (R), the MSE exponent EMSE,rc
(R)
of random block coding equals
∗
EMSE,rc
(R) = min{Er (R), 2R}.
(67)

For a very noisy BSC(), the decoding-error exponent Er (R) of random block coding can be approximated as (40). By using
this approximation, we can show that, where  ∈ [0.5 − δ, 0.5] for a sufficiently small δ > 0,
(
2R,
0 ≤ R ≤ E0 (1/2, )/3,
∗
EMSE,rc
(R) =
(68)
Er (R), E0 (1/2, )/3 < R ≤ C.

19

Fig. 10. Monte Carlo simulation for quantized-MSE E[cq (X, X̂N,finite )] of the querying policies based on superposition coding (dash-dot line) and
of random block coding (solid line) as a function of the number of queries, where the rates (R1 , R2 ) of the partial messages (M1 , M2 ) are fixed as
(R1 , R2 ) = (0.5(C − R2 ), 0.9C2 (α)) for capacity C of the BSC() and for the maximum achievable rate C2 (α) of M2 . The crossover probability  of
the BSC() and the distribution parameter α of the superposition coding are set to be  = 0.3 and α = 0.1, respectively. The markers in each line indicate
the simulation points in terms of (k1 , k2 ), the numbers of MSBs and of LSBs that are queried during the respective number N of queries, for N satisfying
N = (k1 ln 2)/R1 = (k2 ln 2)/R2 . In this simulation, we checked five pairs of (k1 , k2 ) including (5, 4), (6, 5), (6, 6), (7, 7), and (8, 8) at the fixed rate
pair (R1 , R2 ) with the increasing number of queries. The number of Monte Carlo trials at each simulation point is equal to 3000.
∗
(R) of the random block coding is dominated by
In the low-rate regime of 0 ≤ R ≤ E0 (1/2, )/3, the MSE exponent EMSE,rc
the estimation error from the finite-resolution estimator of rate R. On the other hand, in the high rate regime of E0 (1/2, )/3 <
∗
∗
(R), which is equal to Er (R).
R ≤ C, the MSE exponent EMSE,rc
(R) is dominated by the quantized-MSE exponent Eq,rc
∗
We next consider the MSE exponent EMSE,spc (R) of superposition coding, which is equal to
∗
∗
EMSE,spc
(R) = min{Eq,spc
(R), 2R}.

(69)

∗
(R)
Eq,spc

of superposition coding is strictly larger than that
In Theorem 1, we demonstrated that the quantized-MSE exponent
∗
∗
(R) = Er (R) at any rate R ∈ (E0 (1/2, )/3, C) for a very noisy BSC().
(R) > Eq,rc
of random block coding, i.e., Eq,spc
∗
Combining this result with the fact that EMSE,rc
(R) = Er (R) > 2R in this regime of R ∈ (E0 (1/2, )/3, C), we can conclude
∗
∗
that the MSE exponent EMSE,spc (R) with superposition coding is strictly larger than the MSE exponent EMSE,rc
(R) of random
block coding in R ∈ (E0 (1/2, )/3, C) for a very noisy BSC().
∗
Corollary 1: For a very noisy BSC() with  = 0.5 − δ for a sufficiently small δ > 0, the MSE exponent EMSE,spc
(R) with
∗
superposition coding is strictly larger than that of random block coding EMSE,rc (R) at any rate R ∈ (E0 (1/2, )/3, C), i.e,
∗
∗
EMSE,spc
(R) > EMSE,rc
(R) = Er (R).

(70)

The non-adaptive block querying based on superposition coding thus achieves a strictly lager MSE exponent than that of
random block coding, when the querying resolution of the block querying strategy scales as k = N R/ ln 2 bits for any rate
R ∈ (E0 (1/2, )/3, C) over a very noisy BSC().
In Fig 9, we can see that the gain in the quantized-MSE exponent from superposition coding in R ∈ (E0 (1/2, )/3, C) also
∗
results in a gain in the MSE exponent in this high rate regime, since the MSE exponent EMSE,spc
(R) of superposition coding
∗
is proven to be at least larger than Er (R) in this regime, which is equal to the MSE exponent EMSE,rc
(R) of random block
coding, as stated in Corollary 1.
In this section, we focused our discussion on very noisy BSC()s and proved gains in the achievable convergence rates of
estimation errors from superposition coding by using approximations of error exponents of decoding-error probabilities in the
high-noise regime of  ∈ (1/2 − δ, 1/2) for a sufficiently small δ > 0. For other noise regimes, on the other hand, such a nice
approximation of error exponents of decoding-error probabilities does not exist, and it is hard to compare the quantized-MSE
exponent of superposition coding and that of random block coding. Instead, in the next section, we show empirical performances
of the querying policies in mild-noise regimes by comparing the quantized MSE of superposition coding and that of random
block coding.
D. Simulations: Performance of Superposition Coding vs. Random Block Coding
In this section, we compare the performance of two querying policies, one based on superposition coding, which provides
two different levels of error protection for MSBs vs. LSBs in the dyadic expansion of the target variable, and the other based

20

TABLE I
C OMPARISON OF FOUR DIFFERENT QUERYING POLICIES
Policy
Bisection policy
Repetition policy
Random block coding
Superposition coding

MSE convergence rate
e−c1 N
, c1 > 0
√
e−c2 N , c2 > 0
e−c3 N , c3 > 0
e−c4 N , c4 ≥ c3 > 0

Features
Adaptive
Non-adaptive, unequal error protection, no coding gain
Non-adaptive, equal error protection, coding gain
Non-adaptive, unequal error protection, coding gain

on random block coding, which provides equal error protection to all the information bits in the dyadic expansion of the target
variable.
Fig. 10 shows the empirical performance of these two non-adaptive block querying policies by comparing the quantized
MSE E[cq (X, X̂N,finite )] of superposition coding (dash-dot line) and that of random block coding (sold line) for a BSC()
with  = 0.3, where the distribution parameter α of the superposition coding equals α = 0.1 and the rates of the two partial
messages M1 (MSBs) and M2 (LSBs) are fixed as (R1 , R2 ) = (0.5(C − R2 ), 0.9C2 (α)) for C = HB (1/2) − HB () and
C2 (α) = HB (α ∗ ) − HB (). We observe that the estimation error from the superposition coding is about one third of that of
random block coding at the number of queries only about 200. Therefore, even though Theorem 1 states the performance gain
from the UEP superposition coding in the asymptotic regime for very noisy BSCs, empirical simulations show that the idea
of designing a non-adaptive querying policy by using the UEP superposition coding provides performance gains in estimating
the target variable even in non-asymptotic regimes of the number of queries and for wider range of noise levels of BSCs.
V. C OMPARISON B ETWEEN P ERFORMANCES O F THE F OUR D IFFERENT Q UERYING P OLICIES
In this section, we summarize and compare the four different querying policies discussed in this paper, including the adaptive
bisection policy (Section III-A), the non-adaptive UEP repetition policy (Section III-B), the non-adaptive block querying based
on random block coding (Section III-C), and the non-adaptive block querying based on UEP superposition coding (Section IV).
Table I summarizes the MSE convergence rates and features of the four policies. Only the bisection policy uses past answers
from the oracle to design the next query, while the other three policies determine a set of queries non-adaptively. Among the
three non-adaptive block-querying policies, repetition policy and the policy based on superposition coding provide unequal
error protection for MSBs vs. LSBs in the dyadic expansion of the target variable, while the block-querying policy based on
random block coding √
provides equal error protection for every information bit. Repetition policy achieves MSE decreasing
exponentially only in N , while the other two non-adaptive block querying policies as well as the bisection policy achieve
√
the linear in N exponential rate of decrease. This is because the optimal repetition policy can extract only k = O( N )
information bits reliably by N number of queries. Non-adaptive block-querying policies based on either random block coding
or superposition coding, on the other hand, can extract up to k < N R bits for any positive rate 0 < R < C by N number of
queries over a binary symmetric channel of capacity C. Furthermore, superposition coding achieves a better MSE exponent
than that of random block coding by providing unequal error protection for information bits.
We next compare the achievable quantized-MSE exponent at a fixed rate R > 0 for the three non-adaptive querying policies.
∗
• Non-adaptive UEP repetition querying: Eq,repetition (R) = 0 for every rate R > 0.
∗
• Non-adaptive block querying based on random block coding: Eq,rc (R) = Er (R) for Er (R) in (40), i.e.,
(
E0 (1/2, ) − R, 0 ≤ R < Rcrit (),
Er (R) =
(71)
DB (γGV (R)k), Rcrit () ≤ R ≤ C.
•

∗
Non-adaptive block querying based on superposition coding: Eq,spc
(R) ≥ max{Er (R), Eq,spc (R)} where

Eq,spc (R) :=

max min{EMSBs,SC (R − C2 (α), α),

α∈(0,1/2)

(72)

2(R − C2 (α))},
for EMSBs,SC (R1 , α) in (54).
∗
∗
∗
When we compare the three exponents Eq,repetition
(R), Eq,rc
(R), and Eq,spc
(R) of the non-adaptive policies, we can show
that
∗
∗
∗
Eq,spc
(R) ≥ Eq,rc
(R) ≥ Eq,repetition
(R),
(73)
which implies that the non-adaptive block querying based on superposition coding can achieve better error rates of convergence
∗
∗
for the quantized MSE than do the other two non-adaptive policies. The first inequality between Eq,spc
(R) and Eq,rc
(R) follows
from the fact that random block coding is a special case of superposition coding where the parameter α equals 1/2. In Theorem 1,
∗
∗
we also demonstrated a strictly positive gain Eq,spc
(R) > Eq,rc
(R) in the high rate regimes of R for a very noisy BSC() from
∗
the observation that the lower bound Eq,spc (R) in (72) satisfies Eq,spc
(R) > Eq,spc (R) > Er (R).

21

Fig. 11. Monte Carlo simulation for quantized-MSE performance of the querying policies based on random block coding (solid line), superposition coding
(dash-dot line), and bisection policy (dashed line) as a function of the number of queries, where the pair of resolution bits (k1 , k2 ) for the MSBs and LSBs
of the value of the target variable is fixed as (k1 , k2 ) = (6, 6) for every N . The crossover probability  of the BSC() and the distribution parameter α of
the superposition coding are set to  = 0.3 and α = 0.1, respectively. The number of Monte Carlo trials is equal to 3000.

We next compare the performance between the adaptive bisection policy (BZ algorithm) and two non-adaptive querying
policies, one based on random block coding and the other based on superposition coding. In Lemma III-A of Section III-A,
we stated a lower bound on the quantized-MSE exponent for the adaptive BZ algorithm. But we cannot use this lower bound
in comparing the performance between the adaptive BZ algorithm and the two non-adaptive policies, since the tightness of this
lower bound was not proven. Instead, Monte Carlo simulations are provided to compare the empirical performance of these
three policies.
Fig. 11 shows a plot of the empirical quantized MSE E[cq (X, X̂N,finite )] of the two non-adaptive querying policies, random
block coding (solid line) and superposition coding (dash-dot line), as well as that of the BZ algorithm (dashed line) as a
function of the number N of queries, where the pair of resolution bits (k1 , k2 ) for the MSBs and LSBs of the value of the
target variable is fixed as (k1 , k2 ) = (6, 6) for every N . It is observed that the bisection policy achieves the quantized MSE,
one to three orders of magnitude smaller than those of the two non-adaptive policies with number of queries less than 200. The
non-adaptive policy based on superposition coding achieves gain in the quantized MSE performance over that of the random
block coding, but falls short of achieving as fast convergence rate as that of the adaptive bisection policy in the non-asymptotic
regime of number of queries.
VI. F UTURE D IRECTIONS
In this paper, the problem of optimal query design was considered in the context of noisy 20 questions game with the
goal of estimating the value of a continuous target variable. We proposed a new non-adaptive block-querying policy based
on superposition coding that could not only extract k = N R/ ln 2 information bits (0 < R ≤ C) reliably over N uses of a
BSC() of capacity C but also provide two levels of unequal error protection (UEP) for the information bits. Different from
the
√ UEP repetition querying policy considered in [2] where the best achievable quantized MSE decreases exponentially only in
N where N is the number of queries, our non-adaptive querying policy based on superposition coding achieves linear in N
exponential rate of decrease, matching the rate of the bisection-based adaptive 20 questions scheme. Moreover, the achievable
MSE exponent is larger than that of random block coding, which provides equal error protection for every information bit.
There are several open directions worthy of further study related to our work. First, the idea of designing a non-adaptive
querying policy by using the UEP superposition coding can be applied to many other applications of data acquisition, possibly
with diverse channel models, source (target) distributions, and cost functions. In applying the idea of UEP querying to general
models of data acquisition, the important question is how to correctly assess the value (significance) of information bits that
we try to extract by querying. For example, when a continuos random source, which we try to estimate, is not uniformly
distributed over [0, 1], we need to first find the optimal quantization levels and the corresponding reproduction points with
finite number of bits. Depending on the quantization levels and cost function, the significance of those information bits might
be varying. We need to measure the correct value of those bits in estimating the target variable and design a UEP querying
policy to provide different levels of error protection depending on the value of those information bits.
Second, the proposed UEP querying policy based on superposition coding can be generalized to provide more than two levels
of error protection. This generalization may also improve the achievable estimation error since the resulting UEP querying policy

22

would be able to use a fixed querying resource more efficiently by providing finer levels of error protection for information
bits of different significance, compared to the two-level case we considered in this paper. Showing the improved performance,
however, might require more complicated analysis on the error exponents of each of the partial messages. This generalization
might also require development of more efficient decoding algorithms for the superposition codes. In our work, we mainly used
successive-cancellation decoding rule, which is a sub-optimal decoding rule that successively decodes the two partial messages,
public message (MSBs) and private message (LSBs). Compared to the optimal maximum-likelihood decoding for each of the
partial messages, the successive-cancellation decoding is computationally more efficient and also easier to analyze. But when
the number of levels of error protection and the corresponding number of partial messages are increased, the performance of
the successive-cancellation decoding might become worse than the two-level case, since the decoding error of the previous
stage might keep propagating to all the later stages. Therefore, we need to develop another type of decoding rule to overcome
this kind of challenge.
A PPENDIX A
P ROOF OF P ROPOSITION 1: A DAPTIVE B ISECTION P OLICY
Successive-entropy-minimization policies choose the most informative querying region Qi , which asks one bit of information
about the target variable X at each round, by satisfying
Pr(X ∈ Qi |Y1i−1 = y1i−1 ) = Pr(X ∈
/ Qi |Y1i−1 = y1i−1 ) = 1/2

(74)

for answers y1i−1 ∈ {0, 1}i−1 to previous queries. For a continuous random variable X ∼ p(x|y1i−1 ), there exist diverse ways
to design such a querying region Qi satisfying the condition (74).
We quantify the value of the resulting observation Yi by the predicted variance reduction, defined as
Var(X|Y1i−1 = y1i−1 ) − E[Var(X|Yi , Y1i−1 = y1i−1 )].

(75)

Note that E[Var(X|Yi , Y1i−1 = y1i−1 )] depends on the choice of Qi since the two possible posterior distributions of X,
p(x|yi = 0, y1i−1 ) and p(x|yi = 1, y1i−1 ), after the i-th querying, are functions of the choice of Qi . The objective is to find the
querying region Qi that not only satisfies (74) but also maximizes the predicted variance reduction (75). We aim to solve

max Var(X|Y1i−1 = y1i−1 ) − E[Var(X|Yi , Y1i−1 = y1i−1 )] .
(76)
Qi ∈A

Q|Y1i−1

where A = {Q : Pr(X ∈
= y1i−1 ) = Pr(X ∈
/ Q|Y1i−1 = y1i−1 ) = 1/2}. Proposition 1 states that the optimal Qi that
is the solution of the optimization (76) is the querying region that corresponds to the bisection policy, i.e., the optimal Qi is
right region of the median of p(x|y1i−1 ).
For adaptive sequential querying, given answers y1i−1 to the previous queries (Q1 , . . . , Qi−1 ) we denote the updated posterior
distribution p(x|y1i−1 ) of X by q(x) := p(x|y1i−1 ). Define a one-step encoding map d : [0, 1] → {0, 1} that maps the value
of x ∈ [0, 1] to a binary bit Z = d(x). This encoding map d(·) is defined as the indicator function of the event X ∈ Q, i.e.,
d(x) = 1 for every x ∈ Q and d(x) = 0 for every x ∈
/ Q. We derive the optimal one-step encoding map d(·) that maximally
reduces the conditional variance of X ∼ q(x) given the noisy answer Y = Z ⊕ N where N ∼ Bernoulli().
The conditional variance of X given Y can be written as
E[Var(X|Y )]
= Pr(Y = 0)Var(X|Y = 0) + Pr(Y = 1)Var(X|Y = 1)




2
2
= Pr(Y = 0) E[X 2 |Y = 0] − (E[X|Y = 0]) + Pr(Y = 1) E[X 2 |Y = 1] − (E[X|Y = 1])


2
2
= E[X 2 ] − Pr(Y = 0) (E[X|Y = 0]) + Pr(Y = 1) (E[X|Y = 1]) .

(77)

Since E[X 2 ] does not depend on the encoding map d(·), to minimize E[Var(X|Y )] the encoding map d(·) should maximize
2

2

Gd := Pr(Y = 0) (E[X|Y = 0]) + Pr(Y = 1) (E[X|Y = 1]) .

(78)

After applying Bayes’ rule, Gd in (78) can be expressed in terms of the probabilities {Pr(Z = 0), Pr(Z = 1)} and the
conditional expectations {E[X|Z = 0] = E[X|X ∈ Q], E[X|Z = 1] = E[X|X ∈
/ Q]} as
Gd =

1
2
((1 − ) · Pr(Z = 0)E[X|Z = 0] +  · Pr(Z = 1)E[X|Z = 1])
Pr(Y = 0)
1
2
+
( · Pr(Z = 0)E[X|Z = 0] + (1 − ) · Pr(Z = 1)E[X|Z = 1]) .
Pr(Y = 1)

(79)

23

Note that both of {Pr(Z = 0), Pr(Z = 1)} and {E[X|Z = 0], E[X|Z = 1]} depend on the encoding map d(·) as
Z
Pr(Z = 0) = Pr(X ∈
/ Qi ) =
q(x)dx,
d(x)=0
Z
Pr(Z = 1) = Pr(X ∈ Qi ) =
q(x)dx,
d(x)=1
Z
1
E[X|Z = a] =
xq(x)dx, for a = 0, 1.
Pr(Z = a) d(x)=a

(80)
(81)
(82)

When m denotes the mean of X ∼ q(x), {Pr(Z = 0), Pr(Z = 1)} and {E[X|Z = 0], E[X|Z = 1]} should satisfy
m = E[X] = Pr(Z = 0)E[X|Z = 0] + Pr(Z = 1)E[X|Z = 1].

(83)

We show that among encoding maps d(·) with a fixed {Pr(Z = 0), Pr(Z = 1)} the encoding map that maximizes Gd in (79),
which thus minimizes E[Var(X|Y )], under the constraint of (83) should be a step function.
Lemma 7: Among encoding maps d : [0, 1] → {0, 1} with a fixed {Pr(Z = 0), Pr(Z = 1)}, the optimal encoding map that
maximizes Gd in (78) under the constraint of (83) should maximize |E[X|Z = 0] − m|. For a fixed Pr(Z = 0), in order to
maximize |E[X|Z = 0] − m| the optimal encoding map d : [0, 1] → {0, 1} should be either
(
0 x ≤ t1
d(x) =
(84)
1 x > t1
Rt
for the threshold t1 such that 0 1 q(x)dx = Pr(Z = 0), or
(
1 x ≤ t2
d(x) =
(85)
0 x > t2
R1
for the threshold t2 such that t2 q(x)dx = Pr(Z = 0).
Proof: Let us define β := Pr(Z = 0) and Aβ := E[X|Z = 0] for a fixed 0 ≤ β ≤ 1. From the constraints in (83), it
becomes Pr(Z = 1)E[X|Z = 1] = m − βAβ . By using these parameters, we can rewrite Gd in (79) as
2

Gd =

(βAβ + (1 − )(m − βAβ ))
((1 − )βAβ + (m − βAβ ))
+
 + (1 − 2)β
(1 − ) − (1 − 2)β

2

(86)

By rearranging terms in the numerator and denominator of Gd , we can simply Gd as
(1 − 2)2 β 2 (Aβ − m)2
+ m2 .
(1 − ) + (1 − 2)2 β(1 − β)

(87)

Pr(Z = 0) = Pr(Z = 1) = 1/2.

(88)

Gd =

Therefore, for a fixed (β, , m), Gd is maximized when Aβ is as far as possible from the mean m = E[X] of X ∼ q(x). For
a fixed β = Pr(Z = 0), the optimal encoding map d : [0, 1] → {0, 1} that maximizes |Aβ − m| = |E[X|Z = 0] − m| should
be a step function of either (84) or (85).
For successive-entropy-minimization strategies that query one bit of information about the target variable X ∼ q(x) at each
round, the probabilities of the event {Z = 0} and of {Z = 1} are balanced as
The thresholds of the two step functions (84) and (85) for this case become the same as the median of the distribution. Lemma 7
thus implies that among policies satisfying (88), the adaptive bisection policy is the optimal one-step policy that minimizes
the conditional variance of X given a noisy answer Y .
A PPENDIX B
P ROOF OF L EMMA 2: B IT-E RROR P ROBABILITY WITH R EPETITION C ODING
In Lemma 2, we show that when a binary bit Bi ∼ Bernoulli(1/2) is repeatedly transmitted through a BSC() by Ni times,
the decoding-error probability of Bi with the majority voting algorithm is bounded below and above as
e−1/(3Ni ) −Ni DB (1/2k)
√
e
≤ Pr(B̂i 6= Bi ) ≤ e−Ni DB (1/2k) .
2πNi

(89)

We first prove the upper bound. For bit Bi repeatedly queried Ni times, denote the corresponding channel outputs by
(Y1 , . . . , YNi ) ∈ {0, 1}Ni and define Yj0 = 2Yj − 1 ∈ {−1, 1}. The majority voting claims an estimate B̂i = 1 when

24

PNi
Yj0 ≤ 0. Since the channel is symmetric and Bi ∼ Bernoulli(1/2), the bit error
Yj0 > 0, and B̂i = 0 when j=1
probability can be bounded above as

PNi

j=1

Pr(B̂i 6= Bi )




Ni
Ni
X
X
1
1
= Pr 
Yj0 > 0 Bi = 0 + Pr 
Yj0 ≤ 0 Bi = 1
2
2
j=1
j=1


Ni
X
≤ Pr 
Yj0 ≤ 0 Bi = 1

(90)

j=1


PNi
0
= Pr e−λ j=1 Yj ≥ 1 Bi = 1 , for λ > 0
h
i
PNi
0
≤ E e−λ j=1 Yj Bi = 1 ,


where the last inequality is from the Markov’s inequality.
Using the conditional independence of Y10 , . . . , YN0 i given Bi = 1 and the fact that Pr(Yj0 = 1|Bi = 1) = 1 −  and
Pr(Yj0 = −1|Bi = 1) = ,
Ni
h
h
i Y
i
PNi
0
0
E e−λ j=1 Yj Bi = 1 =
E e−λYj Bi = 1
j=1

=

Ni
Y
j=1

(91)

(1 − )e−λ +  · eλ .

q

p

−λ
+  · eλ is minimized as 2 (1 − ) = e−DB (1/2k) . Therefore, the bit-error
When λ = ln 1−
 , the term (1 − )e
probability can be bounded above as


Ni
Y

(1 − )e−λ +  · eλ 
Pr(B̂i 6= Bi ) ≤ min 
λ
(92)
j=1
= e−Ni DB (1/2k) .
We next prove the lower bound in (89). The bit error probability can be bounded below as


Ni
X
1
Pr(B̂i 6= Bi ) ≥ Pr 
Yj0 = 0 Bi = 1 ,
2
j=1

(93)

P

Ni
0
where Pr
j=1 Yj = 0 Bi = 1 is the probability of the event that a half of the transmitted bits are flipped by the channel
noise, which is distributed by Bernoulli() distribution. This probability is bounded below as


Ni
X
Pr 
Yj0 = 0 Bi = 1
j=1




Ni
Ni /2 (1 − )Ni /2
Ni /2
r
2 −1/(3Ni ) Ni Ni /2
e
2 
(1 − )Ni /2
≥
πNi
r
2 −1/(3Ni ) −Ni DB (1/2k)
=
e
e
πNi

=

(94)

where the middle inequality is from the Stirling bound. By plugging this lower bound into (93), we obtain
e−1/(3Ni ) −Ni DB (1/2k)
Pr(B̂i 6= Bi ) ≥ √
e
.
2πNi

(95)

25

A PPENDIX C
P ROOF OF L EMMA 4: QUANTIZED -MSE EXPONENT WITH R ANDOM B LOCK C ODING
In Lemma 4, we show that the best achievable quantized-MSE exponent with the random block codes of rate R is
∗
Eq,rc
(R) = Er (R)

(96)

for Er (R) in (40). The achievability of (96) was shown by the bound (42). In this section we prove the converse, i.e., the
quantized-MSE exponent with the random block codes of rate R cannot be better than Er (R). We prove this by providing a
lower bound on the quantized MSE.
Consider the quantized MSE expanded in terms of the conditional bit-error probabilities.
E[cq (X, X̂N,finite )]
k 

X
=
Pr(B̂i 6= Bi , B̂1i−1 = B1i−1 )E[cq (X, X̂N,finite ) B̂i 6= Bi , B̂1i−1 = B1i−1 ] .

(97)

i=1

.
Since Pr(M̂ = M ) → 1 as N → ∞ for the random block codes of rate R ∈ (0, C), we know that Pr(B̂1i = B1i ) = 1 for any
i = 1, . . . , k. Therefore, we can write E[cq (X, X̂N,finite )] as
E[cq (X, X̂N,finite )]
k 

. X
=
Pr(B̂i 6= Bi |B̂1i−1 = B1i−1 )E[cq (X, X̂N,finite ) B̂i 6= Bi , B̂1i−1 = B1i−1 ] .

(98)

i=1

We then show that the first term of the summation in the right-hand side is
˙ −N Er (R) ,
Pr(B̂1 6= B1 )E[cq (X, X̂N,finite )|B̂1 6= B1 ]≥e
for the random coding error exponent Er (R).
Note that
Pr(B̂1 6= B1 ) ≤ Pr(M̂ 6= M ) ≤

k
X
i=1

Pr(B̂i 6= Bi ).

(99)

(100)

The average bit error probability Pr(B̂i 6= Bi ) for the random block codes is the same for every i ∈ {1, . . . , k} from the
symmetry of encoding process for the information bits {Bi }. Since k = N R/ ln 2 increases linearly in N , the exponent of
.
.
Pr(B̂1 6= B1 ) is the same as that of Pr(M̂ 6= M ) = e−N Er (R) , i.e., Pr(B̂1 6= B1 ) = e−N Er (R) . Moreover,
.
E[cq (X, X̂N,finite )|B̂1 6= B1 ] = 1.
(101)
This can be shown by calculating a lower bound on E[cq (X, X̂N,finite )|B̂1 6= B1 ]. When B̂1 = 1 and B1 = 0, the best X̂N
that minimizes the conditional expectation is X̂N = 1/2. Conditioned on B1 = 0, X is uniformly distributed over [0, 1/2],
and thus
Z 1/2
(102)
E[cq (X, X̂N )|B̂1 = 1, B1 = 0] ≥
2(x − 1/2)2 dx = 1/12.
0

The same bound also holds when B̂1 = 0 and B1 = 1. From this lower bound on E[cq (X, X̂N )|B̂1 = 1, B1 = 0] and the bit
.
error probability Pr(B̂1 6= B1 ) = e−N Er (R) , the lower bound in (99) can be proven. From the bound (99) and the expansion
on E[cq (X, X̂N,finite )] in (98), we can conclude that
˙ −N Er (R) .
E[cq (X, X̂N,finite )]≥e

(103)

A PPENDIX D
P ROOFS OF L EMMA 5: DECODING - ERROR EXPONENTS OF PARTIAL M ESSAGES E NCODED BY S UPERPOSITION C ODING
In Lemma 5, we show that superposition coding provides a better, or at least as good, error protection for the more important
partial message M1 (MSBs) than that of the random block coding. We provide two lower bounds EMSBs,JML (R1 , R2 ) and
∗
EMSBs,SC (R1 , α) on the best achievable error exponent EMSBs
(R1 , R2 , α) and prove that these exponents are larger than the
best achievable exponent Er (R1 + R2 ) of random block coding.
The first lower bound EMSBs,JML (R1 , R2 ) is defined as the best achievable error exponent for Pr(M̂1 6= M1 ) with jointmaximum-likelihood (JML) decoding rule for superposition coding. We show that EMSBs,JML (R1 , R2 ) ≥ Er (R1 + R2 ) for
every (R1 , R2 , α) in the following lemma.

26

Er (R)
EMSBs,SC (R1 , ↵) at R2 = 2C2 (↵)/3

E0 (1/2, ✏)

E0 (1/2, ↵ ⇤ ✏)

R2,th (↵, ✏)

R1,th (R2 , ↵, ✏)

R2

R = R1 + R2

Fig. 12. A plot of error exponents Er (R1 + R2 ) (solid line) and EMSBs,SC (R1 , α) (dash-dot line) for the more important partial message M1 (MSBs) with
random block coding and with superposition coding, respectively, where  = 0.45, α = 0.11, and R2 = 2C2 (α)/3. The error exponent EMSBs,SC (R1 , α)
of superposition coding is strictly larger than that of the random block coding Er (R1 , R2 ) over R1 ∈ (0, R1,th (R2 , α, )) for a fixed R2 = 2C2 (α)/3 >
R2,th (α, ).

Lemma 8: For a given (R1 , R2 , α), the best achievable error exponent EMSBs,JML (R1 , R2 ) with joint-ML decoding rule for
superposition coding is bounded below as
LB
EMSBs,JML (R1 , R2 ) ≥ EMSBs,JML
(R1 , R2 )

(104)

where
(
LB
EMSBs,JML
(R1 , R2 )

=

E0 (1/2, ) − R2 − R1 , R1 ≤ max{0, Rcrit () − R2 },
DB (γGV (R1 + R2 )k), max{0, Rcrit () − R2 } < R1 ≤ HB (1/2) − HB () − R2 .

(105)

Proof: Appendix F
LB
Note that for any given (R1 , R2 , α) the achievable exponent EMSBs,JML
(R1 , R2 ) is equal to Er (R1 + R2 ) in (40). Since the
LB
joint-maximum-likelihood decoding is a sub-optimal decoding rule, the fact that EMSBs,JML (R1 , R2 ) ≥ EMSBs,JML
(R1 , R2 ) =
Er (R1 + R2 ) implies that the superposition coding provides a better, or at least as good, error protection for the partial message
M1 than that of the random block coding for every (R1 , R2 ), regardless of the choice of α ∈ (0, 1/2).
∗
We next prove a strictly positive gain in the error exponent EMSBs
(R1 , R2 , α) of superposition coding, by providing another
∗
lower bound EMSBs,SC (R1 , α) on EMSBs (R1 , R2 , α). The exponent EMSBs,SC (R1 , α) is the best achievable error exponent with
successive-cancellation (SC) decoding. As shown in Eq. (54), the exponent can be written as
(
E0 (1/2, α ∗ ) − R1 , 0 ≤ R1 ≤ Rcrit (α ∗ ),
EMSBs,SC (R1 , α) =
(106)
DB (γGV (R1 )kα ∗ ), Rcrit (α ∗ ) < R1 ≤ C − C2 (α),
p
√
√
where E0 (a, b) = − ln(1 − 2a(1 − a)( b − 1 − b)2 ) and thus E0 (1/2, α ∗ ) = − ln(1/2 + (α ∗ )(1 −
(α ∗ ))), C =
√
√
HB (1/2) − HB (), C2 (α) = HB (α ∗ ) − HB (), Rcrit (α ∗ ) = DB (γcrit (α ∗ )k1/2) and γcrit (α ∗ ) = √α∗+α∗
.
1−α∗
By comparing EMSBs,SC (R1 , α) in (106) with the error exponent Er (R1 + R2 ) in (40) of random block coding, we show
that for a sufficiently large R2 and sufficiently small R1 superposition coding provides a strictly better error protection for
the partial message M1 than does random block coding. More precisely, for a given α ∈ (0, 1/2) and a fixed  ∈ (0, 1/2),
we find thresholds R2,th (α, ) on R2 and R1,th (R2 , α, ) on R1 such that when R2,th (α, ) < R2 < C2 (α) and 0 ≤ R1 <
R1,th (R2 , α, ), it is guaranteed that
EMSBs,SC (R1 , α) > Er (R1 + R2 ).
(107)
The threshold on R2 , denoted R2,th (α, ), is defined as the rate R at which the random-coding error exponent Er (R) equals
the error exponent EMSBs,SC (0, α) = E0 (1/2, α ∗ ) of superposition coding at R1 = 0. For a fixed rate R2 > R2,th (α, ),
the threshold on R1 denoted R1,th (R2 , α, ), is defined as the minimum rate R1 where the error exponent EMSBs,SC (R1 , α) of
superposition coding equals the random-coding error exponent Er (R1 +R2 ). There always exists such a threshold R1,th (R2 , α, )
in the range [0, C −R2 ] since both EMSBs,SC (R1 , α) and Er (R1 +R2 ) keeps decreasing as R1 increases and EMSBs,SC (R1 , α) >
Er (R1 +R2 ) at R1 = 0 and EMSBs,SC (R1 , α) = Er (R1 +R2 ) as R1 approaches to C −R2 . In Fig. 12, we plot EMSBs,SC (R1 , α)
(dash-dot line) and Er (R1 + R2 ) (solid line) for α = 0.11,  = 0.45 and R2 = 2C2 (α)/3 > R2,th (α, ). From the plot, we
can observe a gain in the error exponent of Pr(M̂1 6= M1 ) from superposition coding for every 0 ≤ R1 ≤ R1,th (R2 , α, ) at

27

a fixed R2 = 2C2 (α)/3 > R2,th (α, ). From the plot, we can also see how the thresholds R2,th (α, ) and R1,th (R2 , α, ) are
determined for this particular example.
Lastly, we state a lower bound on the error exponent ELSBs,SC (R2 , α) of Pr(M̂2 6= M2 |M̂1 = M1 ) with successivecancellation decoding rule for superposition coding. This result was provided in [20]:
ELSBs,SC (R2 , α) := max [F0 (ρ, α) − ρR2 ]

(108)



1+ρ 


 X

X
1

F0 (ρ, α) = − ln
pV (v)pY |V (y|v) 1+ρ 


y∈{0,1} v∈{0,1}


(109)

0≤ρ≤1

where

for pV (v) being Bernoulli(α) distribution and pY |V (y|v) being the transition probability of BSC(). We can show that
ELSBs,SC (R2 , α) > 0 for R2 < C2 (α) where C2 (α) is equal to
C2 (α) =

∂F0 (ρ, α)
∂ρ

ρ=0

= HB (α ∗ ) − HB ().

(110)

Note that as α decreases from 1/2 to 0, the maximum rate C2 (α) of the less important partial message M2 (LSBs) keeps
decreasing.
A PPENDIX E
P ROOF OF L EMMA 6: G AIN IN THE DECODING - ERROR EXPONENT OF MSB S FROM S UPERPOSITION C ODING FOR A V ERY
N OISY BSC()
In Lemma 6, we show that for a very noisy BSC() with  = 1/2 − δ for a sufficiently small δ > 0, superposition coding
achieves a strictly positive gain in the error exponent of Pr(M̂1 6= M1 ) for every rate R1 ∈ (0, C − C2 (α)) of the more
important message M1 (MSBs) compared to that of random block coding, when the rate R2 of the less important message
M2 (LSBs) equals the maximum rate C2 (α) = HB (α ∗ ) − HB () for a fixed parameter α ∈ (0, 1/2) of superposition coding.
When we fix R2 = C2 (α), the best achievable Pr(M̂1 6= M1 ) of random block coding at a rate R1 ∈ [0, C − C2 (α)] is
.
Pr(M̂1 6= M1 ) = e−N Er (R1 +R2 )
(111)
where
(
Er (R1 + R2 ) =

E0 (1/2, ) − C2 (α) − R1 , 0 ≤ R1 ≤ max{0, Rcrit () − C2 (α)},
DB (γGV (R1 + C2 (α))k), max{0, Rcrit () − C2 (α)} < R1 ≤ C − C2 (α),

(112)

p
for E0 (1/2, ) = ln 2−ln(1+2
(1 − )), C = HB (1/2)−HB (), C2 (α) = HB (α∗)−HB () and Rcrit () = DB (γcrit ()k1/2)
√

√
√
where γcrit () = + 1− .
With superposition coding and successive cancellation (SC) decoding, we can achieve
˙ −N EMSBs,SC (R1 ,α)
Pr(M̂1 6= M1 )≤e

(113)

E0 (1/2, α ∗ ) − R1 , 0 ≤ R1 ≤ Rcrit (α ∗ ),
DB (γGV (R1 )kα ∗ ), Rcrit (α ∗ ) < R1 ≤ C − C2 (α),

(114)

where
(
EMSBs,SC (R1 , α) =

for the Gilbert-Varshamov distance γG (R) ∈ [0, 1/2] that is defined as DB (γGV (R)k1/2) = R.
To prove that EMSBs,SC (R1 , α) > Er (R1 + R2 ) for every R1 ∈ [0, C − C2 (α)) at R2 = C2 (α), we need to demonstrate the
following three statements for  ≈ 0.5 at every α ∈ (0, 1/2),
1) E0 (1/2, α ∗ ) > E0 (1/2, ) − C2 (α).
2) E0 (1/2, α ∗ ) − R1 > DB (γGV (R1 + C2 (α))k) for 0 ≤ R1 ≤ Rcrit (α ∗ ) when Rcrit () < C2 (α).
3) DB (γGV (R1 )kα ∗ ) > DB (γGV (R1 + C2 (α))k) for Rcrit (α ∗ ) < R1 < C − C2 (α).
Once these three statements are proven, it is sufficient to show that EMSBs,SC (R1 , α) > Er (R1 + R2 ) for every 0 ≤ R1 ≤
C − C2 (α) when R2 = C2 (α).
The first statement 1) E0 (1/2, α ∗ ) > E0 (1/2, ) − C2 (α) is equivalent to
√
√
√
√
(115)
HB (α ∗ ) − ln( α ∗  + 1 − α ∗ )2 > HB () − ln(  + 1 − )2 .
√
√
When we define f (x) = HB (x) − ln( x + 1 − x)2 , the above inequality is equivalent to f (α ∗ ) − f () > 0. Note that
0 ≤  < α ∗  ≤ 1/2 for every α ∈ (0, 1/2). Moreover, the derivative of f (x) is positive in the regime of 0.05 ≤ x ≤ 1/2.
Therefore, for a BSC() with  ≥ 0.05, the statement 1) E0 (1/2, α ∗ ) > E0 (1/2, ) − C2 (α) is true.

28

We next prove the statement 3) DB (γGV (R1 )kα ∗ ) > DB (γGV (R1 + C2 (α))k) for Rcrit (α ∗ ) < R1 < C − C2 (α) =
HB (1/2) − HB (α ∗ ), which will also be used to prove the statement 2) later. First, note that at R1 = HB (1/2) − HB (α ∗ ),
DB (γGV (R1 )kα ∗ ) = DB (γGV (R1 + C2 (α))k) = 0 from the definition of γGV (R). We will prove that DB (γGV (R1 )kα ∗
) − DB (γGV (R1 + C2 (α))k) strictly decreases in R1 ∈ (Rcrit (α ∗ ), HB (1/2) − HB (α ∗ )]. Since DB (γGV (R1 )kα ∗ ) =
DB (γGV (R1 + C2 (α)k) = 0 at R1 = HB (1/2) − HB (α ∗ ), the fact that the difference between the two divergences strictly
decreases implies the statemenet 3). To show that DB (γGV (R1 )kα ∗ ) − DB (γGV (R1 + C2 (α))k) keeps decreasing as R1
increases, we will show that
∂
∂
DB (γGV (R1 )kα ∗ ) <
DB (γGV (R1 + C2 (α))k).
(116)
∂R1
∂R1
From the definition of γGV (R), it satisfies ln 2 + γGV (R) ln γGV (R) + (1 − γGV (R)) ln(1 − γGV (R)) = R. By differentiating
both sides by γGV (R) and re-arranging the terms, we get
∂γGV (R)
1
= − 1−γ (R) .
GV
∂R
ln

(117)

γGV (R)

From

∂
∂x DB (xky)

= ln



x 1−y
1−x y



and (117), we have

ln 1−α∗
∂
DB (γGV (R1 )kα ∗ ) = 1 − 1−γα∗(R ) ,
∂R1
ln γGVGV(R1 )1
ln 1−
∂
DB (γGV (R1 + C2 (α))k) = 1 − 1−γ (R +C (α)) .
1
2
∂R1
ln γGVGV(R1 +C
2 (α))

(118)

Therefore, showing (116) is equivalent to showing
GV (R1 +C2 (α))
ln 1−γ
ln 1−
γGV (R1 +C2 (α))

.
<
GV (R1 )
ln 1−α∗
ln 1−γ
α∗
γGV (R1 )

(119)

To prove this inequality, we will first show that
γGV (R1 ) − γGV (R1 + C2 (α)) ≥ α ∗  − 

(120)

Note that α ∗  = γGV (HB (1/2) − HB (α ∗ )) and  = γGV (HB (1/2) − HB ()). Therefore, (120) can be written as
γGV (R1 ) − γGV (R1 + C2 (α)) ≥ γGV (HB (1/2) − HB (α ∗ )) − γGV (HB (1/2) − HB ()).

(121)

Note that γGV (R) ∈ [0, 1/2] is convex and decreasing in R ≥ 0. Moreover, we know that (HB (1/2) − HB ()) − (HB (1/2) −
HB (α ∗ )) = C2 (α). Since we consider the regime where R1 ≤ HB (1/2) − HB (α ∗ ), from the convexity of γGV (R),
the inequality in (121) can be implied. Again, since α ∗  −  = γGV (HB (1/2) − HB (α ∗ )) − γGV (HB (1/2) − HB ()), for
c := α ∗  − , we have γGV (R1 + C2 (α)) ≤ γGV (R1 ) − c ≤ 1/2 from (121).
Since ln 1−x
x is decreasing in 0 ≤ x ≤ 1/2 and γGV (R1 + C2 (α)) ≤ γGV (R1 ) − c ≤ 1/2, we have
GV (R1 )−c)
ln 1−(γ
(γGV (R1 )−c)
GV (R1 )
ln 1−γ
γGV (R1 )

≤

GV (R1 +C2 (α))
ln 1−γ
γGV (R1 +C2 (α))
GV (R1 )
ln 1−γ
γGV (R1 )

.

(122)

Therefore, to prove (119), it is sufficient to show that
GV (R1 )−c)
ln 1−(γ
ln 1−
(γGV (R1 )−c)

.
<
GV (R1 )
ln 1−α∗
ln 1−γ
α∗
γGV (R1 )

(123)

Since α ∗  < γGV (R1 ) and  = α ∗  − c, if we can prove that

ln 1−(x−c)
(x−c)
ln 1−x
x

(124)

is increasing in x ∈ [α ∗ , 1/2], the inequality in (123) holds. We will prove this by showing that the derivative of (124) in x
is positive for a very noisy BSC() with  ≈ 1/2. The derivative of (124) is positive iff
−1
1−x
1
1 − (x − c)
ln
+
ln
> 0.
(x − c)(1 − (x − c))
x
x(1 − x)
(x − c)

(125)

29

From α ∗  =  + α(1 − 2), when  ≈ 1/2 it is implied that c = α ∗  −  ≈ 0 and α ∗  ≈ 1/2. Therefore, in the regime of
α ∗  ≤ x ≤ 1/2, c/x ≈ 0 and c/(1 − x) ≈ 0. In this regime, we can approximate the terms in the left-hand side of (125) as


c
(1
−
x)
1
+
1−x
1 − (x − c)
1−x
c
c

ln
= ln
= ln
+
+ + O(c2 ),
(126)
(x − c)
x
1−x x
x 1 − xc


−1
−1
−1
1
c(1 − 2x)
2


=
=
1
+
+
O(c
)
.
(127)
(x − c)(1 − (x − c))
x(1 − x) 1 − c  1 + c
x(1 − x)
x(1 − x)
x

1−x

By plugging these approximations, the left-hand side of (125) is approximated as


1−x
c
1 − (1 − 2x) ln
+ O(c2 ).
x2 (1 − x)2
x

(128)

Since 0 < (1 − 2x) ln 1−x
x  1 for x = 1/2 − δ for an arbitrarily small δ > 0, it can be shown that (128) is positive. This
implies that (125) is valid for the very noisy channel, and thus (123) is true. This concludes the proof for the statement 3)
DB (γGV (R1 )kα ∗ ) > DB (γGV (R1 + C2 (α))k) for Rcrit (α ∗ ) < R1 < C − C2 (α) = HB (1/2) − HB (α ∗ ).
Lastly, we prove the statement 2) E0 (1/2, α ∗ ) − R1 > DB (γGV (R1 + C2 (α))k) for 0 ≤ R1 ≤ Rcrit (α ∗ ) when
Rcrit () < C2 (α). Statement 3) implies that at R1 = Rcrit (α ∗ ), E0 (1/2, α ∗ ) − R1 > DB (γGV (R1 + C2 (α)k), since
E0 (1/2, α∗)−R1 = DB (γGV (R1 )kα∗) at R1 = Rcrit (α∗). When Rcrit () < C2 (α), the derivative of DB (γGV (R1 +C2 (α))
in R1 ∈ [0, Rcrit (α ∗ )] is
∂
DB (γGV (R1 + C2 (α))k) ≤ 0.
(129)
−1<
∂R1
∂
(E0 (1/2, α ∗)−R1 ) = −1. Since (E0 (1/2, α ∗)−R1 )
On the other hand, the derivative of (E0 (1/2, α ∗)−R1 ) in R1 is ∂R
1
decreases faster than DB (γGV (R1 + C2 (α))k) in R1 ∈ [0, Rcrit (α ∗ )], while (E0 (1/2, α ∗ ) − R1 ) is still greater than
DB (γGV (R1 + C2 (α))k) at R1 = Rcrit (α ∗ ), it is implied that

E0 (1/2, α ∗ ) − R1 > DB (γGV (R1 + C2 (α))k)

(130)

in R1 ∈ [0, Rcrit (α ∗ )].
We proved the three statements 1), 2) and 3), and these three statements imply the Lemma 6.
A PPENDIX F
P ROOF OF L EMMA 8: A L OWER B OUND ON THE DECODING - ERROR EXPONENT OF THE M ORE I MPORTANT PARTIAL
M ESSAGE WITH J OINT-ML D ECODING RULE FOR S UPERPOSITION C ODING
In Lemma 8, we show that the decoding-error exponent EMSBs,JML (R1 , R2 ) of the more important partial message M1
(MSBs) with joint-ML decoding rule for superposition coding is bounded below as
LB
EMSBs,JML (R1 , R2 ) ≥ EMSBs,JML
(R1 , R2 )

(131)

where
(
LB
EMSBs,JML
(R1 , R2 ) =

E0 (1/2, ) − R2 − R1 , R1 ≤ max{0, Rcrit () − R2 },
DB (γGV (R1 + R2 )k), max{0, Rcrit () − R2 } < R1 ≤ HB (1/2) − HB () − R2 .

(132)

In this section, we prove this lemma.
Consider superposition codes composed of codewords {z(m1 ,m2 ) }, m1 ∈ {0, . . . , eN R1 −1}, m2 ∈ {0, . . . , eN R2 −1}, where
(m1 ,m2 )
z
= u(m1 ) ⊕ v(m2 ) and u(m1 ) consists of N i.i.d. symbols of Bernoulli(1/2) distribution and v(m2 ) of Bernoulli(α)
distribution for α ∈ (0, 1/2). Without loss of generality, we suppose that z(0,0) is the correct codeword, which is transmitted
by N uses of a BSC(), and analyze the decoding-error probability of m1 = 0. Given the received word y = z(0,0) ⊕ n, the
joint maximum likelihood decoding rule finds a unique codeword z(m̂1 ,m̂2 ) that is closest to y. When we denote the decoded
message as (m̂1 , m̂2 ), the decoding error happens only when m̂1 6= 0, regardless of whether or not m̂2 = 0.
The decoding-error event of the partial message M1 , denoted EJML , occurs if there exists a codeword z(m1 ,m2 ) with m1 6= 0
whose distance from y is less than or equal to the minimum of all distances between y and z(m1 ,m2 ) for m1 = 0, i.e., when
the minimum distance between y and any incorrect codeword z(m1 ,m2 ) with m1 6= 0 is N δ and the minimum distance between
y and any codeword z(m1 ,m2 ) with m1 = 0 is N τ , the decoding error occurs for the event EJML = {δ ≤ τ }.
Because only the distances of codewords from y matter, we consider the “output-centered analysis” proposed in [16] where
all codewords are translated by y. Let w(m1 ,m2 ) = z(m1 ,m2 ) ⊕ y = z(m1 ,m2 ) ⊕ z(0,0) ⊕ n denote the translated codewords.
For the correct (m1 , m2 ) = (0, 0), the translated codeword w(0,0) is equal to the channel noise word n and is independent
of y. The set of translated codewords for m1 = 0, w(0,m2 ) = v(m2 ) ⊕ v(0) ⊕ n, are independent of y but dependent on n.
Moreover, {w(0,m2 ) }, m2 ∈ {0, . . . , eN R2 − 1} are mutually dependent. The rest of the translated codewords with m1 6= 0,

30

i.e., {w(m1 ,m2 ) } for m1 ∈ {1, . . . , eN R1 − 1} and m2 ∈ {0, . . . , eN R2 − 1}, are independent of y, n, and {w(0,m2 ) } for
m2 ∈ {0, . . . , eN R2 − 1}. However, the codewords {w(m1 ,m2 ) }, m2 ∈ {0, . . . , eN R2 − 1}, for a fixed m1 are mutually
dependent. Lastly, all possible received words y are equiprobable: p(y) = 2−N . The probability distribution of the decoding
system consisting of the translated codewords and a received word y is thus decomposed as
p({w(0,m2 ) }, y, {w(m1 6=0,m2 ) }) = 2−N p({w(0,m2 ) })p({w(m1 6=0,m2 ) }).

(133)

Therefore, we can think of the whole decoding system as the one consisting of two independent subsystems, one comprising
the translated codewords with m1 = 0 and the other comprising the translated codewords with m1 6= 0. We analyze the
lower bound on the decoding-error probability of M1 with the joint-ML decoding rule by using the fact that {w(0,m2 ) } and
{w(m1 6=0,m2 ) } are independent.
The decoding-error event EJML occurs if the minimum weight N τ of {w(0,m2 ) } is greater than or equal to the minimum weight
N δ of {w(m1 6=0,m2 ) }, i.e., EJML = {δ ≤ τ }. Define an error event Eγ = {δ ≤ γ ≤ τ } for a fixed γ ∈ Γ = {γ : 0 ≤Pγ ≤ 1, N γ ∈
N0 } for the set N0 of non-negative integers. The decoding-error probability is equal to Pr(EJML ) = Pr(δ ≤ τ ) = γ∈Γ Pr(Eγ ).
We first analyze Pr(Eγ ) and then find the typical γ that dominates the exponentially decreasing rate of Pr(EJML ) in the
asymptotic regime.
From the independency between {w(0,m2 ) } and {w(m1 6=0,m2 ) },
Pr(Eγ ) = Pr(δ ≤ γ) Pr(τ ≥ γ).

(134)

We first establish an upper bound on Pr(δ ≤ γ). Note that N δ = min(m1 6=0,m2 )wH w(m1 ,m2 where wH (·) is the Hamming
weight of the sequence. We need to analyze the distribution of wH w(m1 6=0,m2 ) . Note that every symbol of every w(m1 6=0,m2)
is equiprobable. By the Chernoff exponent lemma, for γ < 1/2, the probability that the Hamming weight wH w(m1 6=0,m2 )
of a given incorrect codeword w(m1 6=0,m2 ) is less than or equal to N γ is


.
Pr wH (w(m1 6=0,m2 ) ) ≤ N γ = e−N DB (γk1/2) .
(135)
Since there are (eN R − eN R2 ) codewords with m1 6= 0, by the union bound


m1 6=0,m2
Pr(δ ≤ γ) = Pr
min wH (w
) ≤ Nγ
(m1 6=0,m2 )
(
−N (DB (γk1/2)−R)
, γ ≤ γGV (R),
˙ e
≤
1,
γ > γGV (R).


)

(136)

We next analyze Pr(τ ≥ γ) where τ = min(m1 =0,m2 ) wH (w(m1 ,m2 ) ). The translated correct codeword w(0,0) is equal to n
and is distributed by
p(n) = wH (n) (1 − )N −wH (n) .
(137)
Therefore, for γ > , by the Chernoff exponent lemma we have
.
Pr(wH (n) ≥ N γ) = e−N DB (γk) .
(138)

(m1 =0,m2 )
(m1 =0,m2 )
N R2
The event τ ≥ γ occurs when the Hamming weight wH w
of every codeword {w
, 0 ≤ m2 ≤ e
− 1}
is greater than or equal to N γ. Therefore, for  < γ < 1/2,


(m1 =0,m2 )
min wH (w
) ≥ Nγ
Pr(τ ≥ γ) = Pr
(m1 =0,m2 )
(139)
.
≤ Pr(wH (n) ≥ N γ) = e−N DB (γk) .

This bound may not be exponentially tight for 0 ≤ α < 1/2. However, when α = 1/2, since {w(0,m2 6=0) , n} are independent
to each other and every symbol of every w(0,m2 6=0) is independent and equiprobable, for  < γ < 1/2


.
Pr wH (w(0,m2 6=0) ) ≥ N γ = 1.
(140)
Therefore, for the case of α = 1/2, the upper bound in (139) becomes exponentially tight.
From (133), (135) and (139),
(
−N (DB (γk)+DB (γk1/2)−R)
,  < γ ≤ γGV (R),
˙ e
Pr(Eγ )≤
(141)
−N DB (γk)
e
,
γ > γGV (R).
P
By using this result, we calculate the achievable error exponent of Pr(EJML ) = γ∈Γ Pr(Eγ ) by finding γ that dominates
the exponentially decreasing rate of Pr(EJML ) as N increases. The resulting Pr(EJML ) is
(
−N (E0 (1/2,)−R)
, 0 ≤ R < Rcrit (),
˙ e
Pr(EJML )≤
(142)
−N DB (γGV (R)k)
e
, Rcrit () ≤ R < C,

31

p
√
√
where E0 (a, b) = − ln(1 − 2a(1 − √a)( b − 1 − b)2 ) and thus E0 (1/2, ) = ln 2 − ln(1 + 2 (1 − ). And, Rcrit () =
DB (γcrit ()k1/2) with γcrit () = √+√1− , and C = HB (1/2) − HB ().
Therefore, the best achievable error exponent EMSBs,JML (R1 , R2 ) with joint ML decoding for superposition coding of rates
LB
(R1 , R2 ) is bounded below as EMSBs,JML (R1 , R2 ) ≥ EMSBs,JML
(R1 , R2 ) where
LB
EMSBs,JML
(R1 , R2 ) =
(
E0 (1/2, ) − R2 − R1 , R1 < max{0, Rcrit () − R2 },
DB (γGV (R1 + R2 )k), max{0, Rcrit () − R2 } ≤ R1 < HB (1/2) − HB () − R2 .

(143)

A PPENDIX G
P ROOF OF T HEOREM 1: G AINS IN THE QUANTIZED -MSE EXPONENT FROM S UPERPOSITION C ODING
In Theorem 1, we show that for a very noisy BSC() with  = 0.5 − δ for a sufficiently small δ > 0, the best achievable
∗
∗
quantized-MSE exponent Eq,spc
(R) with superposition coding is strictly larger than that of random block coding Eq,rc
(R) for
∗
every rate R ∈ (E0 (1/2, )/3, C). Here we prove this theorem by finding a lower bound Eq,spc (R) on Eq,spc (R) and showing
∗
that this lower bound is strictly larger than Eq,rc
(R) at any rate R ∈ (E0 (1/2, )/3, C).
The quantized MSE E[cq (X, X̂N,finite )] can be bounded above in terms of decoding-error probabilities of the two partial
messages M1 (MSBs) and M2 (LSBs) as
E[cq (X, X̂N,finite )] ≤ Pr(M̂1 6= M1 ) + Pr(M̂2 6= M2 |M̂1 = M1 )e−2N R1 .

(144)

In Lemma 6, we show that successive-cancellation decoding rule for superposition codes of distribution parameter α ∈ (0, 1/2)
achieves Pr(M̂1 6= M1 ) such that
˙ −N EMSBs,SC (R1 ,α)
Pr(M̂1 6= M1 )≤e
(145)
where
(
E0 (1/2, α ∗ ) − R1 , 0 ≤ R1 ≤ Rcrit (α ∗ ),
EMSBs,SC (R1 , α) =
DB (γGV (R1 )kα ∗ ), Rcrit (α ∗ ) < R1 ≤ C − C2 (α).

(146)

By using this bound and the bound on the conditional decoding-error probability of M2 with the successive-cancellation
decoding,
˙ −N ELSBs,SC (R2 ,α) ,
Pr(M̂2 6= M2 |M̂1 = M1 )≤e
(147)
the quantized MSE with the superposition coding can be bounded above as
E[cq (X, X̂N,finite )]
≤ e−N EMSBs,SC (R1 ,α) + e−N ELSBs,SC (R2 ,α) e−2N R1
.
= e−N min{EMSBs,SC (R1 ,α),ELSBs,SC (R2 ,α)+2R1 } .
∗
Therefore, the best achievable quantized-MSE exponent Eq,spc
(R) with the superposition coding of rate R = R1 + R2 is
bounded below as
∗
Eq,spc
(R) ≥

max

{(R1 ,R2 ,α):
R1 +R2 =R,
α∈(0,1/2)}

∗
∗
min{EMSBs
(R1 , R2 , α), ELSBs
(R2 , α) + 2R1 }.

(148)

For a given α ∈ (0, 1/2), when we choose the rate R2 of the partial message M2 (LSBs) equal to C2 (α) = HB (α∗)−HB (),
which is the maximum possible rate of M2 to guarantee Pr(M̂2 6= M2 |M̂1 = M1 ) → 0 as N → ∞, the resulting error exponent
∗
ELSBs,SC (R2 , α) equals 0. This particular choice of R2 = C2 (α) provides a lower bound on Eq,spc
(R) such that
∗
Eq,spc
(R) ≥

max min{EMSBs,SC (R − C2 (α), α), 2(R − C2 (α))}.

α∈(0,1/2)

(149)

We next find α ∈ (0, 1/2) that maximizes min{EMSBs,SC (R − C2 (α), α), 2(R − C2 (α))}. More specifically, we find α that
makes
EMSBs,SC (R − C2 (α), α) = 2(R − C2 (α)).
(150)
For a very noisy BSC() with  ≈ 1/2, as shown in [17] (pp. 147-149), the error exponent EMSBs,SC (R1 , α) in (54) can be
approximated as
(
C−C2 (α)
− R1 ,
0 ≤ R1 < C−C42 (α) ,
√
(151)
EMSBs,SC (R1 , α) ≈ p 2
( C − C2 (α) − R1 )2 , C−C42 (α) ≤ R1 ≤ C − C2 (α).

32

E⇤q,rc (R) = Er (R)
EMSBs,SC (R1 , ↵) at R2 = C2 (↵)

2R1

Eq,spc (C/2)
gain in the quantized
MSE exponent at R=C/2

C2 (↵) C/2

∗ (R + R ) = E (R + R ) (the best achievable quantized MSE with random block coding), E
Fig. 13. A plot of Eq,rc
r
1
2
1
2
MSBs,SC (R1 , α) (the achievable
decoding-error exponent of MSBs with superposition coding), and the line 2R1 at a fixed R2 = C2 (α) where  = 0.45 and α = 0.11. When we choose α
that satisfies the condition in (150), i.e., EMSBs,SC (R − C2 (α), α) = 2(R − C2 (α)) at R = C/2, the achievable quantized-MSE exponent Eq,spc (C/2)
with the superposition coding equals the value of EMSBs,SC (R1 , α) at R1 where EMSBs,SC (R1 , α) and 2R1 cross each other. The achievable quantized-MSE
∗ (C/2) = E (C/2) with random block coding
exponent Eq,spc (C/2) at R = C/2 is strictly larger than the best achievable quantized-MSE exponent Eq,rc
r
as shown in this figure.

By using this approximation, we can see that when  ≈ 1/2, R1 = R − C2 (α) satisfying (150) is in the interval 0 ≤
R1 ≤ Rcrit (α ∗ ) ≈ C−C42 (α) , since at R1 = R − C2 (α) = E0 (1/2, α ∗ )/3 ≈ C−C62 (α) , which is strictly smaller than
Rcrit (α ∗ ) ≈ C−C42 (α) , the condition (150) is satisfied. So, at α ∈ (0, 1/2) satisfying
R = C2 (α) +

E0 (1/2, α ∗ )
,
3

(152)

the condition (150) is met. Moreover, when  ≈ 1/2, the derivative of C2 (α) + E0 (1/2,α∗)
with respect to α is positive in
3
E0 (1/2,α∗)
α ∈ (0, 1/2). Therefore, C2 (α) +
increases from E0 (1/2, )/3 to C = HB (1/2) − HB () as α increases from 0 to
3
1/2. It means that for all R ∈ (E0 (1/2, )/3, C), there always exists a unique α∗ ∈ (0, 1/2) satisfying (152).
∗
(R) = Er (R1 + R2 ) for every R1 ∈ [0, C − C2 (α)) when
Lastly, as shown in Lemma 6, since EMSBs,SC (R1 , α) > Eq,rc
∗
∗
∗
R2 = C2 (α), for our choice of R1 (α ) = R − C2 (α ) ∈ [0, C − C2 (α)) and R2 = C2 (α∗ ) it can be shown that
EMSBs,SC (R − C2 (α∗ ), α∗ ) > Er (R).

(153)

This completes the proof of the theorem.
In Fig 13, we illustrate the gain in the quantized-MSE exponent from superposition coding at R = C/2. When we choose α
that satisfies the condition in (150), i.e., EMSBs,SC (R − C2 (α), α) = 2(R − C2 (α)) at R = C/2, the achievable quantized-MSE
exponent with the superposition coding, which is denoted Eq,spc (C/2), is equal to the value of EMSBs,SC (R1 , α) at R1 where
EMSBs,SC (R1 , α) and 2R1 cross each other. In this plot, we can check that the achievable quantized-MSE exponent Eq,spc (C/2)
∗
with superposition coding is strictly larger than the best achievable quantized-MSE exponent Eq,rc
(C/2) = Er (C/2) with
random block coding.
R EFERENCES
[1] H. W. Chung, L. Zheng, B. M. Sadler, and A. O. Hero, “Unequal error protection coding approaches to the noisy 20 questions problem,” in Proc. IEEE
International Symposium on Information Theory (ISIT). IEEE, 2016, pp. 1700–1704.
[2] E. Variani, K. Lahouez, A. Bar-Hen, and B. Jedynak, “Non-adaptive policies for 20 questions target localization,” in Proc. IEEE International Symposium
on Information Theory Proceedings (ISIT). IEEE, 2015, pp. 775 – 778.
[3] D. J. MacKay, “Information-based objective functions for active data selection,” Neural computation, vol. 4, no. 4, pp. 590–604, 1992.
[4] B. Settles, “Active learning literature survey,” Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009.
[5] R. Castro and R. Nowak, “Active learning and sampling,” in Foundations and Applications of Sensor Management. Springer, 2008, pp. 177–200.
[6] D. V. Lindley, “On a measure of the information provided by an experiment,” The Annals of Mathematical Statistics, pp. 986–1005, 1956.
[7] V. V. Fedorov, Theory of optimal experiments. Elsevier, 1972.
[8] T. Tsiligkaridis, B. M. Sadler, and A. O. Hero, “Collaborative 20 questions for target localization,” IEEE Transactions on Information Theory, vol. 60,
no. 4, pp. 2233–2252, 2014.
[9] S. Luttrell, “The use of transinformation in the design of data sampling schemes for inverse problems,” Inverse Problems, vol. 1, no. 3, p. 199, 1985.
[10] B. Jedynak, P. I. Frazier, R. Sznitman et al., “Twenty questions with noise: Bayes optimal policies for entropy loss,” Journal of Applied Probability,
vol. 49, no. 1, pp. 114–136, 2012.
[11] Y. Chen, S. H. Hassani, A. Karbasi, and A. Krause, “Sequential information maximization: When is greedy near-optimal?” in Proc. of The 28th Conference
on Learning Theory, 2015, pp. 338–363.

33

[12] M. V. Burnashev and K. Zigangirov, “An interval estimation problem for controlled observations,” Problemy Peredachi Informatsii, vol. 10, no. 3, pp.
51–61, 1974.
[13] M. Horstein, “Sequential transmission using noiseless feedback,” IEEE Transactions on Information Theory, vol. 9, no. 3, pp. 136–143, 1963.
[14] T. M. Cover, “Broadcast channels,” IEEE Transactions on Information Theory, vol. 18, no. 1, pp. 2–14, 1972.
[15] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
[16] G. D. Forney Jr, “On exponential error bounds for random codes on the BSC,” unpublished manuscript, 2001.
[17] R. G. Gallager, Information theory and reliable communication. Willey, 1968, vol. 2.
[18] Y. Kaspi and N. Merhav, “Error exponents for broadcast channels with degraded message sets,” IEEE Transactions on Information Theory, vol. 57,
no. 1, pp. 101–123, 2011.
[19] J. Korner and A. Sgarro, “Universally attainable error exponents for broadcast channels with degraded message sets,” IEEE Transactions on Information
Theory, vol. 26, no. 6, pp. 670–679, 1980.
[20] R. G. Gallager, “Capacity and coding for degraded broadcast channels,” Problemy Peredachi Informatsii, vol. 10, no. 3, pp. 3–14, 1974.

