परिचय

मान लीजिए मैं आपसे पूछता हूं कि कितने लोगों को एक कमरे में होना चाहिए ताकि उनमें से दो का जन्मदिन एक दिन की 50% संभावना के साथ हो। उत्तर क्या होगा? इसे ही जन्मदिन का विरोधाभास कहा जाता है।

विरोधाभास पढ़ता है:

यदि कमरे में 23 लोग हैं, तो 50% संभावना के साथ उनमें से दो एक ही दिन पैदा हुए थे।

विरोधाभास के कुछ संस्करण और भी मजबूत बयान देते हैं:

यदि कमरे में 70 लोग हैं, तो 99% की संभावना के साथ, उनमें से दो एक ही दिन पैदा हुए थे।

सबसे पहले, यह मुझे आश्चर्यचकित और प्रतिवादपूर्ण लगा। आइए जानें यह सच क्यों है। कार्य को सरल बनाने के लिए, हम निम्नलिखित धारणाएँ बनाते हैं:

1. हम मानते हैं कि कमरे में सभी लोग एक लीप वर्ष में पैदा नहीं हुए थे। हम यह धारणा बनाते हैं ताकि हमें दो अलग-अलग मामलों का विश्लेषण न करना पड़े।
2. कमरे में कोई जुड़वा बच्चे नहीं हैं। जुड़वाँ की एक जोड़ी के साथ, समाधान तुच्छ होगा।
3. हम मानते हैं कि लोग समान रूप से और यादृच्छिक रूप से पैदा होते हैं। इसका क्या मतलब है? लोगों को वर्ष के किसी भी दिन समान रूप से पैदा होने की संभावना है। यदि इसे थोड़ा औपचारिक रूप दिया जाता है, तो किसी भी चुने हुए दिन पर जन्म की संभावना बराबर होती है $$$\ frac {1} {365}$ ।
4. लोग एक-दूसरे से स्वतंत्र रूप से पैदा होते हैं। इसका मतलब यह है कि किसी भी व्यक्ति के जन्म की तारीख दूसरे के जन्म की तारीख को प्रभावित नहीं करती है।

यह ध्यान देने योग्य है कि इन शर्तों को वास्तविक दुनिया में जरूरी नहीं माना जाता है। विशेष रूप से, वास्तविक दुनिया में, लोग समान यादृच्छिकता के साथ पैदा नहीं होते हैं। इस लिंक में उन दिनों के आँकड़े हैं जिन पर लोग पैदा होते हैं। यद्यपि हमारा मॉडल वास्तविक दुनिया का सटीक प्रतिबिंब नहीं है, लेकिन इसकी सरलता से समस्या का विश्लेषण करना बहुत आसान हो जाता है।

मुझे यह कहना चाहिए कि यदि एक कमरे में 366 या अधिक लोग हैं, तो एक ही जन्मदिन पर दो लोगों के होने की गारंटी है। यह डरिकलेट सिद्धांत ("कबूतर और बक्से का सिद्धांत") से इस प्रकार है: यदि 366 लोग और 365 दिन हैं, तो कम से कम दो लोगों का जन्मदिन समान होना चाहिए।

कल्पना कीजिए कि कमरे में एक व्यक्ति है, तो किसी और के साथ उसके आम जन्मदिन की संभावना 0. लेट है $$$(A_n)$ जिसके बीच में परिणाम होगा $$$एन$ लोगों के पास एक भी जन्मदिन नहीं है। चलो $$$\ Pr [A_n]$ - संभावना है कि बीच में $$$एन$ कमरे में, हर किसी का जन्मदिन होता है। इसी तरह, चलो $$$\ overline {A_n}$ पूरक होगा $$$ए_ एन$ , यानी। जिसके बीच एक परिणाम $$$एन$ लोगों को दो लोगों को एक ही जन्मदिन है।

$$

