2011/05/19 by Yaron Shany, Shany, Yaron, Ram Zamir +1
Computer Science · Mathematics · #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.1105.3793
second version with a considerably simplified proof of the main theorem and additional references. 6 pages
arxiv created 2012/09/29 · arxiv updated 2012/10/02
In this note, it is shown that if f\colon\efqn→\efqn is any function and \bA=(A1,..., An) is uniformly distributed over \efqn, then the average over (k1,...,kn)∈ \efqn of the Renyi (and hence, of the Shannon) entropy of f(\bA)+(k1A1,...,knAn) is at least about log2(qn)-n. In fact, it is shown that the average collision probability of f(\bA)+(k1A1,...,knAn) is at most about 2n/qn.