n個1~n的隨機數，出現重複數字個數的期望是多少？

01-15

感覺很有趣。1L提到用程序模擬，很不錯的。模擬的話，可以模擬一下N=100么

@王某魚的答案很不錯, 不過我認為有點複雜化了問題.

這個問題從概率觀點來看並不困難的喵~

令該離散分布為 $RepeatNum(n)$ ,

隨機變數 $Nsim RepeatNum(n)$ 表示 $n$ 個隨機數 $x_iin[1,n]cap mathbb{Z};(0leq ileq n)$ 中, 出現重複數字個數. 其中 $x_istackrel{ ext{i.i.d}}{sim} Unif(1,n)$ .

求其期望 $mathbb{E}[N]$

設indicator:

$I_{x_i}=left{egin{array}{ll} 1quad(number x_i has appeared in the sequence (x_1,..,x_{i-1}))\ 0quad(otherwise) end{array} ight.$

有

$mathbb{P}(I_{x_i}=0)={left( frac{n-1}{n} ight) }^{i-1}$

$mathbb{P}(I_{x_i}=1)=1-mathbb{P}(I_{x_i}=0)=1-{left( frac{n-1}{n} ight) }^{i-1}$

$mathbb{E}[I_{x_i}]=mathbb{P}(I_{x_i}=1)$

那麼有:

$N=sum_{i=1}^{n}{I_{x_i}}$

$egin{split} mathbb{E}[N]=mathbb{E}[sum_{i=1}^{n}{I_{x_i}}]=sum_{i=1}^{n}{mathbb{E}[I_{x_i}]}\ = sum_{i=1}^{n}{mathbb{P}(I_{x_i}=1)}\ =sum_{i=1}^{n}{1-{left( frac{n-1}{n} ight) }^{i-1}}\ =n- frac{1left( 1-{left( frac{n-1}{n} ight) }^n ight) }{1-left( frac{n-1}{n} ight)} \ =n{left( 1- frac{1}{n} ight)}^n end{split}$

當 $n=1000$ 時, $mathbb{E}[N]=1000cdot {left( 1- frac{1}{1000} ight)}^{1000}=$ 367.70

若取 $n ightarrow infty$ , 則有 $mathbb{E}[N]sim frac{n}{e}$

推薦 @朱沖喵的答案, 他的答案用到了期望的和的簡單性質, 過程比我的葯簡單得多.

---------------------分隔線--------------

第一次評論丟臉了, 實際上答案是

$n-dfrac{sum_{k=1}^nkcdot inom n kcdot sum_{j=1}^k (-1)^{k-j}inom k jcdot j^n}{n^n}$ .

這個式子的來源是這樣的. 首先注意到不同的數字的個數 $xi$ 和重複的數字數 $eta$ 滿足 $xi+eta=n$ , 因此為了求 $mathrm{E}eta$ , 我們只需要用 $n$ 減去 $mathrm{E}xi$ 即可.

根據容斥原理, 恰有 $k$ 個不同數字的排列一共有 $inom n kleft(k^n-inom k{k-1} cdot(k-1)^n+inom k {k-2}cdot (k-2)^n-cdots+inom k 1(-1)^{k-1}cdot 1^n ight)$ , 即 $inom n ksum_{j=1}^kinom k j (-1)^{k-j} cdot j^n$ 種.

所以 $mathrm{E}xi=sum_{k=1}^n kcdot dfrac{inom n k cdot sum_{j=1}^k (-1)^{k-j} inom k j cdot j^n}{n^n}$ .

事實上, $sum_{k=1}^nsum_{j=1}^k(-1)^{k-j}kcdot inom n kinom k jcdot j^n=sum_{j=1}^nsum_{k=j}^n(-1)^{k-j}kcdot inom n jinom {n-j}{k-j}cdot j^n$

它等於 $sum_{j=1}^ninom n jcdot j^nsum_{l=0}^{n-j}(-1)^l(l+j)cdot inom {n-j}l=sum_{j=1}^ninom n jcdot j^nleft(sum_{l=0}^{n-j}(-1)^lcdot lcdot inom {n-j}l+sum_{l=0}^{n-j}(-1)^lcdot jcdot inom {n-j}l ight)$ .

熟知 $jcdotsum_{l=0}^{n-j}(-1)^linom {n-j}l=jcdot delta_{j,n}$ , 而 $sum_{l=0}^{n-j}(-1)^lcdot lcdot inom {n-j}l=(n-j)cdotsum_{l=1}^{n-j}(-1)^lcdot inom {n-j-1}{l-1}=-(n-j)delta_{j,n-1}$ .

因此 $n^nmathrm{E}xi=sum_{j=1}^ninom n jcdot j^n(jcdot delta_{j,n}-(n-j)cdotdelta_{j,n-1})=n^{n+1}-ncdot (n-1)^n$ .

於是 $mathrm{E}xi=n-dfrac{(n-1)^n}{n^{n-1}}$ , 進而 $mathrm{E}eta=dfrac{(n-1)^n}{n^{n-1}}$ .

所以這個答案是 $dfrac{(n-1)^n}{n^{n-1}}$ , 約為 $dfrac{n}{mathrm{e}}$ .

好像是不錯的中學競賽題?

這個題目描述其實是有歧義的。「重複數字個數」的解釋有多種。比如5個隨機數 1 1 2 2 2，重複數字個數是多少呢？

A. 重複數字個數是3，這似乎是題主想要的解釋。每個數字第一次出現的時候不算「重複」，之後每次出現都「重複」，所以1重複了1次，2重複了2次，總共重複次數是1+2=3。

B. 重複數字個數是2，因為重複出現的數字有2個，1和2。

C. 重複數字個數是5，因為1和2都是重複出現的數字，而且分別出現了2次和3次，所以總次數是2+3=5。

按照期望的可加性（其實 @陳俊欽所說的全同性就利用到了期望的可加性），可以算出來：

解釋A: f(n) = n[ (n-1)^n / n^n ] = (n-1)^n / n^(n-1)

解釋B: g(n) = n [ 1 - (2n-1)*(n-1)^(n-1) / n^n ]

解釋C: h(n) = n [ 1 - (n-1)^(n-1) / n^(n-1) ]

對於每個數i，它在n^n種排列中一共出現了n^n次，但一共只有n^n-(n-1)^n個排列包含i，所以i一共重複了(n-1)^n次

所以所有重複數字次數的期望是n*(n-1)^n/n^n=(n-1)^n/n^(n-1)

這算是給@Tim答案的補充吧，他已經給了這個式子了。

翻譯一下，原題可以認為是求空槽數的期待值。

每個槽空的概率是（1-1/n）^n 約是 1/e。

所以總的空槽數就是n/e。

空槽數就是重複數。

先看強行算的結果。我寫了個fortran小程序，計算了一下，結果很有意思，n=1000，期望是367.8808。重複操作次數10000次。

注意到， $frac{Ex}{n}$ 是一個固定的數字，我不知道為什麼。

這是每一次的重複個數的圖，波動還是蠻小的。

首先其實1-n這n個數字哪個重複都是一樣的（全同性），所以只要算出1的重複個數期望，再×n就是整體的期望。

對於1的重複個數，我採用蠻力計算的辦法，若1出現i次個，概率是 $left( i-1 ight) imes C_{n}^{i} imes left( frac{1}{n} ight) ^{i} imes left( frac{n-1}{n} ight) ^{n-i}$

然後i從1到n求和。

我又寫了fortran程序驗證，跟前面暴力隨機的結果是一樣的。

源碼如下。

1 program ne 2 implicit none 3 real*8 rand 4 integer i,j,n,ier,l,rep,cntt 5 integer,allocatable:: k(:),cnt(:) 6 open(100,file="number.dat") 7 read(*,*)n,rep 8 allocate (k(n),stat=ier) 9 allocate (cnt(rep),stat=ier) 10 if (ier/=0) then 11 write(*, *) "failed in memory allocation at main, PROGRAM STOP" 12 endif 13 cnt=0!計數的cnt初始化 14 do l=1,rep 15 !--------------------------- 16 !第l次執行產生n次隨機數，並計數 17 k=-1!k初始化，以-1開始這樣表示比較方便 18 do i=1,n 19 call random_number(rand) 20 j=int(rand*n)+1 21 k(j)=k(j)+1!表示j重複出現的次數 22 enddo 23 !第l次n個隨機數產生並完畢 24 !--------------------- 25 do i=1,n 26 if(k(i)&>0)cnt(l)=cnt(l)+k(i) 27 enddo 28 !計數重複的數目 29 enddo 30 cntt=0 31 do l=1,rep 32 cntt=cnt(l)+cntt 33 write(100,*)l,cnt(l) 34 enddo 35 write(*,*)real(cntt)/real(rep) 36 37 38 close(100) 39 endprogram

1 program nnnnn 2 implicit none 3 real*8 n,i,j,k 4 real*8 total,res 5 common res 6 read(*,*)n 7 total=0 8 do i=2,n!i代表數字出現次數 9 call cal(n,i) 10 total=(i-1)*res*(1/n)**i*((n-1)/n)**(n-i)+total 11 enddo 12 write(*,*)total*n 13 endprogram 14 15 subroutine cal(n,m) 16 real*8 n,m,i 17 real*8 res 18 common res 19 res=0 20 if(m&>n/2.and.m&0)then 22 res=1 23 do i=0,m-1 24 res=res*(n-i)/(i+1) 25 enddo 26 endif 27 if(m==n)res=1 28 endsubroutine

一共n^n種結果，均勻分布，有A(n, n)種不滿足的組合。所以不重複的概率是1 - A(n, n) / n^n

@朱沖喵是正解，R代碼的模擬在unique函數的幫助文件里就有

n = 1000000 length(unique(sample(n, n, replace = TRUE)))/n

另外還可以參考這裡 Bootstrap aggregating

我來提供一個用dp推的計算方法

python代碼如下,經驗證和王某魚的答案一致

n = 100 dp = [] for i in range(n + 1): dp.append([0] * (n + 1)) dp[0][0] = 1 for i in range(n): for j in range(i + 1): dp[i + 1][j] += 1.0 * dp[i][j] * j / n dp[i + 1][j + 1] += 1.0 * dp[i][j] * (n - j) / n res = 0 for j in range(n + 1): res += dp[n][j] * (n - j) print res print 1.0 * ((n - 1) ** n) / (n ** (n - 1))

n = 100的時候

結果為36.6032341273