$$\ Pr [A_n] + \ Pr [\ overline {A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \ text {क्योंकि कमरे में केवल एक व्यक्ति है}$$

मान लीजिए कि कमरे में दो लोग हैं, ए और बी सामान्यीकरण के नुकसान के बिना, बस कल्पना करें कि ए 1 जनवरी को पैदा हुआ था। बी और ए के लिए अलग-अलग जन्मदिन हैं, बी को पहली जनवरी को छोड़कर किसी भी दिन पैदा करने की आवश्यकता है। व्यक्ति बी में 364 जन्मदिन विकल्प होंगे।

$$

$$\ Pr [A_2] = \ Pr [\ text {B A} से अलग है] = \ frac {364} 365 * "$$

कल्पना कीजिए कि कमरे में तीन लोग हैं, ए, बी और सी। मान लीजिए कि व्यक्ति ए का जन्म 1 जनवरी को हुआ था, ताकि सभी का जन्म अलग-अलग दिनों में हुआ हो, व्यक्ति बी के पास केवल 364 दिन थे, जैसा कि पिछले उदाहरण में था। चूंकि A और B को दो दिन लगते हैं, व्यक्ति C केवल 365 - 2 = 363 दिनों में पैदा हो सकता है।

$$

$$\ Pr [A_3] = \ Pr [\ text {B अलग है A और C, B, A}] से भिन्न है = \ frac {364} {365} \ टाइम्स \ frac {363} {365}$$

यहां कुछ और दिलचस्प होता है: मान लीजिए कि कमरे में पहले से ही है $$$k - 1$ लोग। जब वह कमरे में प्रवेश करता है $$$k$ वह व्यक्ति $$$k$ लोगों के अलग-अलग जन्मदिन थे, दो नतीजे सच होने चाहिए

1. सब $$$k - 1$ उसके पहले कमरे में प्रवेश करने वाले लोगों के जन्मदिन अलग-अलग होने चाहिए। इसकी संभावना क्या है? $$$\ Pr [A_ {k-1}]$ ।
2. $$$k$ - उस व्यक्ति को अन्य सभी लोगों से अलग जन्मदिन की आवश्यकता होती है $$$k - 1$ कमरे में लोग। इसकी संभावना क्या है? $$$\ frac {365 - (k-1)} {365}$ ।

यह भी ध्यान दिया जाना चाहिए कि ऊपर प्रस्तुत दो परिणाम एक-दूसरे से स्वतंत्र हैं, क्योंकि पद की शुरुआत में किए गए धारणा (4) द्वारा, $$$k$ दूसरे व्यक्ति का जन्म अन्य सभी लोगों से स्वतंत्र रूप से हुआ था।

$$$ $ प्रदर्शन $ $ \ _ {आरंभ * समीकरण}} शुरू / विभाजित} \ Pr [A_k] & = \ Pr [k - 1 \ पाठ {कमरे में लोगों का अलग-अलग जन्मदिन है} \ textbf {AND} \\ & \ _ \ \ \ \ \ \ पाठ {व्यक्ति k का} k - 1 \ text {लोग}] से एक अलग जन्मदिन होता है, \\ & = \ Pr [k - 1 \ text {कमरे के लोगों का अलग-अलग जन्मदिन होता है}] \\ & \ \ \ \ \ \ बार \ Pr [\ text {व्यक्ति k का} k - 1 \ text {लोग}] से एक अलग जन्मदिन है, \\ & = \ Pr [A_ {k-1}] \ गुना \ frac { 365 - (k-1)} {365} \ end {विभाजित} \ end {समीकरण *} $ $ प्रदर्शन $ $

अब हम संभावनाओं की गणना करते हैं:

$$$ $ प्रदर्शन $ $ \ _ शुरू {समीकरण *} \ start {विभाजित} \ Pr [A_1] & = 1 \\ \ Pr [A_2] और = \ Pr [A_1] \ गुना \ frac {364} {365} = \ frac {364} {365} \ लगभग 0.997 \\ \ Pr [A_3] & = \ Pr [A_2] \ गुना \ frac {363} {365} = \ frac {364} {365} \ "frac {363} {365} \ लगभग 0.991 \\ \ Pr [A_4] & = \ Pr [A_3] \ गुना \ frac {362} {365} \ लगभग 0.983 \\ & \ vdots \\ \ Pr [A_ {22}] & = = \ Pr [A_ {21}] \ टाइम्स \ frac {344} {365} \ लगभग 0.525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ टाइम्स \ frac {343} {365 } \ लगभग 0.493 \\ \ अंत {विभाजन} \ अंत {समीकरण *} $ $ प्रदर्शन $ $

जब से हमें मिला है $$$\ Pr [A_ {23}] = 0.493 <0.5$ , इसका मतलब यह होगा कि दो लोगों के लिए एक सामान्य जन्मदिन की संभावना बराबर है

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0.493 = 0.507> 0.5$$

वृद्धि के साथ $$$एन$ संभावना 1 तक जाती है और उस तक पहुंच जाती है।

अधिक कठिन कार्य

