Computer Science – Information Theory
Scientific paper
2011-07-29
Computer Science
Information Theory
Small addition in abstract. New paragraph on expectations vs. measurements in Intro between eqs. (1.1) and (1.2). In caption o
Scientific paper
Consider the construction of an object composed of $m$ parts by distributing $n$ units to those parts. For example, say we are assigning $n$ balls to $m$ boxes. Each assignment results in a certain count vector, specifying the number of balls allocated to each box. If only assignments satisfying a set of constraints that are linear in these counts are allowable, and $m$ is fixed while $n$ increases, most assignments that satisfy the constraints result in frequency vectors (normalized counts) whose entropy approaches that of the maximum entropy vector satisfying the constraints. This phenomenon of "entropy concentration" is known in various forms, and is one of the justifications of the maximum entropy method, one of the most powerful tools for solving problems with incomplete information. The appeal of entropy concentration comes from the simplicity of the argument: it is based purely on counting. Existing proofs of the concentration phenomenon are based on limits or asymptotics. Here we present non-asymptotic, explicit lower bounds on $n$ for a number of variants of the concentration result to hold to any prescribed accuracies, taking into account the fact that allocations of discrete units can satisfy constraints only approximately. The results are illustrated with examples on die tossing, vehicle or network traffic, and the probability distribution of the length of a $G / G / 1$ queue.
No associations
LandOfFree
Explicit Bounds for Entropy Concentration under Linear Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Explicit Bounds for Entropy Concentration under Linear Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit Bounds for Entropy Concentration under Linear Constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-319425