احتمال اینکه دو عنصر i,j به یک خانه نگاشته شوند برابر احتمال این که i به خانه‌ی خاصی نگاشته شود ضربدر احتمال اینکه j به همان خانه نگاشته شود که میشه برابر [tex]\frac{1}{m}*\frac{1}{m}[/tex]
حال [tex]c(2,n)[/tex] زوج متفاوت داریم پس میشه [tex]\frac{\frac{n(n-1)}{2}}^{m^2}[/tex]
گزینه ۴/
در حالی که گزینه ۳ درسته.
چرا؟
من فکر میکنم احتمال اینکه i,j هر دو به یک خانه اشاره کنند [tex]\binom{m}{1}*1/m^{2}[/tex]
چون میشه حالتی که برخورد پیش میاد تقسیم بر کل حالات . که تعداد حالات برخورد به این صورت بدست میاد که برای عنصر اول m حالت داریم (چون احتمالشون برابره فرقی نداره اول کدوم رو بگذاریم) و برای عنصر دوم یک حالت چون اجبارا باید به همان خونه نگاشت بشه.
و مخرج هم m^2 است چون برای عنصر اول m حالت و برای عنصر دوم نیز m حالت داریم.
۱- برای هر جفت کلید مجزای k و n ([tex]n\neq k[/tex]
)، یک متغییر تصادفی تعریف می کنیم به صورت زیر:
[tex]Xij=I\left \{ h(n)=h(k) \right \}[/tex]
دقت کنید متغییر تصادفی بالا وقتی تابع hash برای دو کلید یه مقدار یکسان تولید کنه برابر عدد یک میشه:
پس احتمال و امید ریاضی اون برابر میشه با:
[tex]P\left \{ Xij=1 \right \}= P\left \{ h(n)=h(k) \right \}=1/m[/tex]
[tex]E\left [ Xij \right ]=1/m[/tex]
خوب حالا یه متغییر تصادفی دیگه مثلا Y تعریف می کنیم که تمام برخوردها را در بر میگیره:
[tex]Y=\sum_{n\neq k}Xij[/tex]
پس امید برخوردها یعنی Y رو بدست میاریم:
[tex]E\left [ Y \right ]= E\left [ \sum_{n\neq k}Xij \right ]=\sum_{n\neq k}E\left [ Xij \right ]=\binom{n}{2}*1/m[/tex]
توجه کنید به ازای هر دو مقداری که تابع Hash بدست میاره اونهم در صورت برابری احتمالش اون موقعه میشه [tex]1/m[/tex]
بحث ما روی تابع hash و برخورد،این دوتا رو که با هم در نظر بگیری اون موقع برای دو عنصر احتمالش میشه [tex]1/m[/tex] نه [tex]1/\left (m ^{2} \right )[/tex]