मान लीजिए हम इस समस्या को उस स्थिति में सामान्य करना चाहते हैं जब वहाँ है $$$एन$ लोग और $$$एम$ संभव जन्मदिन। होने $$$एन, एम$ , क्या हम इस संभावना को निर्धारित कर सकते हैं कि दो लोगों का एक आम जन्मदिन होगा?

आप एक ही प्रणाली का उपयोग कर सकते हैं: हमारे पास एक परिणाम होगा $$$ए_ एन$ सभी को दर्शाते हुए $$$एन$ अलग-अलग दिनों में पैदा हुए लोग। एक व्यक्ति के मामले में, कुछ भी नहीं बदलता है

$$

$$\ Pr [A_1] = 1$$

ऐसे मामले में जहां दो लोग हैं, हम उन्हें ए और बी के रूप में नामित करते हैं। व्यक्ति बी दूसरे दिन पैदा होने के लिए, व्यक्ति बी के बीच जन्मदिन होना चाहिए $$$m - 1$ अन्य विकल्प।

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

तीन लोगों के मामले में, व्यक्ति बी का जन्मदिन ए से अलग होना चाहिए। व्यक्ति सी का जन्मदिन ए और बी के जन्मदिन से अलग होना चाहिए।

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ टाइम्स \ frac {m-2} {{}$$

आम तौर पर किसी के लिए $$$एन$ हम पिछले अनुभाग के समान पुनरावर्ती सूत्र का उपयोग कर सकते हैं:

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \ टाइम्स \ frac {m - (n-1)} {m}$$

मान लीजिए अगर हम एक अभिव्यक्ति को बंद रूप में खोजना चाहते हैं $$$\ Pr [A_n]$ , तो हम अभिव्यक्ति को विघटित करते हैं

$$$ $ प्रदर्शन $ $ \ _ शुरू {समीकरण *} \ start {विभाजित} \ Pr [A_n] & = \ Pr [A_ {n-1}] \ गुना \ frac {m - (n-1)} {m} \ \ & = \ Pr [A_ {n-2}] \ टाइम्स \ frac {m - (n-2)} {m} \ टाइम्स \ frac {m - (n-1)} {m} \\ & = \ _ Pr [A_ {n-3}] \ टाइम्स \ frac {m - (n-3)} {m} \ टाइम्स \ frac {m - (n-2)} {m} \ टाइम्स \ frac {m - (n) -1)} {m} \\ & \ \ vdots \\ & = \ Pr [A_2] \ टाइम्स \ frac {m-2} {m} \ गुना \ frac {m-3} {m} \ टाइम्स \ cdots \ times \ frac {m - (n-3)} {m} \ टाइम्स \ frac {m - (n-2)} {m} \ टाइम्स \ frac {m - (n-1)} {m} \\ & = \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1 - \ frac {i} {m} \\ & \ approx \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {पहचान का उपयोग} 1 - x \ लगभग e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ लगभग e ^ {\ frac {-n ^ 2} {2m}} \ end {विभाजित} \ end {समीकरण *} $ $ $ $

इस परिणाम का एक अनुमान है $$$\ Pr [A_n] \ लगभग e ^ {\ frac {-n ^ 2} {2m}}$ । यद्यपि हम अधिक अनुमानित सीमाएँ पा सकते हैं, यह हमें एक पर्याप्त सन्निकटन देता है। एकमात्र पहचान जिसका उपयोग हमने इस सन्निकटन में किया है:

$$

$$1 - x \ लगभग e ^ {- x}$$

अपने अमूर्त रूप में, जन्मदिन के विरोधाभास का कंप्यूटर कंप्यूटिंग में कई उपयोग हैं। विशेष रूप से, इसका उपयोग हैशिंग में किया जाता है, जो अपने आप में कई उपयोग करता है। इस कार्य में किए गए निष्कर्ष हैशिंग दो तत्वों की संभावना को एक कुंजी में विश्लेषण करने के लिए महत्वपूर्ण हैं। इस समस्या को गेंदों और बेसिन (गेंदों और डिब्बे की समस्या) की संभावित समस्या के लिए और अधिक सामान्यीकृत किया जा सकता है, जिसे हम दूसरे पद पर छोड़ देंगे।

आवेदन

