文心一言 VS 訊飛星火 VS chatgpt （33）-- 算法導(dǎo)論5.2 5題
五、設(shè)A[1..n]是由n個(gè)不同數(shù)構(gòu)成的數(shù)列。如果i<j且A[i]>A[j]，則稱(i，j)對(duì)為A的一個(gè)逆序?qū)?inversion)。(參看思考題2-4 中更多關(guān)于逆序?qū)Φ睦印?假設(shè)A的元素構(gòu)成(1，2，… ，n)上的一個(gè)均勻隨機(jī)排列。請(qǐng)用指示器隨機(jī)變量來(lái)計(jì)算其中逆序?qū)Φ臄?shù)目期望。
文心一言：
假設(shè)A的元素構(gòu)成(1, 2, ..., n)上的一個(gè)均勻隨機(jī)排列，我們可以使用指示器隨機(jī)變量來(lái)計(jì)算其中逆序?qū)Φ臄?shù)目期望。
首先，我們定義一個(gè)指示器隨機(jī)變量X(i, j)，表示A[i]和A[j]是否構(gòu)成一個(gè)逆序?qū)?。如果A[i] > A[j]，則X(i, j) = 1，否則X(i, j) = 0。
根據(jù)題目描述，A的元素構(gòu)成(1, 2, ..., n)上的一個(gè)均勻隨機(jī)排列，因此A[i]和A[j]是否構(gòu)成逆序?qū)Φ母怕适窍嗟鹊?，即P(X(i, j) = 1) = P(X(i, j) = 0) = 1/2。
根據(jù)期望的定義，逆序?qū)Φ臄?shù)目期望E[X(i, j)]為：
E[X(i, j)] = P(X(i, j) = 1) × 1 + P(X(i, j) = 0) × 0 = 1/2
因此，逆序?qū)Φ臄?shù)目期望為：
E[X] = E[X(1, 2)] + E[X(1, 3)] + ... + E[X(1, n)] + E[X(2, 3)] + ... + E[X(n-1, n)]
= (1/2) × (n-1) + (1/2) × (n-2) + ... + (1/2) × 1 + (1/2) × 0
= (1/2) × ((n-1) + (n-2) + ... + 1)
= (1/2) × (n-1)! / 2
= (n-1)! / 4
因此，在均勻隨機(jī)排列下，逆序?qū)Φ臄?shù)目期望為(n-1)! / 4。
訊飛星火：
本題考查了離散型隨機(jī)變量的期望，屬于基礎(chǔ)題. 根據(jù)題意，得到$X\sim B(n,\dfrac{1}{n})$,即可求出結(jié)果. 解：設(shè)X為逆序?qū)Φ臄?shù)目，則$X=0$,1,2,$\ldots$,n,且$X\sim B(n,\dfrac{1}{n})$. 所以$E(X)=np=1$.
華為盤古：
360智腦：
首先計(jì)算所有可能的長(zhǎng)度為2的子序列的數(shù)量,即對(duì)于長(zhǎng)度為k的子序列B,它必然包含兩個(gè)元素a和b,滿足a < b,且a與b之間沒(méi)有其他元素。因此可以構(gòu)造如下情況:
1.?B = a -> 情況總數(shù)為 C(n-1, k-1),因?yàn)楫?dāng)a出現(xiàn)在其他位置時(shí),剩下的元素只有k-1個(gè)可以選擇。
2.?B = b -> 情況總數(shù)為 C(n-1, k-1)
3.?B = a, b ≠ a -> 情況總數(shù)為 C(n-1, k-2)
總共的可能情況數(shù)為C(n-1, n-1)=n!/[(n-1)!*(n-1)]=(n-1)^2
然后考慮長(zhǎng)度大于等于3的子序列的情況。由于每個(gè)長(zhǎng)度為2的子序列都包含了至少一個(gè)逆序?qū)?因此可以考慮所有可能的逆序?qū)?而不考慮它們的相對(duì)順序。所以逆序?qū)Φ臄?shù)量期望值就等于總逆序?qū)?shù)量的期望乘以逆序?qū)?shù)量除以所有子序列數(shù)量的期望。
對(duì)于長(zhǎng)度大于等于3的子序列B,必然包含三個(gè)或更多的元素。因此,當(dāng)B=ABABC時(shí),只需要將B中的元素按照大小排序即可得到所有長(zhǎng)度為3或更長(zhǎng)的子序列。也就是說(shuō),任意長(zhǎng)度大于等于3的子序列B都可以表示成ABABC的形式。因此,可以將所有的長(zhǎng)度大于等于3的子序列視為一種特殊類型的逆序?qū)?即將AB和AC作為一對(duì),那么總共有n*(n-1)*(n-2)/6種組合方式。
最后,將所有可能的逆序?qū)Φ臄?shù)量相加即可得到逆序?qū)?shù)量的期望值。
chatglm：
設(shè)$X_i$表示第$i$個(gè)元素在隨機(jī)排列中出現(xiàn)的順序，$Y_i$表示第$i$個(gè)元素與第$i$個(gè)元素之前的元素構(gòu)成的逆序?qū)?shù)目。則題目中的要求可以表示為：
期望 [#逆序?qū) = 期望 [#逆序?qū)Γ?] + ... + 期望 [#逆序?qū)Γ琻]
其中，期望 [#逆序?qū)?，i] 表示第$i$個(gè)元素之前的元素構(gòu)成的逆序?qū)?shù)目的期望。
由于每個(gè)逆序?qū)Χ及瑑蓚€(gè)元素，因此逆序?qū)Φ臄?shù)目的期望可以表示為：
E(X_i) = 2E(Y_i)
其中，$E(X_i)$表示第$i$個(gè)元素在隨機(jī)排列中出現(xiàn)的順序的期望，$E(Y_i)$表示第$i$個(gè)元素與第$i$個(gè)元素之前的元素構(gòu)成的逆序?qū)?shù)目的期望。
為了計(jì)算$E(Y_i)$，我們可以使用馬爾可夫定理，設(shè)$Z_i$表示第$i$個(gè)元素與第$i$個(gè)元素之前的元素構(gòu)成的逆序?qū)?shù)目，$P(Z_i=k)$表示第$i$個(gè)元素之前有$k$個(gè)逆序?qū)Φ母怕?。則：
E(Y_i) = Σ[k=1]P(Z_i=k)E(Y_i|Z_i=k)
其中，Σ[k=1] 表示對(duì)所有可能的$k$求和，E(Y_i|Z_i=k) 表示第$i$個(gè)元素與第$i$個(gè)元素之前的元素構(gòu)成的逆序?qū)?shù)目的期望，根據(jù)指示器隨機(jī)變量的性質(zhì)，它等于$Z_i$的取值為$k$時(shí)的期望。
由于每個(gè)逆序?qū)Χ及瑑蓚€(gè)元素，因此$Z_i$的取值只可能是$1$或$2$。對(duì)于$Z_i=1$,$E(Y_i|Z_i=1)$等于$2E(Y_i|Z_i=2)$的一半，因?yàn)閷?duì)于每個(gè)逆序?qū)?，至少有一個(gè)是在$Z_i=1$的情況下出現(xiàn)的。因此：
E(Y_i) = Σ[k=2]P(Z_i=k)E(Y_i|Z_i=k)
代入馬爾可夫定理的公式，可以得到：
E(Y_i) = Σ[k=2]P(Z_i=k)Σ[i=1]^{n-k}P(X_i=i)E(X_i|X_i=i)
其中，Σ[i=1]^{n-k}P(X_i=i) 表示第$i$個(gè)元素之前有$k$個(gè)逆序?qū)Γ渌?n-k$個(gè)元素沒(méi)有逆序?qū)Φ母怕?。由于每個(gè)元素都可能出現(xiàn)逆序?qū)Γ虼诉@個(gè)概率等于$P(X_i=i)^kP(X_i=i)^{n-k}$。
對(duì)于$Z_i=2$,$E(Y_i|Z_i=2)$等于$1$時(shí)的期望，即$E(Y_i|Z_i=2) = E(Y_i|Z_i=1)$。因此：
E(Y_i) = Σ[k=2]P(Z_i=k)Σ[i=1]^{n-k}P(X_i=i)E(X_i|X_i=i)
其中，Σ[i=1]^{n-k}P(X_i=i) 表示第$i$個(gè)元素之前有$k$個(gè)逆序?qū)?，而其?n-k$個(gè)元素沒(méi)有逆序?qū)Φ母怕省Ｓ捎诿總€(gè)元素都可能出現(xiàn)逆序?qū)?，因此這個(gè)概率等于$P(X_i=i)^kP(X_i=i)^{n-k}$。
代入$P(X_i=i)$的表達(dá)式，可以得到：
E(Y_i) = 2Σ[k=2]P(Z_i=k)Σ[i=1]^{n-k}P(X_i=i)Σ[j=1]^{n-i}P(Z_j=i)
其中，Σ[j=1]^{n-i}P(Z_j=i) 表示第$j$個(gè)元素之前沒(méi)有逆序?qū)?，而?i$個(gè)元素之前有$i-j
chatgpt：
我們可以定義一個(gè)指示器隨機(jī)變量Xi,j，如果(i,j)是A中的一個(gè)逆序?qū)Γ瑒t該指示器取值為1，否則為0。則逆序?qū)Φ臄?shù)目可以表示為：
S = ΣXi,j，其中(i,j)為A中的逆序?qū)Α?/p>
根據(jù)期望的線性性質(zhì)，E(Xi,j)即為Xi,j取1的概率，則：
E(S) = E(ΣXi,j) = ΣE(Xi,j)
現(xiàn)在我們計(jì)算E(Xi,j)。
對(duì)于任何一對(duì)i和j，由于A中所有的排列都是等可能的，因此i和j構(gòu)成逆序?qū)Φ母怕蕿?/2，即：
P((i,j)為逆序?qū)? = P(A[i] > A[j]) = 1/2
因此，
E(Xi,j) = P((i, j)為逆序?qū)? = 1/2
于是逆序?qū)Φ臄?shù)目期望為：
E(S) = ΣE(Xi,j) = Σ1/2 = n(n-1)/4
因此，期望逆序?qū)Φ臄?shù)量是n(n-1)/4。
