1

Fundamental Limits on Data Acquisition: Trade-offs
between Sample Complexity and Query Difficulty
Hye Won Chung∗ , Ji Oon Lee, and Alfred O. Hero

arXiv:1712.00157v2 [] 2 Jan 2018

Abstract
We consider query-based data acquisition and the corresponding information recovery problem, where the goal
is to recover k binary variables (information bits) from parity measurements of those variables. The queries and the
corresponding parity measurements are designed using the encoding rule of Fountain codes. By using Fountain codes,
we can design potentially limitless number of queries, and corresponding parity measurements, and guarantee that
the original k information bits can be recovered with high probability from any sufficiently large set of measurements
of size n. In the query design, the average number of information bits that is associated with one parity measurement
¯ and the minimum number of measurements required to recover the k information bits
is called query difficulty (d)
for a fixed d¯ is called sample complexity (n). We analyze the fundamental trade-offs between the query difficulty
¯ for some constant
and the sample complexity, and show that the sample complexity of n = c max{k, (k log k)/d}
c > 0 is necessary and sufficient to recover k information bits with high probability as k → ∞.
Index Terms
Sample complexity, query difficulty, Fountain codes, Soliton distribution, crowdsourcing.

I. I NTRODUCTION
Query-based data acquisition arises in diverse applications including: crowdsourcing [1], [2]; active learning [3],
[4]; experimental design [5], [6]; and community recovery or clustering in graphs [7], [8]. In these applications,
query-based data acquisition can be modeled as a 20 questions problem [9] between an oracle (or oracles) and
a player where the oracle knows the values of information bits that the player aims to recover, while the player
designs queries to the oracle and receives answers from the oracle. In this paper, we consider query-based data
acquisition with the goal of recovering the values of k variables (x1 , . . . , xk ) (information bits). When we assume
that the variables and the answers (measurements) are binary, we can consider a parity check sum as a type of
measurement, which corresponds to exclusive or (XOR or modulo 2 sum) of some subset of the information bits.
Querying parity symbols of the information bits generalizes the 20 questions model of [9], [10]. This generalization
is the focus of this paper and has a wide range of applications, in particular to crowdsourcing systems [1].
Consider a crowdsourcing system consisting of a number of workers and a particular task that they are expected
to work on. Assume that the task is to classify a collection of k images into two exclusive groups, e.g., whether
or not an image is suitable for children. A worker (oracle) in the system is given a query about some subset of the
images and asked to provide a binary answer regarding those images. Assume that the worker can skip the query
if the worker is unsure of the answer. The probability that one worker skips a query is unknown at the stage of
query design and it can be different for each of the workers in the system, depending on their abilities or efforts.
Therefore, from the query designer’s point of view, it is natural to assume that only a random subset of the designed
queries will be answered by the workers in the crowdsourcing system. The query designer’s objective is to design
queries such that when the received number of answers exceeds some threshold, regardless of which subset of the
answers was collected, the original k binary bits can be recovered with high probability.
In this paper we show that Fountain codes [11] are naturally suited to this crowdsourcing query design problem.
Fountain codes are a type of forward error correcting codes suitable for binary erasure channels (BEC) with
unknown erasure probabilities. This type of codes has been the subject of much research for reliable internet packet
transmissions when the packets transmitted from the source are randomly lost before they arrive at the destination.
Hye Won Chung∗ (hwchung@kaist.ac.kr) is with the School of Electrical Engineering at KAIST in South Korea. Ji Oon Lee
(jioon.lee@kaist.edu) is with the Department of Mathematical Sciences at KAIST in South Korea. Alfred O. Hero (hero@eecs.umich.edu) is
with the Department of EECS at the University of Michigan. This work was partially supported by National Research Foundation of Korea
under grant number 2017R1E1A1A01076340, and by United States Army Research Office under grant W911NF-15-1-0479.

2

