{'fraction_non_alphanumeric': 0.051109200343938094, 'fraction_numerical': 0.013207222699914015, 'mean_word_length': 4.291355777979982, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Asynchronous Decentralized 20 Questions for Adaptive Search

This paper considers the problem of adaptively searching for an unknown target using multiple agents connected through a time-varying network topology. Agents are equipped with sensors capable of fast information processing, and we propose a decentralized collaborative algorithm for controlling their search given noisy observations. Specifically, we propose decentralized extensions of the adaptive query-based search strategy that combines elements from the 20 questions approach and social learning. Under standard assumptions on the time-varying network dynamics, we prove convergence to correct consensus on the value of the parameter as the number of iterations go to infinity. The convergence analysis takes a novel approach using martingale-based techniques combined with spectral graph theory. Our results establish that stability and consistency can be maintained even with one-way updating and randomized pairwise averaging, thus providing a scalable low complexity method with performance guarantees. We illustrate the effectiveness of our algorithm for random network topologies.


I. INTRODUCTION
Consider a set of agents that try to estimate a parameter, e.g., estimate a target state or location, collectively. The agents are connected by a time-varying information sharing network and can periodically query one of their local neighbors about the target location. In this paper we adopt a generic observation model based on query-response models where the queries are functions of agents' local information and successive queries are determined by a feedback control policy. Specifically, in the 20 questions-type model considered in this paper, the observation of each agent is coupled with the query region chosen by that agent, which is a function of its current local belief.
A centralized collaborative 20 questions framework was proposed and studied in [1], where a global centralized controller jointly or sequentially formulates optimal queries about target location for all agents. This work was later extended in [2] to the decentralized setting, in which each agent formulates his own query based on his local information and exchanges beliefs with its neighbors in a synchronous fashion (i.e, updating the beliefs of all agents simultaneously at each update step). The proposed decentralized algorithm therein consisted of two stages: 1) local belief update; and 2) local information sharing. In stage 1 each agent implements the bisection query policy of [1] to update their local belief function. In stage 2 the local belief functions are averaged over nearest neighborhoods in the information sharing network. This two-stage algorithm was proven to converge to a consensus estimate of the true state, assuming synchronous updating of all agents' beliefs in the network and irreducibility of the social interaction graph.
The decentralized collaborative 20 questions problem is applicable to large scale collaborative stochastic search applications where there is no centralized authority. Examples include: object tracking in camera networks [3]; road tracking from satellite remote sensing networks [4]; and wide area surveillance networks [5]. Other applications may include extending active testing approaches in the decentralized setting for classification problems, for instance in vision, recommendation systems, and epidemic networks. The 20 questions paradigm is motivated by asking the correct type of questions in the correct order and is applicable to various other domains where computational effort and time are critical resources to manage.
In this paper, we consider a variant of the two-stage decentralized collaborative algorithm of [2] by relaxing the assumption of a fixed network topology. We consider time-varying network topologies in which two randomly chosen agents interact at each update step, giving rise to asynchronous updates (i.e., beliefs of all agents are not updated at each update step). We analyze the convergence properties of the two-stage asynchronous decentralized collaborative 20 questions algorithm under appropriate conditions. This asynchronous model is applicable to practical sensor networks where agents may be located in large geometric distances, and as a result their wireless communications are unreliable or intermittent due to path occlusions or other environmental effects, and lead to time-varying network topologies. Our analysis is based on smoothing techniques and martingale convergence theory in similar spirit to [2]. However, the randomness due to the time-varying network topology and lack of strong connectivity at each time instant introduce additional complications in the analysis that were absent when analyzing the static network case of adaptive agents in [2].
In addition to theoretical analysis of the convergence of the proposed algorithm, numerical studies of performance are provided showing interesting information behavior that information sharing yields. The benefit of our asynchronous approach is that the asynchronous decentralized algorithm attains similar performance as its synchronous counterpart introduced and analyzed in [2]. The lack of synchronization our approach offers is of great practical interest because synchronization of a large number of agents can be difficult [6]. Furthermore, the popular time-division-multiple-access (TDMA) communication protocol for distributed networks is only applicable to synchronized networks. Even though the synchronous update scheme in [2] is proven to be convergent to the correct limit, it is still an open question whether the same algorithm converges with an asynchronous implementation.
Counterexamples showing that asynchronous updates do not converge although synchronous updates converge are presented in [7] for the standard consensus problem.

