r/algorithms • • 16h ago

Help Am I using chernoff bound correctly?

7 Upvotes

Given two sets A, B, each containing n words, we want to determine whether they share at least 10% of n words. We can sample m words uniformly at random from (A) and check whether they appear in (B). We want to answer YES with probability at least (1-1/n) if they share at least 10% of the n words.

I solved this exercise just using like basic math like and the porperty of independence then I solved m thru (9/10)^m <= 1/n. And I was wondering if that is a correct method or not?

I am struggling with this because in class we talked about markov's inequality and Chernoff bounds for randomized algorithms or functions . Otherwise I started with chernoff to create a random variable where X_i is 1 if the the sample is in B else 0. The probability of that P(X_i = 1 ) = 1/10, then let X be the sum of X1, ..., Xm and its expected value is m/10 due to using linearity. My bad event is P(X=0) < 1/n. To use chernoff we have to have values between 0 and 1 so I average Z = X/m. Then I use the chernoff formula P(X <= E[X] - e) <= e^{−2m e^2} to solve for m. But I feel unsure about all this and I have spent way too much time.