For k input symbols (x1 , x2 , . . . , xk ), Fountain codes produce a potentially limitless number of parity measurements,
which are also called output symbols. By using well-designed Fountain codes, one can guarantee that, given any
set of output symbols of size k(1 + δ) with small overhead δ > 0, the input symbols can be recovered with high
probability. Examples of Fountain codes are LT-codes [12] and Raptor codes [13]. By using these Fountain codes,
we can design potentially limitless number of queries (and corresponding parity measurements) with the desired
properties suitable for the crowdsourcing example.
However, the Fountain code framework must be extended in order to account for the worker’s limited capacity to
answer difficult queries. The query difficulty is defined as the average number of input symbols required to compute
a single parity measurement. The query difficulty is related to the encoding complexity for one-stage encoding, but
it is different from the encoding complexity when the encoding is done in multiple stages. The query difficulty
represents the number of input symbols on average the worker must know to calculate one parity measurement.
Depending on the query difficulty, the number of answers (parity measurements) required to recover k input symbols
may vary greatly. We call the minimum number of measurements required to recover k input symbols the sample
complexity. The sample complexity is a function of the query difficulty as well as the number k of input symbols
to be recovered.
Let us consider two extreme cases. First, consider the case when the query difficulty is equal to 1. More
specifically, we assume that each query asks the value of only one variable in (x1 , x2 , . . . , xk ) at a time. Since it is
not known which of the queries would be answered by the workers at the stage of query design, a set of queries is
designed by uniformly and randomly picking one variable in (x1 , x2 , . . . , xk ) at a time. For such querying scenarios,
with randomly selected n measurements, in order to recover the k information bits with error probability less than
1/k u for some constant u > 0, the required number n of queries scales as k log k . On the other hand, when each
query is designed to generate a parity measurement of randomly selected k/2 bits at a time, the required number
n of measurements is only k + c log k for some constant c > 0 [13]. Therefore, in these two extreme cases, we can
observe that when the query difficulty is equal to 1, the sample complexity scales as k log k , whereas for the query
difficulty of order k the sample complexity scales as k . Then the question is how the sample complexity scales as
the query difficulty increases from 1 to Θ(k).
In this paper, we aim to analyze the fundamental trade-offs between the sample complexity and the query difficulty
in recovering k information bits. There have been papers that have analyzed such trade-offs when it is assumed that
the parity measurements involve only a fixed number 1 ≤ d ≤ k of input symbols. In [14], the case of pairwise
measurements
 (d = 2) was considered and in [15], a general integer 1 ≤ d ≤ k was considered. Note that there are
k
a total of d possible parity measurements for a fixed d. In both papers, it was assumed that each measurement is
independently observed with probability pobs . It was shown that the number n of measurements to recover k input
symbols with high probability scales as n = pobs kd = c max{k, (k log k)/d} for some constant c > 0.
In this paper, we generalize the work in [15] by not fixing the number d but instead allowing that the number
d
follows
a distribution (Ω0 , Ω1 , . . . , Ωk ) where Ωd denotes
probability that the value d is chosen, where
Pk
Pthe
k
¯
Ω
=
1
.
We
consider
the
average
query
difficulty
d
=
d
d=0 d
d=0 Ωd and analyze the sample complexity n as a
¯
function of the query difficulty d and the number k of input symbols. By assuming that d follows the prescribed
distribution, we can generate potentially limitless parity measurements by using the encoding rule employed by
Fountain codes; guaranteeing that for any set of fixed number of measurements it is possible to recover the k input
symbols with high probability. This framework is thus more suitable for the situations where the parity measurements
are erased with arbitrary (unknown) probabilities and thus it is required to have the ability to generate potentially
limitless number of queries and corresponding parity measurements.
For the previous frameworks in [14], [15], the

k
maximum number of parity measurements is restricted to d for a fixed d.
Our main contribution in this paper is to specify the fundamental trade-offs between the sample complexity
(n) and the query difficulty (d¯) in this generalized measurement model. We show that the sample complexity n
necessary and sufficient to recover k input symbols with high probability scales as

n = c · max k, (k log k)/d¯
(1)
for some constant c > 0. Note that for d¯ = O(log k), the sample complexity n is inversely proportional to the
query difficulty d¯. In particular, when query difficulty d¯ = Θ(1), the sample complexity scales as k log k , whereas
when d¯ = Θ(log k), the sample complexity scales as k .

3

The rest of this paper is organized as follows. In Section II, we explain the encoding rule of Fountain codes
(how to generate potentially limitless number of parity measurements) and state the main problem of this paper. In
Section III, we provide the main results, showing the fundamental trade-offs between the sample complexity and
the query difficulty. In Section IV, we prove the main theorem. More technical details for the proof are presented
in Appendices. In Section V, some simulation results are provided, which further support our theoretical results.
In Section VI, we provide conclusions and discuss possible future research directions.
A. Notations
We use the notation ⊕ for XOR of binary variables, i.e., for a, b ∈ {0, 1}, a ⊕ b = 0 iff a = b and a ⊕ b = 1 iff
a 6= b. We denote by ej the k -dimensional unit vector with its j -th element equal to 1. For a vector x, kxk1 denotes
the number of 1’s in the vector x. For vectors x and y, the inner product between x and y is denoted by x · y.
For two integers α and β , we use the notation α ≡ β to indicate that mod(α, 2) = mod(β, 2). For two vectors
x = (x1 , x2 , . . . , xk ) and y = (y1 , y2 , . . . , yk ), when we write x ≡ y, it means that mod(xi , 2) = mod(yi , 2) for
all i ∈ {1, 2, . . . , k}. We use the O(·) and Θ(·) notations to describe the asymptotics of real sequences {ak } and
{bk }: ak = O(bk ) implies that ak ≤ M bk for some positive real number M for all k ≥ k0 ; ak = Θ(bk ) implies
that ak ≤ M bk and ak ≥ M 0 bk for some positive real numbers M and M 0 for all k ≥ k00 . The logarithmic function
log is with base e.
II. M ODEL AND P ROBLEM S TATEMENT
Consider a k -dimensional binary random vector x = (X1 , X2 , . . . , Xk )T , which is uniformly and randomly
distributed over {0, 1}k . We call X1 , X2 , . . . , Xk the input symbols. We aim to learn the values of (X1 , X2 , . . . , Xk )
by observing a total of n parity measurements of different subsets of those k bits. Consider k -dimensional binary
vectors vi = (vi1 , vi2 , . . . , vik ), i = 1, . . . , n. The parity measurement associated with the vector vi is defined by


