Recently I'm working on Chapter-11, but the Problem 11-1.a obstruct my way. I've read the corresponding answer in this project and also a more detailed explanation which I stated below:
Since we assume uniform hashing, we can use the same observation as is used
in Corollary 11.7: that inserting a key entails an unsuccessful search followed
by placing the key into the first empty slot found. As in the proof of Theorem
11.6, if we let X be the random variable denoting the number of probes
in an unsuccessful search, then Pr{X >= i} <= α^(i-1). Since n <= m/2, we have α <= 1/2. Letting i = k + 1, we have Pr{X>k} = Pr{X >= k + 1} <= (1/2)^((k+1)-1) = 2^(-k).
However, I think the one above has missed something:
Pr{X>= k + 1} should equal to Pr{X=k+1} + Pr{X=k+2} + ... + Pr{X=i}, but the Proof of Theorem 11.6 says "We will bound Pr{X>=i} by bounding Pr{A1 ^ A2 ^ ... ^Ai-1}" which only consider every probe in first (i-1)th probe sequence should be fail. It can not represent all events in set {X >= i}.
I think there should be something i misunderstand. So, is there anyone can tell me what wrong am i ? Thanks a lot!
Recently I'm working on Chapter-11, but the Problem 11-1.a obstruct my way. I've read the corresponding answer in this project and also a more detailed explanation which I stated below:
However, I think the one above has missed something: Pr{X>= k + 1} should equal to Pr{X=k+1} + Pr{X=k+2} + ... + Pr{X=i}, but the Proof of Theorem 11.6 says "We will bound Pr{X>=i} by bounding Pr{A1 ^ A2 ^ ... ^Ai-1}" which only consider every probe in first (i-1)th probe sequence should be fail. It can not represent all events in set {X >= i}.
I think there should be something i misunderstand. So, is there anyone can tell me what wrong am i ? Thanks a lot!