A. Prior Work
The noisy 20 questions problem, also known as Ulam's game, was introduced by Renyi [8] and was later rediscovered by Ulam [9]. The first work making the connection between communication with feedback and noisy search appeared in [10]. The probabilistic bisection algorithm dates back to the work of Horstein [11], where it was originally proposed and analyzed heuristically in the contest of communication with noiseless feedback over the binary symmetric channel. This algorithm was shown to achieve capacity for arbitrary memoryless channels in [12], [13]. The probabilistic bisection algorithm was generalized to multiple players in [1] in the centralized setting, and decentralized algorithms for probabilistic bisection search were proposed in [2].
Our work also differs from the works on 20 questions/active stochastic search of Jedynak, et al., [14], Castro & Nowak [5], Waeber, et al., [15], and Tsiligkaridis, et al., [1] because we consider intermediate local belief sharing between agents after each local bisection and update. In addition, in contrast to previous work, in the proposed framework each agent incorporates the beliefs of its neighbors in a way that is agnostic of its neighbors' error probabilities. The analysis of [16], [17] does not apply to our model since we consider controlled observations, although we use a form of the social learning model of [16], [17]. While a randomized distributed averaging/consensus problem was analyzed in [18], the convergence analysis is not applicable because we consider new information injected in the dynamical system at each iteration (controlled information gathering) in addition to randomized information sharing.
Although consensus to the true target location holds for the degenerate case of no agent collaboration by using results in the existing literature, collaboration improves the rate of convergence of the estimation error. As shown in the numerical results in this paper, the error decays faster as a function of iterations. This is the primary motivation for studying such collaborative signal processing algorithms. However, proving convergence to the correct consensus is the first step in analyzing such algorithms, and it is by no means a trivial one. In fact, even for the simple singleagent case, only very recently, Waeber, et al [15] were able to prove the first rigorous convergence rate result for the continuous probabilistic bisection algorithm. The focus of this paper is to establish convergence of decentralized algorithms for probabilistic bisection in time-varying networks.

II. NOTATION
We define X * the true parameter, the target state in the sequel, and its domain as the unit interval X = [0, 1]. Let B(X ) be the set of all Borel-measurable subsets B ⊆ X . Let N = {1, . . . , M } index the M agents in an interaction network, denoted by the vertex set N and the directed edges joining agents at time t ∈ N are captured by E(t). Let A t = {a i,j (t)} denote the interaction matrix at time t, which is a stochastic matrix (i.e., nonnegative entries with rows summing to unity). At each time t, the time-varying network structure is modeled by the directed graph (N , E(t)), where Let A i→j denote the interaction matrix when agent i performs a Bayesian update based on its query and averages beliefs with agent j. In our model, a random agent i is chosen with probability q i and a collaborating agent j is chosen with probability P i,j at each update step. Thus, the interaction matrix A t = A i→j is chosen with probability q i P i,j , and nodes i and j collaborate. The matrix P = {P i,j } contains the probabilistic weights for collaboration between agents and are zero when there is no edge in the information sharing network at any time; if P i,j = 0, then agent i cannot collaborate with agent j at any time. Define the probability space (Ω, F, P) consisting of the sample space Ω generating the unknown state X * and the observations {Y i,t+1 } at times t = 0, 1, . . ., an event space F and a probability measure P. The expectation operator E is defined with respect to P.
Define the belief of the i-th agent at time t on X as the posterior density p i,t (x) of target state x ∈ X based on all of the information available to this agent at this time. Define the M × 1 vector p t (x) = [p 1,t (x), . . . , p M,t (x)] T for each x ∈ X . For any B ∈ B(X ), define P t (B) as the vector of probabilities with i-th element equal to B p i,t (x)dx. We define the query point/target estimate of the i-th agent asX i,t . The query point is the right boundary of the region We assume that a randomly chosen agent i constructs a query at time t of the form "does X * lie in the region A i,t ⊂ X ?". We indicate this query with the binary variable Z i,t = I(X * ∈ A i,t ) to which agent i responds with a binary response Y i,t+1 , which is correct with probability 1 − i , and without loss of generality i ≤ 1/2. This error model is equivalent to a binary symmetric channel (BSC) with crossover probability i . The query region A i,t depends on the accumulated information up to time t at agent i. Define the nested sequence of event spaces F t , F t−1 ⊂ F t , for all t ≥ 0, generated by the sequence of queries and responses. The queries {A i,t } t≥0 are measurable with respect to this filtration. Define the canonical basis vectors e i ∈ R M as [e i ] j = I(j = i). The notation i.p. denotes convergence in probability and a.s. denotes almost-sure convergence.