k
X
Yi = mod 
vij Xj , 2 = vi1 X1 ⊕ · · · ⊕ vik Xk ,
(2)
j=1

for i = 1, . . . , n. We call such parity measurements (Y1 , Y2 , . . . , Yn ) the output symbols. Each vi ∈ {0, 1}k
determines which subset of (X1 , X2 , . . . , Xk ) is to be picked in calculating the i-th parity measurement.
The process of designing {vi } is called query design or encoding. We use Fountain codes, also known as
erasure rateless codes, for the encoding. Let (Ω0 ,P
Ω1 , . . . , Ωk ) be a distribution on {0, 1, . . . , k} where Ωd denotes
k
the probability that the value d is chosen and
d=0 Ωd = 1. In the encoding of Fountain codes, each vector
vi is generated independently and randomly by first sampling a weight d ∈ {0, 1, . . . , k} from the distribution
(Ω0 , . . . , Ωk ) and then selecting a k -dimension vector of weight d uniformly at random from all the vectors of
{0, 1}k with weight d.
Consider an arbitrary set of n output symbols (Y1 , . . . , Yn ) generated by the above encoding rule. The relationship
between the k input symbols and the n output symbols can be depicted by a bipartite graph with k input nodes on
one side and n output nodes on the other side as shown in Fig 1. Denote by d¯ the average degree of the output
nodes,
k
X
¯
d=
d · Ωd .
(3)
d=1

This number d¯ indicates the average number of input symbols involved in one parity measurement (output symbol)
and is related to the difficulty in calculating one parity measurement. We call this number query difficulty.
The process of recovering the k input symbols from the n output symbols is called information recovery or
decoding. Denote by x̂(Y1k ) the estimate of x given Y1n and define the probability of error as
Pe(k) = min Pr(x̂(Y1k ) 6= x).

(4)

x̂(·)

(k)

With the proper choice of the distribution (Ω0 , . . . , Ωk ), the Fountain codes guarantee that Pe → 0 as k → ∞ with
(k)
n larger than some threshold. The minimum number of n required to guarantee Pe → 0 as k → ∞, minimized
over all (Ω0 , . . . , Ωk ) for a fixed k and d¯, is called sample complexity. We aim to find the fundamental limits on
n to guarantee reliable information recovery of k input symbols for a fixed query difficulty d¯.

4

Input nodes

Output nodes

x1
x2
x3

x4
x5
x6

..
.

xk

..
.

y1
y2
y3
y4
y5
y6
y7
yn

Fig. 1. Bipartite graph between input nodes and output nodes.

III. M AIN R ESULTS : F UNDAMENTAL T RADE - OFFS BETWEEN S AMPLE C OMPLEXITY AND Q UERY D IFFICULTY
In this section, we state our main results that the sample complexity n that is necessary and sufficient to make
¯ for some constant c > 0 independent
→ 0 as k → ∞ scales in terms of k and d¯ as n = c · max{k, (k log k)/d}
of k and d¯, when the parity measurements are generated by the encoding rule of Fountain codes as explained in
Section II.
We first state the well-known lower bound on the sample complexity n of Fountain codes presented in [13].
(k)
Proposition 1: To reliably recover k input symbols with Pe ≤ 1/k u for some constant u > 0 from parity
measurements generated by Fountain codes, it is necessary that


k log k
n ≥ cl max k,
(5)
d¯
(k)
Pe

for some constant cl > 0.
P

k
Proof: Showing the first condition n ≥ cl k is straightforward. Each output symbol Yi = mod
v
X
,
2
j=1 ij j
represents a linear equation of k unknown input symbols (X1 , X2 , . . . , Xk ). Since there are k unknowns, it is
necessary to have at least n = k linear equations to solve this linear system reliably.
The second condition n ≥ (cl k log k)/d¯ is from a property of random graphs. In the bipartite graph between
input nodes and output nodes, we say that an input node is isolated if it is not connected to any of the output
nodes. We analyze the probability that an input node is isolated when the edges are designed by the encoding rule
(k)
of Fountain codes. The error probability Pe is bounded below by the probability that an input node is isolated,
since when an input node is isolated the decoding error happens.
Consider an output node with degree d. The probability that an input node is not connected to this output node
of degree d equals 1 − d/k . Since an output node has degree d with probability Ωd , the probability that an input
node is not connected to an output node equals
k
X

