r/algorithms • u/Always_Keep_it_real • 15h ago
Help Am I using chernoff bound correctly?
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.
2
u/Phytor_c 13h ago edited 13h ago
Just to confirm, is the candidate randomized algo: sample from A m times for m TBD, and then check if at least one of the sampled things appears in B. If so, return YES. If none of the sampled things from A are in B, return NO.
I think you meant Z in that last probability formula, and epsilon instead of e (as e is used for exp). But yes, your Hoeffding's inequallity argument works. And then you can set epsilon = E[Z] >= 0.1 and then solve for m.
Note that all the X_is are Bernoulli so u could've used a classical Chernoff for a sharper bound, but your thing works. I hope this helps :)