Consider a target moving at a constant velocity on a unit-circumference circle, starting at an arbitrary location. To acquire the target, any region of the circle can be probed to obtain a noisy measurement of the target's presence, where the noise level increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity and a given reliability, we provide an asymptotical characterization of the optimal tradeoff between time and resolution. Considering an asymptotically diminishing error probability, we derive the maximal targeting rate, and show that in contrast to the well-studied case of constant measurement noise, measurement dependent noise incurs a multiplicative gap in the maximal targeting rate between adaptive and non-adaptive search strategies. Moreover, for all rates below this maximal rate, our adaptive strategy attains the optimal rate-reliability tradeoff. We further show that accounting for a target moving at an unknown fixed velocity, the optimal non-adaptive search strategy incurs a factor of at least two in the maximal targeting rate.

In this paper we describe a general algorithmic scheme for communication over any memoryless channel in the presence of noiseless feedback. The scheme is based on the idea of posterior matching, in which the information still missing at the receiver is extracted from the a-posteriori density function, and matched to any desirable input distribution. We analyze the error probability attained by this scheme for additive noise channels, and show that the well-known Schalkwijk-Kailath scheme for the AWGN channel with average power constraint and the Horstein scheme for the BSC, can be derived as special cases.

Consider two sequences of n independent and identically distributed fair coin tosses, X = (X1,...,Xn) and Y = (Y1,...,Yn), which are ρ-correlated for each j, i.e. P[Xj = Yj] = 1+ρ/2. We study the question of how large (small) the probability P[X ∈ A; Y ∈ B] can be among all sets A;B ⊂ {0,1} of a given cardinality. For sets |A| |B| = Θ(2n) it is well known that the largest (smallest) probability is approximately attained by concentric (anticoncentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of |A| |B| = 2Θ(n). By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize P[X ∈ A; Y ∈ B] in the regime of ρ → 1. We also prove a similar tight lower bound, i.e. show that for ρ → 0 the pair of opposite Hamming balls approximately minimizes the probability P[X ∈ A; Y ∈ B].

We study a distributed estimation problem in which two remotely located parties, Alice and Bob, observe an unlimited number of i.i.d. samples corresponding to two different parts of a random vector. Alice can send k bits on average to Bob, who in turn wants to estimate the cross-correlation matrix between the two parts of the vector. In the case where the parties observe jointly Gaussian scalar random variables with an unknown correlation ρ, we obtain two constructive and simple unbiased estimators attaining a variance of (1-ρ2)=(2k ln 2), which coincides with a known but non-constructive random coding result of Zhang and Berger. We extend our approach to the vector Gaussian case, which has not been treated before, and construct an estimator that is uniformly better than the scalar estimator applied separately to each of the correlations. We then show that the Gaussian performance can essentially be attained even when the distribution is completely unknown. This in particular implies that in the general problem of distributed correlation estimation, the variance can decay at least as O(1=k) with the number of transmitted bits. This behavior, however, is not tight: we give an example of a rich family of distributions for which local samples reveal essentially nothing about the correlations, and where a slightly modified estimator attains a variance of 2-Ω(k).

Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof, showing that it achieves capacity for a large class of memoryless channels. Naghshvar et al. considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel extrinsic Jensen-Shannon divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential randomized horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system decoder.

Alice holds a random variable $X$ , and Bob is trying to guess its value by asking questions of the form “is $X=x$ ?”. Alice answers truthfully and the game terminates once Bob guesses correctly. Before the game begins, Bob is allowed to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a question of the form “is $X\in A$ ?”. Carole is known to lie with a given probability $p$ . What should Bob ask Carole if he would like to minimize his expected guessing time? When Carole is always truthful ( $p=0$ ), it is not difficult to check that Bob should order the symbol probabilities in descending order and ask Carole whether the index of $X$ with respect to this order is even or odd. We show that this strategy is almost optimal for any lying probability $p$ , up to a small additive constant upper bounded by 1/4. We discuss a connection to the cutoff rate of the BSC with feedback.