¯
Ωd (1 − d/k) = 1 − d/k.

(6)

d=0

Since there are n output nodes and these output nodes are sampled independently, the probability that an input
node is isolated (not connected to any of those output nodes) equals

n
d¯
1−
.
(7)
k
¯ n ≥ e−α/(1−α/n) where α = nd/k
¯ . Since the decoding
By the mean value theorem, we can show that (1 − d/k)
(k)
(k)
error probability Pe is lower bounded by the probability that an input node is isolated, to satisfy Pe ≤ 1/k u

5

for some constant u > 0, it is necessary that e−α/(1−α/n) ≤ 1/k u , which is equivalent to
u
α ≥ log k ·
1 + (u log k)/n
u
≥ log k ·
1 + (u log k)/k
u
≥ log k ·
1 + (u log 3)/3
≥ cl log k

(8)

¯ , we get
for some constant cl > 0. By plugging in α = nd/k
nd¯ ≥ cl k log k.

(9)

The main contribution of this paper is showing that the bound in (5) is indeed achievable (up to constant scaling)
by properly designed Fountain codes for any d¯ from Θ(1) to Θ(log k). We provide a particular output degree
distribution (Ω0 , Ω1 , . . . , Ωk ) for which we can control the query difficulty d¯ from Θ(1) to Θ(log k) and show that
it is possible to reliably recover k information bits with sample complexity obeying


k log k
(10)
n = cu max k,
d¯
¯ is
for some constant cu > 0. Therefore, by combining (10) with (5), we conclude that n = c · max{k, (k log k)/d}
¯
necessary and sufficient for reliable recovery of k information bits when d is the average query difficulty.
Suppose that the law of Ωd is given by an ideal Soliton distribution
1
if d = 1

D
1
Ωd = d(d−1) if 2 ≤ d ≤ D
(11)


0
if d > D or d = 0,
for some D ∈ {2, 3, . . . , k}. Here, for simplicity, we assume that k ≥ 3. Note that the query difficulty scales as
log D since
D
D
X
X
1
1
1
log(D + 1) < d¯ =
+
=
< log D + 1.
D
d−1
d
d=2

d=1

Therefore, as D increases from 2 to k , the query difficulty d¯ scales from log 3 to log k .
Theorem 1: For the Soliton distribution (11) with D ∈ {2, 3, . . . , k}, the k input symbols can be reliably recovered,
(k)
i.e., Pe → 0 as k → ∞, with sample complexity


k log k
n = cu · max k,
(12)
d¯
for some constant cu > 0.
The proof of Theorem 1 will be presented in Section IV.
Theorem 1 states that for query difficulty d¯ = O(log k), the sample complexity n to reliably recover k input
symbols is inversely proportional to the query difficulty d¯. When the query difficulty does not increase in k , i.e.,
d¯ = Θ(1), it is necessary and sufficient to have n = Θ(k log k) to reliably recover the k information bits. In this
regime, the ratio between k and n converges to 0 as k → ∞. On the other hand, when we increase the query
difficulty to d¯ = Θ(log k), it is enough to have n = Θ(k) samples, which results in a positive limit of k/n as
k → ∞. When d¯  log k , increasing the query difficulty no longer helps in reducing the sample complexity.
By using the Soliton distribution (11) and the encoding rule of Fountain codes, we can design potentially limitless
number of queries about (x1 , x2 , . . . , xk ) and the corresponding parity measurements. Theorem 1 shows that with
any set of measurements of size n no larger than (12), we can reliably recover the k information bits as k → ∞.
Moreover, this sample size is optimal up to constants as shown by Proposition 1. Thus, our results provide the
optimal query design strategy for reliable information recovery from an arbitrary set of parity measurements, optimal
in terms of the sample complexity (up to constants) for a fixed query difficulty.

6

IV. P ROOF OF T HEOREM 1
(k)

In this section, we prove Theorem 1 by providing an upper bound on Pe and showing that the sample complexity
¯ for some constant
n sufficient to make this upper bound converge to 0 as k → ∞ is equal to cu ·max{k, (k log k)/d}
cu > 0.
(k)
Consider Pe defined in (4). The optimal decoding rule x̂(·) that minimizes the probability of error is the
maximum likelihood (ML) decoding for the uniformly distributed
Assume that we collect n parity
P input symbols.