III. ASYNCHRONOUS DECENTRALIZED 20 QUESTIONS
Motivated by the work of [1], [2] and [16], we proceed as follows. As in the fixed-topology decentralized algorithm in [2], starting with a collection of prior distributions {p i,0 (x)} i∈N on X * , the goal is to reach consensus across the network through repeated querying and information sharing. Our proposed asynchronous decentralized collaborative 20 questions algorithm consists of two stages. Motivated by the optimality of the bisection rule for symmetric channels proved by Jedynak, et al., [14], the first stage bisects the posterior of a randomly chosen agent i ∈ N (say with probability q i ) atX i,t and refines its own belief through Bayes' rule 1 . In the second stage, agent i collaborates with an agent j with probability P i,j by averaging their beliefs (see Algorithm 1). Some simplifications occur in Algorithm 1. The normalizing factor Z i,t (y) is given by X p i,t (x)l i (y|x,X i,t )dx and can be shown to be equal to 1/2 (see proof of Lemma 1 in Appendix A). The bisection query points are mediansX i,t = F −1 i,t (1/2) and the observation distribution is: where the distributions f (i) z (·) are defined in (6). We note that the conditioning on the query region A i,t (or query pointX i,t in one-dimension) is necessary as the binary observation y is linked to the query in the 20 questions model, in which the correct answer is obtained with probability 1 − i and the wrong answer is obtained with probability i . We remark that the density l i (y|x,X i,t ) depends on the query pointX i,t , which is time-varying and as a result, the density l i (y|x,X i,t ) is time-varying.
We remark that Algorithm 1 is fully decentralized, i.e., only local information processing and local information sharing is needed. Furthermore, it operates in an asynchronous fashion as the belief updates are not occurring simultaneously for all agents in the network. At each step, two agents collaborate with each other and update their beliefs. This belief averaging leads to a non-Bayesian social learning scheme in similar spirit to [16], [17].

8:
Choose a collaborating agent j ∈ N with probability P i,j .

9:
Belief update: where the observation p.m.f. is: Collaboration becomes essential in certain scenarios when some agents in the network are completely unreliable i = 1/2, and helps tremendously when agents are unreliable, i.e., i ≈ 1/2. When an agent is completely unreliable, its learning capacity is zero and cannot localize the target on its own. With collaboration, neighboring agents may steer the belief of unreliable agents closer to the true location (also see Section V for several experiments).

IV. CONVERGENCE OF ASYNCHRONOUS DECENTRALIZED ESTIMATION ALGORITHM
In this section convergence properties of Algorithm 1 are established under the assumptions below. The two main theoretical results, Thm. 1 and Thm. 2, establish that the proposed algorithm attains asymptotic agreement (consensus) and asymptotic consistency, respectively. Several technical lemmas are necessary and are proven in the appendices. A block diagram showing the interdependencies between the lemmas and theorems in this section is shown in Fig. 1.  The flow of the analysis for establishing convergence of the asynchronous decentralized 20-questions algorithm to the correct consensus limit.
According to Algorithm 1, the density evolution described by (1) can be written in matrix form as: where A t accounts for the averaging action of the iteration and D t (x) is the innovation. According to Algorithm 1, it follows that with probability q i P i,j , agents i and j collaborate, resulting in:

A. Assumptions
To simplify the analysis of Algorithm 1, we make the following assumptions, which are comparable to those made in [1], [2] and [16].
Each agent's response is governed by the conditional distribution: Assumption 1. (Memoryless Binary Symmetric Channels) We model the agents' responses as independent (memoryless) binary symmetric channels (BSC) [19] with crossover probabilities i ∈ (0, 1/2]. The probability mass function f Define the set of agents I 1 = {i ∈ N : i < 1/2} and assume the set I 1 is nonempty. The condition i < 1/2 implies that the response of an agent i is 'almost correct'. Agents i / ∈ I 1 do not have the ability to localize the target on their own. Assumption 2. (Average Strong Connectivity) As in [16], we assume that the network is strongly connected on average, i.e. A = E[A t ] = i,j q i P i,j A i→j is irreducible. Furthermore, we assume α = min i α i > 0 to ensure collaboration.
The following standard assumption about the network connectivity over time [20], [21], [22], [23], [24] will be made to prove the correctness of the asymptotic limit of CDF's in Thm. 2. We remark that this assumption is not needed to prove asymptotic consensus (Thm. 1).
This condition is true with high probability as R gets large.

