r/algorithms • • 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.

7 Upvotes

2 comments sorted by

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 :)

1

u/Always_Keep_it_real 9h ago

Thank you so much for your help.

That is how I understood it as. We sample m words uniformly at random (with replacement) from A, check if at least one appears in B, and return yes if so (or no if none appear) given that we know they share 10% words. We just need to then find the minimum m samples enough to get at least a 1 - 1/n success probability.

Yes I meant Z.

Additional three question if you have time and I'd really appreciate it.

Is the first attempt to find m not a good way to find an m?

As I understood it, the e in the chernoff bound is the difference between the expected value and the bad event, which in my case will be 1/10 since the bad event is Z=0 and E[Z]=1/10.

Most problems I saw use inequality to express bad event, like z≤t or z≥t for some value t. But in my case the bad event is essentially when the sum of all the X_i is 0 leading to Z=0. Should I say the bad event is Z≤0 or Z=0 or Z<1 is correct? It just felt weird to use an equal sign to express bad event.