n
measurements (Y1 , . . . , Yn ) each of which equals Yi = mod
j=1 vij Xj , 2 . Consider a matrix A whose i-th row
is vi = (vi1 , vi2 , . . . , vik ), i.e.,
A := [v1 ; v2 ; . . . ; vn ].
(13)
We call A a sampling matrix. Given (Y1 , . . . , Yn ) and the sampling matrix A, the ML decoding rule finds x =
(X1 , X2 , . . . , Xk )T ∈ {0, 1}k such that
Ax ≡ (Y1 , Y2 , . . . , Yn )T .
(14)
If there is a unique solution x ∈ {0, 1}k for this linear system, then it is claimed that x̂(Y1k ) = x. If there is more
than one x satisfying this linear system, then an error is declared. The probability of error is thus equal to
X 1
Pr(∃x0 6= x such that Ax0 ≡ Ax).
(15)
Pe(k) =
k
2
k
x∈{0,1}

Due to symmetry, the probabilities Pr(∃x0 6= x such that Ax0 ≡ Ax) are equal for every x ∈ {0, 1}k . Thus, we
focus on the case where x is the vector of all zeros and consider
Pe(k) = Pr(∃x0 6= 0 such that Ax0 ≡ 0).

(16)

By using the union bound, it can be shown that
Pe(k) ≤

X

Pr(Ax0 ≡ 0) =

x0 6=0

=

Pr(Ax0 ≡ 0)

s=1 kx0 k1 =s

k  
X
k
s=1

k
X
X

s

s
X

Pr A

!
ei

(17)

!
≡0

i=1

where ei is the i-th standard unit vector. The last equality follows from the symmetry of the sampling matrix A.
Since all the output samples are generated independently by the identically distributed vi ’s, each of which has
weight d with probability Ωd ,
!
!!n
s
k  
X
X
k
ei ≡ 0
Pe(k) ≤
Pr v1 ·
s
s=1
i=1
k  
X
k
(18)
=
×
s
s=1
!!n !
!
k
s
X
X
Ωd Pr v1 ·
ei ≡ 0 kv1 k1 = d
.
i=1

d=1

We next analyze
Pr v1 ·

s
X

!
ei

!
≡ 0 kv1 k1 = d .

(19)

i=1

P
Note that v1 · ( si=1 ei ) ≡ 0 if and only if there are even number of 1’s in the first s entries of v1 . This probability
equals


!
! P
s k−s
s
i≤d
X
i d−i
(20)
Pr v1 ·
ei ≡ 0 kv1T k = d = i is evenk
.
i=1

d

7

We next provide an upper bound on (20). Define
X sk − s
Id =
.
i
d−i

(21)

i≤d
i is even


In the following lemma, we provide an upper bound on Id as a multiple of kd . The proof of this lemma is based
on that of the similar lemma provided in [15], where the upper bound on Id is stated depending on the regimes of
s for a fixed d. We provide an alternative version where the upper bound on Id depends on the regimes of d for a
fixed s.
Lemma 1: Consider the case that s ≤ k2 (i.e., s ≤ k − s). Define
κ(s) =

1) For d ≤

2) For d >

k
2

k
2

k−s+1
.
2s + 1

(22)

(or, k − d ≥ d), when we define α = k−d+1
,
d
(
 k
2s
1 − 5α
d , when d < κ(s),
Id ≤ 4 k 
when d ≥ κ(s).
5 d ,

(23)

d+1
(or, k − d < d), when we define α0 = k−d
,
(


k
2s
1 − 5α
0
d , when d > k − κ(s),

Id ≤ 4 k
when d ≤ k − κ(s).
5 d ,

(24)

In the case s > k2 , we can obtain the bounds for Id simply by changing s to k − s.
Proof: Appendix A.
(k)
By using Lemma 1 and (20), the upper bound on Pe in (18) can be further bounded by


k−dκ(s)e
X k  dκ(s)e−1
X 4
X 
2s
(k)

Pe ≤ 2
Ωd +
Ωd
1−
5α
5
s
k
d=1
d=dκ(s)e
s≤ 2
n


k
X
2s
+
1 − 0 Ωd 
5α
d=k−dκ(s)e+1
X k 
X k 
(1 − Σs )n ≤ 2
e−nΣs ,
=2
s
s
k
k
s≤ 2

(25)

s≤ 2

where we let
k−dκ(s)e
1 X
Ωd +
5
d=dκ(s)e

dκ(s)e−1
2s  X
d Ωd
+
5
k−d+1

Σs =

d=1

k
X
d=k−dκ(s)e+1



(26)

(k − d)Ωd 
.
d+1

Suppose that the law of Ωd is given by a Soliton distribution provided in (11). Here, for simplicity,
 we assume
that D ∈ {2, 3, . . . , k} and k ≥ 3. For this Soliton distribution, we provide an upper bound on ks e−nΣs in (25)
for s ≤ k2 depending on the regime of dκ(s)e with conditions on the sample complexity n.
Lemma 2: With the sample complexity


k log k
n ≥ cu max k,
(27)
d¯

for some constant cu > 0, the term ks e−nΣs is bounded above as follows.

8

(k)
¯ (the query difficulties). The
Fig. 2. Monte Carlo simulation (5000 runs) of the probability of error Pe with k = 300 for three different d’s
(k)
¯
sample complexity is normalized by (k log k)/d. We can observe the phase transition for Pe around the normalized sample complexity
equal to 1 for all the three query difficulties considered.

1) If dκ(s)e > D,

2) If 4 ≤ dκ(s)e ≤ D

 
k −nΣs
< k −s .
e
s
(
 
k −s
k −nΣs
√
e
≤
s
2−2 k

(28)

√
if s ≤ k ,
√
if k < s ≤ k/2 .

(29)

3) If dκ(s)e ≤ 3,
 