B. Analysis
The principal component that enables the proofs of convergence of Algorithm 1 is Equation (1), that propagates the vector of belief functions forward in time. In (2), A t = A it→jt is the time-varying interaction matrix between agents i t and j t and D t (x) = D it→jt (x) is a diagonal time-varying matrix dependent on the response of agent i, y i,t+1 , the query region A it,t ⊂ X and the state x ∈ X . For intuition, (2) can be written as a sum of two terms: The first term simply zeroes out the i and j components and the second term fills them in with the average between the updated belief of agent i and the current belief of agent j. The rest of the components are left intact.
Proposition 1 provides bounds on the dynamic range of Ax, where x is any arbitrary vector (see Theorem 3.1 in [25]). The coefficient of ergodicity of an interaction matrix A is defined as [25], [26]: This coefficient satisfies τ 1 (·) ∈ [0, 1]. The most non-ergodic interaction matrix is the identity matrix I M , for which τ 1 (I M ) = 1 and there is no information sharing, and the other extreme is the full-rank matrix τ 1 ( 1 M 11 T ) = 0. Proposition 1. (Contraction Property of A) Assume A = {a i,j } is a M × M stochastic matrix. Let x be an arbitrary non-negative vector. Then, we have for all pairs (i, j): is, which is used in Lemmas 2,3. Next, we recall a tight smooth approximation to the non-smooth maximum and minima operators. Similar results have appeared in Prop. 1 in [27] and p. 72 in [28]. and Lemma 1. Consider Algorithm 1. Let B ∈ B(X ). Then, we have: where D t (x) was defined in (4).
Proof: See Appendix A. Proof: See Appendix B. Lemmas 1 and 2 imply that the term B v T D t (x)p t (x)dx is a martingale difference noise term. where Then, we have Λ t a.s.
Proof: See Appendix C. Proof: See Appendix D. Define the dynamic range (with respect to all agents in the network) of the posterior probability that X * lies in set B ⊂ X : Also, define the innovation: We next prove a lemma that shows that the dynamic range V t (B) has a useful upper bound.
Then, for all R ∈ N: Proof: See Appendix E. To show convergence of the integrated beliefs of all agents in the network to a common limiting belief, it suffices to show V t (B) i.p.
→ 0. Theorem 1 shows convergence of asymptotic beliefs to a common limiting belief. The structure of the limiting belief is given in Theorem 2.
Proof: See Appendix F. Theorem 1 establishes that Algorithm 1 produces belief functions that become identical over all agents. This establishes asymptotic consensus among the beliefs, i.e., that as time goes on all agents come to agreement about the uncertainty in the target state. It remains to show the limiting belief is in fact concentrated at the true target state X * (Thm. 2). Lemma 6. Consider Algorithm 1. Assume p i,0 (X * ) > 0, ∀i ∈ N . Then, the posteriors evaluated at the true target state X * have the following asymptotic behavior: for some c i > 0.
Proof: See Appendix G. Now, we are ready to prove the main consistency result of the asymptotic beliefs. The proof is based on the consensus result of Theorem 1.
as t → ∞. In addition, for all i ∈ N :X Proof: Theorem 1 implies that for each agent i, as t → ∞, where F ∞ (b) is a common limiting random variable. To finish the proof, we show F ∞ (b) is equal to the constant I(b > X * ). Lemma 6 implies that M i=1 c i log p i,mR (X * ) → ∞ almost surely as m → ∞. Thus, there exists an agent i 0 ∈ I 1 such that p i0,mR (X * ) → ∞. Lemma 4 implies µ i0,t (b ) = min{F i0,t (b ), 1 − F i0,t (b )} a.s. → 0 for any b ∈ [0, 1]. This asymptotic result, combined with the monotonicity of the CDF operator F i0,t (·) and p i0,mR (X * ) a.s.
The second part (i.e., (13)) of the proof is identical to the one of Theorem 2 in [2].

