अपेक्षित संख्या

Question

मैं जैसे मैं जिस तरह से इस समस्या को overthinking कर रहा हूँ लगता है, लेकिन यहाँ वैसे भी जाता है ...

मैं अपनी आंतरिक सरणी में एम स्लॉट के साथ एक हैश तालिका है। मुझे हैश टेबल में एन तत्वों को सम्मिलित करने की आवश्यकता है। मान लीजिए कि मेरे पास हैश फ़ंक्शन है जो यादृच्छिक रूप से प्रत्येक स्लॉट के लिए समान संभावना के साथ एक स्लॉट में तत्व डालता है, हैश टकराव की कुल संख्या का अनुमानित मूल्य क्या है?

(क्षमा करें कि यह प्रोग्रामिंग प्रश्न से अधिक गणित प्रश्न है)।

संपादित करें: यहां कुछ कोड है जो मुझे पायथन का उपयोग करके अनुकरण करना है। मुझे संख्यात्मक उत्तर मिल रहे हैं, लेकिन इसे एक सूत्र में सामान्यीकृत करने और इसे समझाते हुए परेशानी हो रही है।

import random 
import pdb 

N = 5 
M = 8 

NUM_ITER = 100000 

def get_collisions(table): 
    col = 0 
    for item in table: 
     if item > 1: 
      col += (item-1) 
    return col 

def run(): 
    table = [0 for x in range(M)] 

    for i in range(N): 
     table[int(random.random() * M)] += 1 

    #print table 
    return get_collisions(table) 

# Main 

total = 0 
for i in range(NUM_ITER): 
    total += run() 

print float(total)/NUM_ITER 

Answer 1

आपको यहां जवाब मिलेगा: Quora.com। मीटर बाल्टी और n आवेषण के लिए टकराव की अपेक्षित संख्या

n - m * (1 - ((m-1)/m)^n) है।

Answer 2

SUM(x*(x+1)/2) मीट्रिक के लिए सूत्र here पाया जा सकता है, और उम्मीद मूल्य(n/2m)* (n+2m -1) प्रतीत होता है।

भिन्नता, IANAM के बारे में पता नहीं है।