k −nΣs
≤ 2k e−k .
e
s

(30)

Proof: Appendix B.
We remark that the case 2) does not happen when D ∈ {2, 3}.
(k)
From Lemma 2, when the sample complexity n satisfies (27) we can further bound Pe in (25) by

√
X
k −s + 2−2 k + 2k e−k
Pe(k) ≤ 2
s≤ k2

≤ c0



√
1
+ k2−2 k + k2k e−k
k



(31)

for some constant c0 > 0. Note that this upper bound converges to 0 as k → ∞.
V. S IMULATIONS
In this section, we provide empirical performance analysis for the probability of error in the recovery of k
information bits, as a function of the sample complexity and query difficulty. In Fig. 2, we provide Monte Carlo
(k)
simulation results for the probability of error Pe , defined in (4), where the number k of information bits to
(k)
recover is fixed as k = 300. We plot Pe in terms of the normalized sample complexity, normalized by (k log k)/d¯
where d¯ is the query difficulty. We run the simulations for three different query difficulties, d¯ =4, 4.7, 5.6. The
parity measurements (output symbols) are designed by first sampling d (the number of input symbols required to
compute a single parity measurement) from the Soliton distribution (11) and then generating the measurements by
the encoding rule of Fountain codes.

9

Fig. 3. Same simulation conditions as in Fig 2 except that the horizontal axis is the un-normalized sample complexity. As the query difficulty
(k)
increases, the sample complexity to make Pe close to 0 decreases. This illustrates the trade-offs between the query difficulty and the sample
complexity.
(k)

Observe the phase transition of Pe around the normalized sample complexity equal to 1. In Theorem 1, we stated
¯ for some constant cu > 0, we can guarantee Pe(k) → 0 as
that with sample complexity of cu · max{k, (k log k)/d}
(k)
k → ∞. The simulation results show that cu ≈ 1 is sufficient to produce a dramatic decrease of Pe . Since the phase
transition occurs in the vicinity of normalized sample complexity equal to 1, the figure demonstrates the trade-offs
between the query difficulty and the sample complexity. Specifically, the required number of parity measurements
to reliably recover k information bits is inversely proportional to the query difficulty when d¯ = O(log k). Note that
¯ = Θ((k log k)/d)
¯.
for the Soliton distribution (11), the query difficulty is O(log k), and thus max{k, (k log k)/d}
In Fig 3, we show the same simulation with un-normalized sample complexity indexing the horizontal axis. From
(k)
this plot, we can observe that as the query difficulty increases, the required number of samples to make Pe close
to 0 decreases.
VI. C ONCLUSIONS
In this paper, we analyzed the fundamental trade-offs between query difficulty d¯ and sample complexity n in a
query-based data acquisition system associated with a crowdsourcing task with workers who may be non-responsive
to certain queries (channel erasures). We considered the information recovery of k binary variables (x1 , x2 , . . . , xk )
from parity measurements of subsets of these variables. We used a query design based on the encoding rules of
Fountain codes, with which we can design potentially limitless numbers of queries. We showed that the proposed
query design policy guarantees that the original k information bits can be recovered with high probability from
any set of measurements of size n larger than some threshold. We obtained necessary and sufficient conditions on
¯.
sample complexity n ≥ c · max{k, (k log k)/d}
There are several interesting future research directions related to this work. One of such directions includes
analyzing trade-offs between query difficulty and sample complexity for partial information recovery problems.
In this paper, we considered exact information recovery, meaning we aimed to recover all the k information bits
with high probability. But depending on scenarios, it could be enough to recover only αk of information bits for
α ∈ (0, 1). Then, the question is how much this relaxed recovery condition would help in reducing the sample
complexity for a given query difficulty d¯. Especially, one interesting question might be whether it is possible to
recover αk information bits with only n = Θ(k) measurements even with the very low query difficulty d¯ = Θ(1),
which does not increase in k . In the exact recovery problem, it was impossible to reliably recover k input symbols
with the sample complexity n = Θ(k) when the query difficulty is d¯ = Θ(1). With d¯ = Θ(1), it was necessary to
have at least n = Θ(k log k) sample complexity for the exact recovery, which makes the ratio k/n goes to 0 as
k → ∞. Therefore, it would be interesting to see whether the sample complexity of n = Θ(k) is sufficient for the
partial recovery problem even with the query difficulty of d¯ = Θ(1).

