Mathematics – Probability
Scientific paper
2004-08-03
Mathematics
Probability
i+11 pp
Scientific paper
We show that if X and Y are integers independently and uniformly distributed in the set {1, ..., N}, then the information lost in forming their product (which is given by the equivocation H(X,Y | XY)), is of order log log N. We also prove two extremal results regarding cases in which X and Y are not necessarily independently or uniformly distributed. First, we note that the information lost in multiplication can of course be 0. We show that the condition H(X,Y | XY) = 0 implies that 2log_2 N - H(X, Y) is of order at least log log N. Furthermore, if X and Y are independent and uniformly distributed on disjoint sets of primes, it is possible to have H(X,Y | XY) = 0 with log_2 N - H(X) and log_2 N - H(Y) each of order at most log log N. Second, we show that however X and Y are distributed, H(X,Y | XY) is of order at most log N/log log N. Furthermore, there are distributions (in which X and Y are independent and uniformly distributed over sets of numbers having only small and distinct prime factors) for which H(X,Y | XY) is of order log log N.
No associations
LandOfFree
The average amount of information lost in multiplication 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 The average amount of information lost in multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The average amount of information lost in multiplication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-307538