जन्मदिन का विरोधाभास केवल एक कृत्रिम कार्य या एक दिलचस्प पार्टी चाल नहीं है, इसमें कई वास्तविक दुनिया के अनुप्रयोग हैं। व्यक्तिगत रूप से, मेरा मानना ​​है कि साक्ष्य में प्रयुक्त संभाव्य विश्लेषण अन्य कार्यों के विश्लेषण में उपयोगी है जिसमें यादृच्छिकरण शामिल है। विशेष रूप से, यह क्रिप्टोग्राफिक हैश फ़ंक्शन के विकास से संबंधित है। हम देखेंगे कि ऊपर दिए गए विश्लेषण "जन्मदिन" के हमलों से सुरक्षा के साथ हैश फ़ंक्शन बनाने में काफी उपयोगी हो सकते हैं।

सबसे पहले, परिभाषित करते हैं कि हैश फ़ंक्शन क्या है। हैश फंक्शन $$$h: U \ rightarrow [0, m-1]$ एक फ़ंक्शन है जो एक सेट से मैपिंग करता है $$$यू$ रेंज में एक संख्या में $$$[0, एम -1]$ । समारोह $$$ज$ के रूप में परिभाषित किया गया $$$h (x) = x \ mod m$ - उदाहरण हैश फ़ंक्शन से $$$\ mathbb {N} \ rightarrow [0, m-1]$ । हैश फ़ंक्शन के कई उपयोग हैं, विशेष रूप से लोकप्रिय हैश टेबल डेटा संरचना के साथ संयोजन में। इसका उपयोग क्रिप्टोग्राफी में भी किया जाता है, जहाँ एक विशिष्ट प्रकार के हैश फ़ंक्शन को "क्रिप्टोर्फिक हैश फ़ंक्शन" कहा जाता है।

कई गुणों में से एक जो एक क्रिप्टोर्फिक हैश फ़ंक्शन के पास टकराव प्रतिरोध होना चाहिए। ऐसे दो को ढूंढना मुश्किल होगा $$$u_1, u_2 \ u में$ ताकि वे एक टकराव का निर्माण करें, अर्थात $$$h (u_1) = h (u_2)$ ।

यह टकराव के प्रतिरोध पर है जिस पर हम ध्यान केंद्रित करेंगे। पहले, मैं समझाऊंगा कि यह वांछनीय संपत्ति क्यों है। ऐसा करने के लिए, हम पहले डिजिटल हस्ताक्षर पर विचार करेंगे।

अतीत में, लोगों और संगठनों ने दस्तावेजों और मुहरों का उपयोग दस्तावेजों पर "हस्ताक्षर" करने के लिए किया था। हाल ही में, इलेक्ट्रॉनिक या डिजिटल हस्ताक्षरों के लिए संक्रमण हुआ है। एक डिजिटल हस्ताक्षर को तीन बुनियादी गुणों को पूरा करना होगा।

1. दस्तावेज़ पर हस्ताक्षर करते समय, आपको यह सत्यापित करने में सक्षम होना चाहिए कि दस्तावेज़ पर हस्ताक्षर किसने किए।
2. दस्तावेज़ पर हस्ताक्षर करने के बाद, कोई भी इसे नकली करने में सक्षम नहीं होना चाहिए।
3. दस्तावेज़ पर हस्ताक्षर करने वाले व्यक्ति बाद में दस्तावेज़ पर हस्ताक्षर करने से इनकार नहीं कर सकते।

एक डिजिटल हस्ताक्षर दस्तावेज़ या संदेश की सच्चाई को प्रमाणित करने का एक तरीका है। एक डिजिटल हस्ताक्षर यह सुनिश्चित करता है कि प्राप्त संदेश एक ज्ञात प्रेषक द्वारा बनाया गया था और परिवर्तित नहीं किया गया था।

मान लीजिए कि हमारे पास एक दस्तावेज है $$$एम$ । हम इस पर हस्ताक्षर कैसे करते हैं?

प्रत्येक उपयोगकर्ता / संगठन के पास एक अद्वितीय निजी कुंजी है $$$p_k$ और सार्वजनिक कुंजी $$$pub_k$ । वे अपने स्वयं के निजी कुंजी के साथ दस्तावेज़ पर हस्ताक्षर करने के लिए हस्ताक्षर समारोह का उपयोग करते हैं। हालांकि, एक डिजिटल हस्ताक्षर केवल कुछ दस्तावेजों पर हस्ताक्षर कर सकता है। हस्ताक्षर समारोह का दायरा छोटा है। इस समस्या को हल करने का एक तरीका एक छोटा दस्तावेज़ बनाना है जो मूल दस्तावेज़ का प्रतिनिधित्व करता है, लेकिन बहुत छोटे आकार में। सबसे अधिक बार, इस बड़े दस्तावेज़ में एक हैश फ़ंक्शन लागू होता है। एक हैश फ़ंक्शन का उपयोग इसे बड़े स्थान से छोटे स्थान पर मैप करने के लिए किया जाता है, और इस तरह के ऑपरेशन के परिणाम को "फिंगरप्रिंट" कहा जाता है। हस्ताक्षर बनाने के लिए हस्ताक्षर फिंगरप्रिंट और निजी कुंजी का उपयोग करता है। प्रक्रिया को निम्नानुसार वर्णित किया जा सकता है:

