How to prove the expected number of probes in Open addressing

Question

The outline of my following content

• background

• question

1.background

• theorem 11.6 and Proof process

• questions

questions in the background

(1) my first question is why Pr{X>=i} but not Pr{X==i} ?

(2) my second question is Why Pr{A1} = n/m ?

I have some thought for question(2) in my figure.

Answer 1

你的第二的问题挺显然的，第一次就撞上被占用格子的概率就是load factor（n/m）啊。

第一个问题把m,n换成具体的数字就好理解了。比如100个格子里面占用了10个，空闲90个：

$$\array{Pr\{X \geq 3\} = Pr\{\text{前两次都撞到占用}\} \\\qquad = \frac{10}{100} \cdot \frac{9}{99}}$$

不同于

$$\matrix{Pr\{X = 3\} = Pr\{\text{前两次都撞到占用，第三次撞到空闲}\} \\= \frac{10}{100} \cdot \frac{9}{99} \cdot \frac{90}{98}}$$