How to prove the expected number of probes in Open addressing

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.

阅读 2.8k
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}}$$

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题