V. EXPERIMENTAL VALIDATION
This section presents simulations that validate the theory in Section IV and demonstrate the benefits of the proposed asynchronous decentralized 20 questions algorithm. We compare the performance of the asynchronous algorithm proposed in this paper with the synchronous counterpart studied in [2], the centralized fully Bayesian estimator implemented via the basic equivalence principle derived in [1] and the standard query-based estimator with no information sharing. The root mean-squared error (RMSE) was chosen as a performance metric and we consider the performance for strongly connected geometric random graphs [29] to model ad-hoc wireless network topologies. An example geometric random graph is shown in Fig. 2. To ensure fairness in the comparisons, each algorithm iteration consists of M queries. Thus, the performance at each iteration of the synchronous setup (in which all agents are queried about the target location) should be compared with the performance at every M iterations of the asynchronous setup. This is denoted as "effective iteration" in the figures. We average performance over T = 200 Monte Carlo trials for each random graph realization. Performance is further averaged over 10 geometric random graphs to obtain the ensemble-average RMSE's. The average and worst-case RMSE metrics were calculated as: Figures 3 and 4 show the average and worst-case RMSE performance of the network as a function of iteration for the case of M = 20 homogeneous agents, i.e., all agents are unreliable with error probability = 0.45. We observe that the asynchronous and synchronous algorithms both uniformly outperform the case of no information sharing over all iterations. We remark that the asynchronous algorithm seems to have a slower asymptotic rate of convergence as compared to the synchronous algorithm, while it seems to improve the RMSE more than the synchronous counterpart for the first few iterations. This may be due to biasing effects that occur in the synchronous algorithm; i.e., the belief is perturbed by multiple unreliable neighbors at each update step. In the asynchronous algorithm on the other hand, there are less perturbations in the initial learning stage since it consists of pairwise belief averaging at each update step.   Figures 5 and 6 show the average and worst-case RMSE performance of the network for the case of M = 20 heterogeneous agents, i.e., three agents are reliable with error probability = 0.05 and the rest are unreliable with error probability = 0.45. Here, the reliable agents speed up the convergence of the unreliable agents through belief averaging. We observe the interesting result that the asynchronous algorithm uniformly outperforms the synchronous algorithm over all iterations, both in terms of average and worst-case RMSE. This can be attributed to the fact that one-way updating and pairwise averaging induce less bias when combining beliefs at each node at each update step, effectively spreading the good information around the network in a simplified fashion without being influenced too much by multiple neighbors. Thus, asynchronous implementations of the non-Bayesian decentralized 20 questions algorithm have the potential to improve network-wide estimation performance and getting closer to the centralized Bayesian performance, in addition to requiring significantly less infrastructure and computational complexity, in comparison to synchronous implementations.

VI. CONCLUSION
We introduced an asynchronous version of decentralized 20 questions with noise based on one-way updating and pairwise belief averaging, and analyzed its convergence properties. We also illustrated several benefits of information sharing as compared to no information sharing, and asynchronous vs. synchronous implementations. Asymptotic convergence properties of the agents' beliefs were derived, showing that they reach consensus to the true belief. Numerical experiments were presented to validate the convergence properties of the algorithm. APPENDIX A PROOF OF LEMMA 1 Proof: Note the following: Decomposing the inner term, we obtain: where we used the fact that Z i,t (y) = 1/2 for all y ∈ Y. This follows from the probabilistic bisection property: where we used the fact f , it follows that: Taking the conditional expectation, and using E[f (i) 1 (y i,t+1 )] = 1/2, we obtain: This concludes the lemma.

APPENDIX B PROOF OF LEMMA 2
Proof: From the tower property of conditional expectation, we obtain: where we used the result of Lemma 1. From strong connectivity (i.e., Assumption 2), it follows that A is an irreducible stochastic matrix. Thus, there exists a left eigenvector v ∈ R M with strictly positive entries corresponding to a unit eigenvalue-i.e., v T = v T A [30]. Multiplying both sides of (15) from the left by v T , we obtain Thus, the process {v T P t (B) : t ≥ 0} is a martingale with respect to the filtration F t . We note that it is bounded below by zero and above by v 1 almost surely. From the martingale convergence theorem [31], it follows that it converges almost surely.
APPENDIX C PROOF OF LEMMA 3 Proof: Define the tilted measure variable ζ t (B) def = exp(v T P t (B)). From Lemma 2 and Jensen's inequality, it follows that so the process {ζ t (B) : t ≥ 0} is a submartingale with respect to the filtration F t . From the proof of Lemma 2, it follows that ζ t (B) is bounded a.s., so by the martingale convergence theorem [31], it follows that lim t→∞ ζ t (B) exists and is finite almost surely. Define the ratio β t+1 (B) def = ζt+1(B) ζt(B) . As a result, we have from Lemma 2: lim a.s.

