If m is the number of bits in the array, k is the number of hash functions and we have

rmd1228887e 2022-07-02 Answered
If m is the number of bits in the array, k is the number of hash functions and we have n entries, then the false positive probability upper bound can be approximated as:
( 1 e k n m ) k
It further states in the wiki article that:
"The number of hash functions, k, must be a positive integer. Putting this constraint aside, for a given m and n, the value of k that minimizes the false positive probability is:"
k = m n ln 2
How can I find the k value that minimizes the false positive function ?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

treccinair
Answered 2022-07-03 Author has 18 answers
Let f ( k ) = ( 1 e k n m ) k = ( 1 e a k ) k where a = n / m
Then
f ( k ) = ( ( 1 e a k ) k ) = ( e k ln ( 1 e a k ) ) = ( k ln ( 1 e a k ) ) ( e k ln ( 1 e a k ) ) since  ( e g ( k ) ) = g ( k ) e g ( k ) = ( ln ( 1 e a k ) + k ( ln ( 1 e a k ) ) ) ( e k ln ( 1 e a k ) ) = ( ln ( 1 e a k ) + k ( 1 e a k ) 1 e a k ) ( 1 e a k ) k since  ( ln ( g ) ) = g g = ( ln ( 1 e a k ) + k a e a k 1 e a k ) ( 1 e a k ) k = ln ( 1 e a k ) ( 1 e a k ) k a e a k 1 e a k ( 1 e a k ) k = 0 when  ( 1 e a k ) ln ( 1 e a k ) = k a e a k
Let 1 e a k = y, so k = ln ( 1 y ) / a.
Then ( 1 e a k ) ln ( 1 e a k ) = k a e a k becomes y ln ( y ) = ( ln ( 1 y ) / a ) ( 1 y ) or y y = ( 1 y ) ( 1 y ) / a .

We have step-by-step solutions for your answer!

Ryan Robertson
Answered 2022-07-04 Author has 3 answers
You helped me with the same problem, thanks!

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-21
How to calculate the false negative, the true negative, the false positive and the true positive to form a confusion matrix. A numeric example would clear all doubts I think.
asked 2022-08-09
One in two hundred people in a population have a particular disease. A diagnosis test gives a false positive 3% of the time, and a false negative 2% of the time. Ross takes the test and the report comes positive. Find the probability that Ross has the disease.
asked 2022-04-30
3% of the population has disease X.
A laboratory blood test has
(a) 96% effective at detecting disease X, given that the person actually has it.
(b) 1% “false positive” rate. i.e, a person who does not have disease X has a probability of 0.01 of obtaining a test result implying they have the disease.
What is the probability a person has the disease given that the test result is positive?
asked 2022-06-10
5% of the population have the disease (D). A test is available that has a 10% false positive and a 10% false negative rate.
part (B) of the question asks what is the probability of having the disease given that you test positive. I'm quite confident the answer to this is ~ 32%
Part (D) - Suppose that there is no cost or benefit from testing negative but a benefit B from true positives which detect the disease and a cost C to false positives.
i) What is the expected value of the testing programme?
ii) What benefit-cost ratio would you require to proceed with the testing programme?
I'm not quite sure to how to answer either of part D. My somewhat educated guesses are
the expected value = 0.045B - 0.095C
and the benefit to cost ratio required to proceed with the testing programme is 2.11 (or greater)
asked 2022-05-01
The latest worldwide virus has an infection rate of 0.1 % (that is, 1 in 1000 people actually have the virus). The chance that someone who has the virus tests positive is said to be 99 %. The chance that someone who does not have the virus tests negative is also said to be 99 %. What are the chances that someone who tests positive does not in fact have the virus (a “false positive”)?
asked 2022-06-01
According to my research the Fowlkes-Mallows Index should be a good tool to get a comparable evaluation score, but I am not sure about the correct application.
Currently I calculate the true positives, false positives and false negatives for each cluster, then sum them together for total values and add them in the formula.
F M = T P T P + F P T P T P + F N
where T P is the number of true positives, F P is the number of false positives, and F N is the number of false negatives.
Is this the correct application of the Algorithm?
asked 2022-05-08
My problem is the following. I like to know if there exist a sentence true in complex a field but false in a field of positive characteristic.

New questions