10

Another interesting direction is to apply the proposed query design to real crowdsourcing systems and to analyze
the experimental trade-offs between the query difficulty and the sample complexity. Especially, when the collected
measurements contain inaccurate answers and the probability that the measurements include inaccurate answers
changes depending on the query difficulty, the corresponding sample complexity might be a different function of
k and d¯. Therefore, it would be interesting to find the query difficulty that minimizes the sample complexity in
crowdsourcing systems with random erasures and inaccurate answers, and this direction of research would help
guiding the design of sample-efficient crowdsourcing systems.
A PPENDIX A
P ROOF OF L EMMA 1
To prove this lemma,
refer to the similarombound provided n
in [15].
l we n
o
k−d+1
d+1
d+1
Lemma 3: Let β = max 2d+1 , 2(k−d)+1
,
and α = max k−d+1
d
k−d . Then we have


2s k

,
when s < β,




5α
d
X s k−s

≥ 15 kd ,
when β ≤ s ≤ k − β,

i
d−i
 2(k−s) k
i≤d
5α
d , when k − β < s.
i is odd
Note that

(32)

 
X sk − s
X sk − s
k
=
+
.
d
i
d−i
i
d−i
i≤d
i is odd

(33)

i≤d
i is even

Therefore, by using Lemma 3, we can find an upper bound on

s
i≤d
i
i is even

P



k−s
d−i



as a scaling of

k
d



such that

X sk − s
Id =
i
d−i
i≤d

i is even  
k
2s


 1 − 5α d ,
4 k
≤ 5 d ,



 1 − 2(k−s)
5α

k
d

We define
κ(s) =

We first consider the case s ≤
find that

k
2

(34)

when s < β,
when β ≤ s ≤ k − β,


,

when k − β < s.

k−s+1
.
2s + 1

(35)

(i.e., s ≤ k − s). Since β attains its maximum

k
3

at d = 1 or d = k − 1, we

k
≤ k − s.
2
Hence, k − β > s and the last case in (34) cannot happen.
1) For d ≤ k2 (or, k − d ≥ d),


k−d+1
k−d+1
β=
,
α=
.
2d + 1
d
β<

Note that

2) For d >

k
2

k−κ(s)+1
2κ(s)+1

= s. Since

k−d+1
2d+1

is an increasing function of d, if d < κ(s) then β > s. Thus,
(
 k
2s
1 − 5α
d , when d < κ(s),
Id ≤ 4 k
when d ≥ κ(s).
5 d ,

(or, k − d < d),



d+1
β=
,
2(k − d) + 1

α=

d+1
.
k−d

(36)

11

Proceeding as above, we get
(
Id ≤

2s
1 − 5α

4 k
5 d ,

k
d





,

when d > k − κ(s),
when d ≤ k − κ(s).

(37)

In the case s > k2 , we can obtain the bounds for Id simply by changing s to k − s.
A PPENDIX B
P ROOF OF L EMMA 2

In this lemma, we prove an upper bound on ks e−nΣs where
k−dκ(s)e
1 X
Σs =
Ωd +
5
d=dκ(s)e

dκ(s)e−1
2s  X
d Ωd
+
5
k−d+1
d=1

For the Soliton distribution
Ωd =



k
X
d=k−dκ(s)e+1

(k − d)Ωd 
.
d+1

1

D

if d = 1
if 2 ≤ d ≤ D


0

if d > D or d = 0,

1
 d(d−1)

(38)

we have the query difficulty
D

D

d=2

d=1

X 1
X1
1
log(D + 1) < d¯ =
+
=
< log D + 1.
D
d−1
d
For simplicity, here we assume that D ≥ 2. Recall that
κ(s) =

k−s+1
,
2s + 1

(39)

which is a decreasing function of s, and κ(s) > 0 for s ≤ k2 .
1) If dκ(s)e > D,
dκ(s)e−1
D
2s X
d Ωd
2s X
2sd¯
Σs ≥
>
d Ωd =
.
5
k−d+1
5k
5k
d=1

Thus, if nd¯ ≥ 5k log k ,

d=1

 


2nsd¯
k −nΣs
s
e
< k exp −
≤ k s k −2s = k −s .
5k
s

2) If 4 ≤ dκ(s)e ≤ D, we first notice that
k−2
⇔ κ(s) > 3 ⇔ dκ(s)e ≥ 4.
7
4k
4k
≥ 7(2s+1)
≥ 21s
. In this case,

