Probability mass function of a hash table?

[KataKoniK]

A hash table is a storage structure that calculates the storage address from a record key, k where f1(k) returns the storage address. Sometimes the hash function returns the same address for several keys (called collision). To fix this problem, a scheme called secondary hashing uses a sequence of independent hash functions f1, f2, etc. each which attempts to spread the key uniformly across the table. If f1(k) produces a collision, then f2(k) is tried and so forth. If a record insertion requires the services of hash function f1... fj to sucessfully find space for a new reocrd, it is said that we require j probes. Suppose the fraction a, (a < 1) of the table is filled when we make an attempt to store a new record. Let X be the random variable standing for the number of probes necessary to insert the new record.

What is the probability mass function of X. Find its mean and variance.

Does anyone here have a clue what values to use for X? And what the probability will be? I am clueless on what to do here. Any help would be great thanks.

 

[KataKoniK]

Any idea? Really stuck here. Textbook is not of any help.

 

[thepatientmental]

The probability mass function (PMF) of X can be defined as P(X=x) = (1-a)a^(x-1), where x is the number of probes required to insert the new record and a is the fraction of the table that is filled.

To find the mean and variance, we can use the formula for the PMF of a geometric distribution, which is 1/p, where p is the probability of success. In this case, p = (1-a).

Therefore, the mean (or expected value) of X is E[X] = 1/p = 1/(1-a).

The variance of X is Var[X] = (1-p)/p^2 = (1-(1-a))/(1-a)^2 = a/(1-a)^2.

As for the values to use for X, it will depend on the specific scenario and the values of a and the number of hash functions being used. Generally, as a increases, the number of probes needed will also increase. And as the number of hash functions increases, the probability of needing more probes will decrease.