1. निजी कुंजी प्राप्त करें $$$p_k$ ।
2. एक दस्तावेज़ को हैश करें $$$एम$ और मिलता है $$$ज (एम)$ ।
3. संकेत $$$ज (एम)$ निजी कुंजी का उपयोग करना $$$p_k$ ।
4. हम भेजते हैं $$$चिन्ह (h (m), p_k)$ और सार्वजनिक कुंजी $$$pub_k$ जो कोई भी दस्तावेज़ की पुष्टि करना चाहता है।

जिसके पास भी कोई हो $$$चिन्ह (h (m), p_k))$ और सार्वजनिक कुंजी, यह देख सकती है कि दस्तावेज़ वास्तव में है या नहीं $$$एम$ सही व्यक्ति द्वारा हस्ताक्षरित।

समस्या: मान लीजिए हमलावर ईवा को दो दस्तावेज मिले $$$एम, एम '$ जहाँ $$$एम$ - यह वर्तमान अनुबंध है, और $$$म ’$ - एक कपटपूर्ण दस्तावेज़ ऐसा $$$h (m) = h (m ')$ । मान लीजिए कि ईव पहले से जानता है कि एलिस केवल हस्ताक्षर करेगा $$$एम$ लेकिन नहीं $$$म ’$ । हस्ताक्षर करने से पहले, एक क्रिप्टोग्राफिक हैश फ़ंक्शन दस्तावेज़ पर लागू होता है $$$ज$ । ईव ऐलिस के पास जाता है और उसे एक दस्तावेज पर हस्ताक्षर करने के लिए कहता है $$$एम$ ऊपर वर्णित अनुक्रम का उपयोग करना। अब, ईव दावा कर सकता है कि एलिस ने एक कपटपूर्ण दस्तावेज पर हस्ताक्षर किए $$$म ’$ क्योंकि $$$h (m) = h (m ')$ । एलिस किसी भी तरह से साबित नहीं कर पाएगी कि उसने हस्ताक्षर नहीं किए $$$म ’$ ।

ऊपर के उदाहरण में $$$ज$ एक टकराव-प्रतिरोधी फ़ंक्शन के रूप में निकला, इसलिए ईव दो आने वाले डेटा सेटों को खोजने में सक्षम था जो एक ही मूल्य को पाले हुए हैं। ईव दावा करने में सक्षम था कि ऐलिस ने हस्ताक्षर किए $$$म ’$ हालांकि वास्तव में उसने केवल हस्ताक्षर किए $$$एम$ । यह टकराव प्रतिरोध के महत्व को रेखांकित करता है और दिखाता है कि हैश फ़ंक्शन अस्थिर होने पर डिजिटल हस्ताक्षर असुरक्षित क्यों हैं।

चलो $$$h: U \ rightarrow [0, m-1]$ एक हैश फ़ंक्शन होगा। मान लें कि इनपुट डेटा अनियमित रूप से समान और स्वतंत्र रूप से किसी भी तत्व में हैशेड है $$$एम$ ।

"जन्मदिन" हमले का कार्य कम से कम तत्वों की खोज करना है $$$एन$ जिसके साथ हैश किया जा सकता है $$$ज$ ताकि हम दो तत्वों को पा सकें $$$x, y $ U मे$ जिस पर $$$h (x) = h (y)$ ।

"जन्मदिन" पर हमला करते समय, हमलावर यादृच्छिक रूप से उठाएगा $$ और जोड़े रखें $$$(x, h (x))$ । एक हमलावर बार-बार इन जोड़ों का चयन करेगा और तब तक बचाएगा जब तक कि वह दो मान नहीं पाता $$$x, y$ जिस पर $$$h (x) = h (y)$ । हमें यह निर्धारित करने की आवश्यकता है कि हमलावर को कितनी बार इस ऑपरेशन को दोहराने की आवश्यकता है जब तक कि वह टकराव न हो जाए।

"जन्मदिन" हमले का विश्लेषण करने के लिए, आप उन्हीं सिद्धांतों का उपयोग कर सकते हैं जो हमने जन्मदिन विरोधाभास के लिए उपयोग किए थे। हमले में "जन्मदिन" $$$एम$ एक वर्ष में दिनों की संख्या को दर्शाता है, और $$$यू$ एक कमरे में प्रवेश करने वाले लोगों के समान। लोग अपने जन्मदिन पर हैशेड करते हैं, जो अर्थ में से एक हो सकता है। $$$एम$ । मान लीजिए कि हमें 99% की संभाव्यता के साथ टकराव खोजने की आवश्यकता है। हमें यह जानना होगा कि सबसे छोटा क्या है $$$एन$ , जिसमें दो मूल्यों का हैश एक जन्मदिन होगा (हैश फ़ंक्शन की दुनिया में, इसका मतलब है कि दो इनपुट डेटा सेट एक ही मूल्य में हैशेड हैं)।

हमने पहले दिखाया था $$$\ Pr [A_n] \ लगभग e ^ {\ frac {-n ^ 2} {2m}}$

हम पूछना चाहते हैं $$$\ $ वह है $$$\ Pr [A_n] \ लगभग e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ ।

$$$ $ प्रदर्शन $ $ \ शुरू {समीकरण *} \ start {विभाजित} ई ^ {\ frac {-n ^ 2} {2m}} & = \ frac {1} {100} \\ \ frac {n ^ 2} {2 मी} & = \ ln 100 \\ n ^ 2 & = 2 m \ ln 100 \\ n & = \ sqrt {2 m \ ln 100} \ end {विभाजित} \ end {समीकरण *} $ $ $ $ प्रदर्शन

ऊपर दिखाया गया विश्लेषण बताता है कि आकार के अंतराल के साथ हैश कार्यों में टकराव प्राप्त करना है $$$एम$ एक हमलावर को समान रूप से और स्वतंत्र रूप से हैश करने की आवश्यकता होती है $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ लगभग पूर्ण गारंटी (99% संभावना) के लिए कि दो तत्व एक ही मूल्य पर हैशेड हैं।

मान लीजिए कि हम 50% की संभावना के साथ टकराव प्राप्त करना चाहते हैं; तो हमें जरूरत है $$$n = \ sqrt {2 m \ ln 2}$ । यहां महत्वपूर्ण निष्कर्ष यह है कि 0.5 से अधिक की संभावना के साथ टकराव प्राप्त करने के लिए, हमें आदेश को हैश करना होगा $$$\ sqrt {m}$ तत्वों। यह हमारे पिछले विश्लेषण के अनुरूप है $$$m = 365$ क्योंकि $$$\ sqrt {2 \ ln 2 \ cdot 365}$ लगभग 23 के बराबर।

अतिरिक्त कार्य

1. होने $$$एन$ लोगों की $$$एम$ दिन और एक निश्चित संख्या $$$k$ संभावना है कि वास्तव में मिल $$$k$ लोगों का एक ही जन्मदिन है।
2. उपरोक्त कार्य को थोड़ा बदल दें। मान लीजिए कि हमारे पास है $$$एम$ दिन और एक निश्चित संख्या $$$k$ । सबसे छोटा मूल्य क्या होगा $$$एन$ जिस पर कोई कम नहीं $$$k$ लोगों के पास कम से कम 0.5 की संभावना के साथ एक ही जन्मदिन होगा? क्या आप इस कार्य को किसी भी संभावना के लिए सामान्य कर सकते हैं $$$p> 0$ ?
3. मान लें कि हमारे पास 1 से 100 तक 100 नंबर हैं, साथ ही एक समान और यादृच्छिक क्रम में 1 से 100 तक यादृच्छिक संख्या का अनुमान लगाने वाली मशीन है। मशीन को अपेक्षित रूप से कितनी बार उपयोग करने की आवश्यकता होगी, ताकि मशीन 1 से 100 तक की सभी संख्याओं का अनुमान लगा ले?
4. क्या आप इस कार्य को किसी भी तरह से सामान्य कर सकते हैं $$$एन$ ?
5. मान लीजिए कि हमारे पास एक हैश फ़ंक्शन है जो एक स्मृति क्षेत्र में अनियमित रूप से समान रूप से तत्वों को प्रदर्शित करता है। कुल क्षेत्रों दें $$$एम$ । कितने आइटम हैं $$$एन$ क्या हमें अपनी डेटा संरचना में गणितीय अपेक्षा जोड़ने की ज़रूरत है ताकि प्रत्येक क्षेत्र में कम से कम दो तत्वों को हैशेड किया जा सके?