s<

Thus s ≤

k−2
7

and κ(s) − 1 =

k−3s
2s+1

Σs ≥

>

2s
5
2s
5k

dκ(s)e−1

X
d=1
dκ(s)e−1

X
d=2

d Ωd
k−d+1
1
d−1

2s
>
log(dκ(s)e − 1)
5k


4k
2s
≥
log
.
5k
21s

(40)

12

Moreover, since

k
s

≥ 7, if n ≥ Ck for some sufficiently large C , (C ≥ 68 suffices)

nΣs


2Cs
4k
≥
log
5
21s
  

 
k
2C
4
2Cs
≥ 4s log
+
− 4 s log 7 +
log
s
5
5
21
 
k
≥ 4s log
.
s
From Stirling’s formula, we also have that
√
1
1
2πnn+ 2 e−n ≤ n! ≤ enn+ 2 e−n ,

hence
 
1
k
ek k+ 2 e−k
≤
1
1
s
2π(k − s)k−s+ 2 e−(k−s) ss+ 2 e−s
√
k
kk
≤ p
·
2 (k − s)s (k − s)k−s ss
 s 
k
s s−k
≤
1−
s
k

 s

 
2
s2
k
k
s− sk
e
+s−
≤
= exp s log
s
s
k

 
k
≤ exp 2s log
.
s
Thus, if n ≥ 68k ,

Note that


   −2s
 
k
k −nΣs
k
≤ exp −2s log
e
=
.
s
s
s
√
 −2s ( −s
k
if s ≤ k ,
k
√
√
≤
s
2−2 k if k < s ≤ k/2 .

3) If dκ(s)e = 3, we find from (40) that s ≥

k−2
7 .

Σs ≥

for k ≥ 3. Thus, if n ≥ 35k ,

Then, by considering the case d = 2,
2s
5

dκ(s)e−1

X
d=1

d Ωd
k−d+1

2s
≥
5(k − 1)
2(k − 2)
≥
35(k − 1)
1
≥
35
 
k −nΣs
e
≤ 2k e−k .
s

4) If dκ(s)e = 1, 2,
1
Σs ≥
5

Thus, if n ≥ 10k ,

k−dκ(s)e

X
d=dκ(s)e

Ωd ≥

Ω2
1
= .
5
10

 
k −nΣs
e
≤ 2k e−k .
s

13

R EFERENCES
[1] D. R. Karger, S. Oh, and D. Shah, “Budget-optimal task allocation for reliable crowdsourcing systems,” Operations Research, vol. 62,
no. 1, pp. 1–24, 2014.
[2] M. S. Bernstein, J. Brandt, R. C. Miller, and D. R. Karger, “Crowds in two seconds: Enabling realtime crowd-powered interfaces,” in
Proceedings of the 24th annual ACM symposium on User interface software and technology. ACM, 2011, pp. 33–42.
[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,” University of Wisconsin, Madison, vol. 52, no. 55-66, p. 11, 2010.
[5] D. V. Lindley, “On a measure of the information provided by an experiment,” The Annals of Mathematical Statistics, pp. 986–1005,
1956.
[6] V. V. Fedorov, Theory of optimal experiments. Elsevier, 1972.
[7] E. Abbe and C. Sandon, “Community detection in general stochastic block models: Fundamental limits and efficient algorithms for
recovery,” in Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, 2015, pp. 670–688.
[8] B. Hajek, Y. Wu, and J. Xu, “Information limits for recovering a hidden community,” IEEE Transactions on Information Theory, 2017.
[9] H. W. Chung, B. M. Sadler, L. Zheng, and A. O. Hero, “Unequal error protection querying policies for the noisy 20 questions problem,”
IEEE Transactions on Information Theory, DOI: 10.1109/TIT.2017.2760634, 2017.
[10] 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.
[11] D. J. MacKay, “Fountain codes,” IEE Proceedings-Communications, vol. 152, no. 6, pp. 1062–1068, 2005.
[12] M. Luby, “LT codes,” in Proceedings. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. IEEE, 2002,
pp. 271–280.
[13] A. Shokrollahi, “Raptor codes,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2551–2567, 2006.
[14] Y. Chen, C. Suh, and A. J. Goldsmith, “Information recovery from pairwise measurements,” IEEE Transactions on Information Theory,
vol. 62, no. 10, pp. 5881–5905, 2016.
[15] K. Ahn, K. Lee, and C. Suh, “Community recovery in hypergraphs,” in 2016 54th Annual Allerton Conference on Communication,
Control, and Computing (Allerton). IEEE, 2016, pp. 657–663.