= 1
Since the variables in the limit on the LHS are bounded a.s., i.e., |β t+1 (B)| ≤ e v 1 , the dominated convergence theorem for conditional expectations [32] implies: as t → ∞. The conditional expectation can be expanded as: Next, we analyze the ratio of exponentials for two separate cases. First, consider the case Using this fact and P (Y i,t+1 = y|F t , (i, j)) = 1/2: where we used the fact that (e a +e −a )/2 = cosh(a). Second, considering the complementary case P i,t ([0, b]) > 1/2, it follows that b >X i,t , and: Combining the two cases (18) and (19) and using the definition of µ i,t (B), we obtain: The proof is completed by substituting this expression into (17).

APPENDIX D PROOF OF LEMMA 4
Proof: Using the definition of Λ t , Jensen's inequality and the eigenrelation v T = v T A: We also used the fact that e a +e −a Proof: Integrating both sides of the recursion (2): Unrolling (20) over R steps: Since the product of stochastic matrices is also a stochastic matrix, Proposition 1 implies:

APPENDIX F PROOF OF THEOREM 1
Proof: From Lemma 5, we obtain: We next show that the remainder is asymptotically negligible-i.e., Re-writing the remainder term: In order to show (22), it suffices to show: Note that if (23)  → 0 as t + R − k − 1 → ∞, and as a result, (22) follows. Thus, we next focus on proving the bound (23).
Using Proposition 2, we obtain for any γ > 0: where we used Jensen's inequality and the linearity of expectation. Next, note that the (conditional) moment generating functions of the innovation terms can be written as a weighted average of hyperbolic cosines: for any β ∈ R. To prove (25), set t = t + R − k − 1, and proceed similarly as in the proof of Lemma 3: Plugging (25) into (24) and using Proposition 2 again, we obtain: We have now proven (23) by taking γ → ∞ to tighten the bound.
→ 0, for all i ∈ I 1 . Note that here we used the positivity of the weights α i along with the fact that i < 1/2. Define the non-negative sequence  (26): where E[δ  Proof: Evaluating the density update at x = X * : p t+1 (X * ) = A t p t (X * ) + D t (X * )p t (X * ) = l =it,jt p l,t (X * )e l + [(1 − α it )p jt,t (X * ) + α it 2P (Y it,t+1 |Z it,t )p it,t (X * )] where Z i,t = I(X * ∈ A i,t ) is the query input to the noisy channel and P (Y i,t+1 |Z i,t ) models the binary symmetric channel for the ith agent. Taking the logarithm of both sides and using Jensen's inequality, we obtain for a collaborating agent pair (i t , j t ): log p it,t+1 (X * ) = log[(1 − α it )p jt,t (X * ) + α it (2P (Y it,t+1 |Z it,t ))p it (X * )] ≥ (1 − α it ) log p jt,t (X * ) + α it log p it,t (X * ) + α it log(2P (Y it,t+1 |Z it,t )) Writing this in vector form with the understanding that the logarithm of a vector is taken component-wise: log p t+1 (X * ) A t log p t (X * ) + α log(2P (Y t |Z t ))(e it + e jt ) (28) where we defined the response and query variables at time t as Y t = Y it,t+1 and Z t = Z it,t . Define the matrix product Φ t1:t2 def = A t2 A t2−1 · · · A t1 for t 1 ≤ t 2 , and Φ t1:t2 = I for t 1 > t 2 . Using induction on (28), we obtain: log p t+R (X * ) Φ t:t+R−1 log p t (X * ) where we used the bound c T Φ t+R+1−k:t+R−1 e i ≥ c · α R , ∀i, for k = 1, . . . , R. By induction, we have for m ∈ N: = α · c · α R · E R k=1 log(2P (Y R−k |Z R−k )) ≥ α · c · α R · C max i∈I1 i =: K > 0 where C( ) is the channel capacity of a BSC with crossover probability .