Recent research on Doeblin coefficients has shed light on their usefulness as a multi-way generalization of the Dobrushin contraction coefficient for TV distance, in a separate vein from their classic role in the theory of Markov chain ergodicity. However, strong conditions, such as being bounded away from 0, are typically necessary for Doeblin coefficients to establish the existence of information contraction. Building on recently formulated concepts of nonlinear information contraction, we aim to propose a finer-grained Doeblin-based characterization of multi-way contraction behavior which yields non-vacuous contraction guarantees even for channels whose Doeblin coefficient is 0. To this end, we introduce the notion of aDoeblin curve—a nonlinear function which quantifies the contraction behavior of a Markov kernel on collections of input distributions at specific levels of divergence and power. Through the course of our analysis, we develop a new variational characterization of Doeblin coefficients, present several properties of Doeblin curves, define several versions of power-constrained Doeblin curves, and derive upper and lower bounds using our aforementioned variational characterization. We then utilize these results in diverse areas, including generalization bounds for noisy iterative optimization, error bounds for reliable computation with noisy circuits, and differential privacy guarantees for online iterative algorithms. In particular, we extend results in these areas to broader domains or group settings, leveraging Doeblin curves to reveal finer-grained contraction phenomena than Doeblin coefficients.

In this work, we develop a hypothesis testing framework to determine whether pairwise comparison data is generated by an underlying generalized Thurstone model $\mathcal{T}_F$ for a given choice function $F$. While prior work has predominantly focused on parameter estimation and uncertainty quantification for such models, we address the fundamental problem of minimax hypothesis testing for $\mathcal{T}_F$ models. We formulate this testing problem by introducing a notion of separation distance between general pairwise comparison models and the class of $\mathcal{T}_F$ models. We then derive upper and lower bounds on the critical threshold for testing that depend on the topology of the observation graph. For the special case of complete observation graphs, this threshold scales as $\Theta((nk)^{-1/2})$, where $n$ is the number of agents and $k$ is the number of comparisons per pair. Furthermore, we propose a hypothesis test based on our separation distance, construct confidence intervals, establish time-uniform bounds on the probabilities of type I and II errors using reverse martingale techniques, and derive minimax lower bounds using information-theoretic methods. Finally, we validate our results through experiments on synthetic and real-world datasets.

Maximal leakage quantifies the leakage of information from data$X \in \mathcal{X}$due to an observation$Y$. While fundamental properties of maximal leakage, such as data processing, sub-additivity, and its connection to mutual information, are well-established, its behavior over Bayesian networks is not well-understood and existing bounds are primarily limited to binary$\mathcal{X}$. In this paper, we investigate the behavior of maximal leakage over Bayesian networks with finite alphabets. Our bounds on maximal leakage are established by utilizing coupling-based characterizations which exist for channels satisfying certain conditions. Furthermore, we provide more general conditions under which such coupling characterizations hold for$\vert \mathcal{X} \vert =4$. In the course of our analysis, we also present a new simultaneous coupling result on maximal leakage exponents. Finally, we illustrate the effectiveness of the proposed bounds with some examples.

The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a collection of items or agents based on pairwise comparisons among them. Specifically, givennagents, the BTL model endows each agentiwith a latent skill score αi> 0 and posits that the probability that agentiis preferred over agentjin a comparison is αi/(αi+ αj). In this work, our objective is to formulate a hypothesis test that determines whether a given pairwise comparison dataset, withkcomparisons per pair of agents, originates from an underlying BTL model. We formalize this testing problem in the minimax sense and define the critical threshold of the problem. We then establish upper bounds on the critical threshold for general observation graphs and highlight their dependence on two fundamental structural properties: principal ratio and edge expansion. Additionally, we derive lower bounds on the critical threshold for the special case of complete induced graphs, thereby demonstrating that the critical threshold scales as Θ((nk)−1/2) in a minimax sense in this case. In particular, our test statistic for the upper bounds is based on a new approximation we derive for the separation distance between general pairwise comparison models and the class of BTL models. To further assess the performance of our statistical test, we prove upper bounds on conditional probabilities of error. Additionally, we derive several other auxiliary results over the course of our analysis, such as bounds on principal ratios of graphs, ℓ2-bounds on BTL parameter estimation under model mismatch, stability of rankings under the BTL model with small model mismatch, etc. Finally, we conduct several experiments on synthetic and real-world datasets to validate some of our theoretical results. Moreover, we also propose an approach based on permutation testing to determine the threshold of our test in a data-driven manner in these experiments.

