Asymptotic results for the number of Wagner's solutions to a generalised birthday problem

preprint2015arXivOpen access

Abstract

We study two functionals of a random matrix A\boldsymbol A with independent elements uniformly distributed over the cyclic group of integers {0,1,…,M−1}\{0,1,\ldots, M-1\} modulo MM. One of them, V0(A)V_0(\boldsymbol A) with mean μμ, gives the total number of solutions for a generalised birthday problem, and the other, W(A)W(\boldsymbol A) with mean λλ, gives the number of solutions detected by Wagner's tree based algorithm. We establish two limit theorems. Theorem 2.1 describes an asymptotical behaviour of the ratio λ/μλ/μ as M→∞M\to\infty. Theorem 2.2 suggests Chen-Stein bounds for the total variation distance between Poisson distribution and distributions of V0V_{0} and WW.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.