Doeblin coefficients are fundamental tools in the analysis of Markov chains for establishing ergodicity and exponential convergence rates. However, strong conditions, such as Doeblin coefficients being bounded away from 0, are typically required to yield useful convergence or information contraction guarantees. Our work aims to illuminate the contraction behavior of Markov kernels under more relaxed conditions, such as the case where Doeblin coefficients are 0. To do this, we introduce the notion of a Doeblin curve—a nonlinear function that quantifies the contraction behavior of a Markov kernel on a collection of input distributions. We develop new variational characterizations of Doeblin coefficients and use them to derive useful bounds on the Doeblin curve. In the course of this analysis, we present several properties of Doeblin curves and define power-constrained Doeblin curves. Furthermore, our analysis motivates a generalized definition of differential privacy in the group setting. We discuss this motivation and several properties of this definition to lay the groundwork for its application in future.

Doeblin coefficients are a classical tool for analyzing the ergodicity and exponential convergence rates of Markov chains. Propelled by recent works on contraction coefficients of strong data processing inequalities, we investigate whether Doeblin coefficients also exhibit some of the notable properties of canonical contraction coefficients. In this paper, we present several new structural and geometric properties of Doeblin coefficients. Specifically, we show that Doeblin coefficients form a multi-way divergence, exhibit tensorization, and possess an extremal trace characterization. We then show that they also have extremal coupling and simultaneously maximal coupling characterizations. By leveraging these characterizations, we demonstrate that Doeblin coefficients act as a nice generalization of the well-known total variation (TV) distance to a multi-way divergence, enabling us to measure the “distance” between multiple distributions rather than just two. We then prove that Doeblin coefficients exhibit contraction properties over Bayesian networks similar to other canonical contraction coefficients. We additionally derive some other results and discuss an application of Doeblin coefficients to distribution fusion. Finally, in a complementary vein, we introduce and discuss three new quantities:max-Doeblin coefficient,max-DeGroot distance, andmin-DeGroot distance. The max-Doeblin coefficient shares a connection with the concept of maximal leakage in information security; we explore its properties and provide a coupling characterization. On the other hand, the max-DeGroot and min-DeGroot measures extend the concept of DeGroot distance to multiple distributions.

Doeblin coefficients are a classical tool to study the ergodicity of Markov chains. Propelled by recent works on contraction coefficients of strong data processing inequalities, we investigate whether Doeblin coefficients also exhibit some of the notable properties of canonical contraction coefficients. Specifically, we present various new structural and geometric properties of Doeblin coefficients. Then, by establishing an extremal coupling characterization, we show that Doeblin coefficients generalize the well-known total variation (TV) distance to a multi-way divergence, enabling us to measure the distance between multiple distributions rather than just two. We also demonstrate that Doeblin coefficients exhibit contraction properties over Bayesian networks similar to other canonical contraction coefficients. Finally, we discuss how Doeblin coefficients can be used to define a new rule for fusion of probability mass functions.

The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a set of items given data about pairwise comparisons among them. While several studies in the literature have attempted to empirically test how accurately a BTL model can model some given pairwise comparison data, this work aims to develop a formal, computationally efficient hypothesis test to determine whether the BTL model accurately represents the data. Specifically, we first propose such a formal hypothesis test, establish an upper bound on the critical radius of the proposed test, and then provide a complementary lower bound on the critical radius. Our bounds prove the minimax optimality of the scaling of the critical radius with respect to the number of items (up to constant factors). Finally, we also take the first step towards characterizing the stability of rankings under the BTL model when there is a small model mismatch.

Recently, different architectures based on coding theory have been proposed to reduce the storage and communication costs associated with a blockchain system. However, many of these methods have high bandwidth requirements for repairing the share of a failed node or decoding a particular requested block. The bandwidth required for decoding a requested block becomes an important factor in some blockchain applications like healthcare, where historical data needs to be frequently accessed. In this work, we introduce two new architectures for blockchain-based systems, which reduce the storage and communication costs associated with blockchain’s historical data and simultaneously provides confidentiality of the stored data. The two protocols are designed using a combination of fountain codes and a proposed communication and repair efficient secret sharing scheme. We also present a construction of the secret sharing scheme which meets our requirements.