這里稱(chēng)作進(jìn)階數(shù)學(xué)問(wèn)題，其實(shí)著實(shí)是因?yàn)閷⒕€性方程組和期望的問(wèn)題混合到一起總結(jié)，有些不太好起名字，所以采用了進(jìn)階數(shù)學(xué)問(wèn)題。說(shuō)是進(jìn)階，我覺(jué)得期望可能用的稍微多一點(diǎn)，還算是進(jìn)階，線性方程組直接用的應(yīng)該挺少的，不過(guò)這里會(huì)給出一道利用線性方程組計(jì)算解的問(wèn)題，個(gè)人感覺(jué)還是挺厲害的一道題。
一、線性方程組
關(guān)于線性方程組的解法，線性代數(shù)里面應(yīng)該學(xué)了挺多了，有常見(jiàn)的高斯消元法，還有一些更快的算法，這里就不再多說(shuō)了，如果有興趣的話(huà)可以詳細(xì)地去查一查。下面給出一般情況下都?jí)蛴玫母咚瓜ǎ?/p>

const double EPS = 1E-8;
typedef vector<double> vec;
typedef vector<vec> mat;

// A是系數(shù)矩陣，b是結(jié)果向量
vec gauss_jordan(const mat& A,const vec& b){
    int n = A.size();
    mat B(n,vec(n+1));     //用矩陣B來(lái)存儲(chǔ)系數(shù)矩陣和結(jié)果向量，方便之后統(tǒng)一消元
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            B[i][j] = A[i][j];
        }
    }
    for(int i = 0;i < n;i++)B[i][n] = b[i];
    for(int i = 0;i < n;i++){
        /*這里pivot是想找到當(dāng)前要消掉的這一列中，系數(shù)絕對(duì)值最大的那個(gè)，
        一方面保證當(dāng)前的主元(就是用來(lái)消的系數(shù))不為0，另一方面有人證明這
        樣可以更穩(wěn)定。*/
        int pivot = i;
        for(int j = i;j < n;j++){
            if(abs(B[j][i]) > abs(B[pivot][i]))pivot = j;
        }
        swap(B[i],B[pivot])  //如果不放心swap函數(shù)，可以自己寫(xiě)一個(gè)，不復(fù)雜
        
        //<EPS相當(dāng)于系數(shù)是0了，經(jīng)過(guò)上面的pivot，主元找最大的都是0，那么要不
        //就是無(wú)解，要么就是無(wú)窮個(gè)解了
        if(abs(B[i][i]) < EPS)return vec();
        for(int j = i+1;j <= n;j++)B[i][j] /= B[i][i];
        for(int j = 0;j < n;j++){
            if(i != j){
                for(int k = i+1;k <= n;k++)B[j][k] -= B[j][i] * B[i][k];
            }
        }
    }
    vec x(n);
    for(int i = 0;i < n;i++)x[i] = B[i][n];
    return x;
}

一道例題，算是線性方程組向期望過(guò)渡的題：
有一個(gè)N*M大小的格子，從(0,0)出發(fā)，每一步朝著上下左右4個(gè)各自中可以移動(dòng)的格子等概率移動(dòng)。另外有一些格子中有石頭，因此無(wú)法移至這些格子。求第一次到達(dá)(N-1,M-1)格子的期望步數(shù)。題目假定至少存在一條從(0,0)出發(fā)到(N-1,M-1)的路徑。

書(shū)中給出的期望公式：
這里的公式其實(shí)來(lái)的很奇怪，這里的(x,y)與(x-1,y)等周?chē)膫€(gè)格子并沒(méi)有明顯的等式關(guān)系，甚至這里是兩個(gè)變量的期望，為什么可以這樣求？一種想法可能是，E(x,y)用p1(x1,y1)+p2(x2,y2)...這種，概率乘取值這種方法來(lái)求，但是這里顯然不是，因?yàn)镋(x-1,y)必然不是取值，它也是一個(gè)期望。上面也說(shuō)了，它們之間也沒(méi)有明顯的加和關(guān)系，所以也不能直接拆開(kāi)。綜上，這個(gè)公式究竟是哪兒來(lái)的？
我翻了很多博客，沒(méi)有人對(duì)這里有過(guò)講解，仿佛二維圖表中這樣算期望已經(jīng)被默認(rèn)了。我后來(lái)也想了很多，只能有一個(gè)不敢保證對(duì)的方法，幫助自己和大家理解，說(shuō)明這種方法確實(shí)是一個(gè)可以推廣的方法。
對(duì)于這里，上下左右是等可能的，所以各是，就算到不了，它也占著的概率。接下來(lái)，設(shè)X₁₁，X₁₂...都是代表可以到達(dá)X₁的路徑，X₁代表實(shí)際的(x-1,y)，然后 X₂等也有相應(yīng)的含義。那么，E(X)= [p₁₁ * (X₁₁+1) + p₁₂ * (X₁₂+1)+...+p_1n * (X₁+1)+p₂₁ * (X₂₁+1)+...+p_2n * (X_2n+1)+...p₃₁ * (X₃₁+1)+...+p_4n * (X_4n+1)。

上面的公式確實(shí)挺亂。。所以我也不打算再敲公式了，不如這里口糊。。首先，這里肯定可以整體提個(gè)出來(lái)，于情，它們最后都要從各自的位置，轉(zhuǎn)移到(x,y)，這一步轉(zhuǎn)移的概率為；于理，任何數(shù)都可以提個(gè)出來(lái)啊。。因?yàn)樘醾€(gè)就相當(dāng)于乘了個(gè)4。接下來(lái)，提完以后的部分，先把+1都拿出來(lái)，可以湊出4(p₁₁+...+p_1n)這種式子，把4補(bǔ)進(jìn)去，其實(shí)就是從起點(diǎn)出發(fā)，通過(guò)各條路徑到達(dá)(x-1,y)的概率和，而概率和這個(gè)東西一定是等于1的，不管怎么計(jì)算，概率之和為1這一條鐵定不會(huì)變，所以這一塊湊起來(lái)是1；然后剩下的部分，其實(shí)很明顯就是到達(dá)(x-1,y)的期望了，（概率*取值的形式）所以就變成了公式的樣子。

上面的口糊也比較嚴(yán)重，不過(guò)我相信是可以理解的，并且最終是可以得到在格子上運(yùn)動(dòng)時(shí)，期望的公式的。所以這時(shí)我們把這個(gè)公式當(dāng)作已知條件，接著往下探索。此時(shí)沒(méi)有任何一個(gè)點(diǎn)的期望是已知的，所以直接求期望也不太現(xiàn)實(shí)，在這里，如果將每個(gè)E(x,y)都當(dāng)成一個(gè)變量，也就是有N * M個(gè)變量的話(huà)，其實(shí)每一個(gè)變量都能列出一個(gè)方程。

對(duì)于是石頭的格子，E(x,y) = 0。可以到達(dá)終點(diǎn)的格子，可以列出E(x,y) = E(x-1,y) + E(x+1,y) + E(x,y-1) + E(x,y+1) + 1的等式。如果想要優(yōu)化的話(huà)，其實(shí)還可以提前把無(wú)法到達(dá)終點(diǎn)的格子找出來(lái)，然后它們的E(x,y)其實(shí)也是0，保險(xiǎn)起見(jiàn)最好提前求一下。列出線性方程組之后，交給前面的gauss_jordan來(lái)處理就好了，返回值就是每個(gè)點(diǎn)的期望。完結(jié)撒花，接下來(lái)上代碼：

char grid[max_n][max_m+1];    //+1是為了存字符串末尾的'\0'
int n,m;

bool can_goal[max_n][max_m];      //記錄每個(gè)點(diǎn)是否可以到達(dá)終點(diǎn)
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};

// 搜索可以到達(dá)終點(diǎn)的點(diǎn)，記錄
void dfs(int x,int y){
    can_goal[x][y] = true; //這里敢直接標(biāo)成true,其實(shí)是因?yàn)樗阉魇菑慕K點(diǎn)開(kāi)始的逆向搜索
    for(int i = 0;i < 4;i++){
        int nx = x+dx[i],ny = y+dy[i];
        if(0 <= nx && nx < N && 0 <= ny && ny < M && !can_goal[nx][nyh] && grid[nx][ny] != '#'){
            dfs(nx,ny);
        }
    }
}

void solve(){
    mat A(N*M, vec(N*M, 0));     //mat是gauss_jordan定義的類(lèi)型
    vec b(N*M, 0);
    for(int x = 0;x < N;x++){
        for(int y = 0;y < M;y++){
            can_goal[x][y] = false;      //初始化數(shù)組
        }
    }
    dfs(N-1,M-1);
    
    /* A是一個(gè)(N*M,N*M)的矩陣，也就是系數(shù)矩陣。第x*M+y行的方程代表的是(x,y)
    位置建立的方程。如果E(x,y) = 0，那么該行第x*M+y個(gè)變量t,t=0即可。如果E(x,y)
    不是0，就用期望的那個(gè)等式，將該行相鄰位置的變量系數(shù)都設(shè)置一下，并且更新B向量.*/
    for(int x = 0;x < N;x++){
        for(int y = 0;y < M;y++){
            if((x == N-1 && y == M-1) || !can_goal[x][y]){
                A[x*M+y][x*M+y] = 0;
                continue;
            }
            int move_grid = 0;
            for(int k = 0;k < 4;k++){
                int nx = x+dx[k],ny = y+dy[k];
                if(0 <= nx && nx < N && 0 <= ny && ny < M && !can_goal[nx][nyh] && grid[nx][ny] == '.'){
                    A[x*M+y][nx*M+ny] = -1; //4E(x,y) - E(x-1,y) - E(x+1,y) - E(x,y-1) - E(x,y+1) = 4
                    move_grid++;
                }
            }
            b[x*M+y] = A[x*M+y][x*M+Y] = move_grid;
        }
    }
    vec res = gauss_jordan(A,b);
    printf("%.8f\n",res[0]);
}

這道題最難的，其實(shí)我個(gè)人覺(jué)得就是推導(dǎo)二維格子上的期望公式。如果有了這個(gè)，想到了列線性方程組求解，那么這個(gè)題就可以做了。

二、期望總結(jié)
在一些考數(shù)學(xué)的算法題目中，還比較喜歡考一些期望問(wèn)題。這里我將期望問(wèn)題，按照自己的想法分為三類(lèi)。第一類(lèi)是很偏數(shù)學(xué)的考點(diǎn)，就是考察對(duì)于期望的理解，以及期望公式的運(yùn)用，比如E(x) = p₁ * x₁ + p₂ * x₂ + ... + p_n * x_n，這是期望最基本的定義；再比如說(shuō)E(x+y) = E(x) + E(y)，兩個(gè)隨機(jī)變量獨(dú)立時(shí)，E(xy) = E(x) * E(y)。第二類(lèi)就是上面那道題目的類(lèi)型，在二維格子中的期望公式，這個(gè)真的是需要有見(jiàn)過(guò)這類(lèi)型的題目，知道這里的期望公式到底是怎么用的，才能做出來(lái)，一般情況下，都是列出線性方程組來(lái)求解的。第三類(lèi)，是這里想要重點(diǎn)說(shuō)一下的類(lèi)型，是算法導(dǎo)論上的指示器隨機(jī)變量，用它來(lái)求解很多期望問(wèn)題，真的有種神兵利器的感覺(jué)。

首先先來(lái)一個(gè)問(wèn)題，來(lái)感受一下指示器隨機(jī)變量是什么：
拋n次硬幣，求正面向上的次數(shù)？
ok這道題并不難，甚至可以說(shuō)非常簡(jiǎn)單。求法也比較通俗易懂，用定義的話(huà)，正面向上i次的概率p_i = * Cⁱ_n，所以E(x) = * Cⁱ_n * i，右邊的累加，打開(kāi)看一下的話(huà)，很容易發(fā)現(xiàn)其實(shí)就是 Cⁱ_n-1，也就是2^n-1，與左邊相乘，最后的結(jié)果是。

如果再換一種思路呢？這里其實(shí)很容易想到，每次拋擲硬幣，其實(shí)是個(gè)獨(dú)立重復(fù)的過(guò)程，相互之間并不影響，那么把每一次的期望加起來(lái)，不就是n次的期望了嘛。接下來(lái)，每一個(gè)拋擲就是一個(gè)兩點(diǎn)分布，所以E(x) = p * 1 + (1-p) * 0 = p。所以最終E(X) = n*p = 。

其實(shí)分析到這里，指示器隨機(jī)變量的兩個(gè)核心問(wèn)題已經(jīng)都分析出來(lái)了，1. 將一個(gè)分n次進(jìn)行的隨機(jī)變量，分解為n個(gè)進(jìn)行一次的隨機(jī)變量。2. 每一個(gè)進(jìn)行一次的隨機(jī)變量服從兩點(diǎn)分布，所以E(x) = p。 合起來(lái)，E(X) = n*p。

到此，指示器隨機(jī)變量的核心已經(jīng)說(shuō)完了。不過(guò)還不能完結(jié)撒花，我們需要了解為什么可以這樣用，以及究竟怎么用，才能真正的在需要的時(shí)候用出來(lái)。如果只是用它來(lái)解決拋硬幣的問(wèn)題，這個(gè)方法有點(diǎn)過(guò)于雞肋。。

關(guān)于指示器隨機(jī)變量的第一個(gè)問(wèn)題，為什么E(x) = n * E(x)。這里其實(shí)是需要看X這個(gè)隨機(jī)變量，是否可以拆成n個(gè)子過(guò)程的。如果X本身可以拆成n個(gè)子過(guò)程，那么X = n*x。（這樣表達(dá)不準(zhǔn)確，其實(shí)應(yīng)該是X = x_i。然后代入期望的公式中，E(X) = E(x_i) = E(x_i)。其實(shí)我認(rèn)為這才是指示器隨機(jī)變量真正的核心，后面的兩點(diǎn)分布，并不是每一次都能轉(zhuǎn)化的出來(lái)的，但是一旦有了它，很多問(wèn)題的難度就可以直接降一個(gè)level。

下一步的兩點(diǎn)分布，通常定義為，發(fā)生的話(huà)，取值為1，未發(fā)生，取值為0，這里其實(shí)也沒(méi)有太多要說(shuō)的。好了，接下來(lái)看一些例題，這是比較有意思的地方。（例題參考了人家的博客，如有冒犯，請(qǐng)聯(lián)系我，我會(huì)馬上整改）

例一.
拋擲一枚骰子n次，求骰子和的期望。
因?yàn)檫@n次，其實(shí)可以拆成n個(gè)一次，與拋硬幣一樣，所以E(X) = E(x_i)，每一次投擲骰子，很容易計(jì)算期望是3.5，所以結(jié)果是3.5n。這里就是一個(gè)，E(x_i)不是兩點(diǎn)分布的例子。

例二.
一個(gè)隨機(jī)的n排列，求所有排列中，滿(mǎn)足i = a[i]的元素?cái)?shù)目的期望。

這道題就沒(méi)那么簡(jiǎn)單了，首先第一個(gè)問(wèn)題，能不能把X拆分？這里的拆分方案，可能是Aⁿ_n種排列，計(jì)算每一種排列的期望。但是其實(shí)拿出每一次排列的話(huà)，這個(gè)時(shí)候就不是在算期望了，而是能確切地得出有幾個(gè)i = a[i]了，而且這樣計(jì)算也挺難的，我們研究指示器隨機(jī)變量的做法。

i = a[i]，無(wú)非有n種可能，第一個(gè)位置上的值是1，第二個(gè)位置上的值是2...第n個(gè)位置上的值是n。這樣可以順利地將X拆成n個(gè)小的隨機(jī)變量。根據(jù)公式，求出每個(gè)子隨即變量的期望，就可以累加出X的期望。接下來(lái)的問(wèn)題是，求每個(gè)位置上a[i] = i的期望。很明顯這個(gè)問(wèn)題要比前面的問(wèn)題都難很多，這個(gè)問(wèn)題的n個(gè)位置之間，是有相關(guān)性的，而不像前面的拋硬幣，擲骰子這些，是重復(fù)獨(dú)立實(shí)驗(yàn)。

計(jì)算各個(gè)位置a[i] = i的相關(guān)性，如果開(kāi)始考慮位置之間的相關(guān)性，那這個(gè)題基本就做出來(lái)沒(méi)啥希望了。。這里要用期望的眼光來(lái)分析這件事，我們這里算的，是當(dāng)前位置E(a[i] = i)，并沒(méi)有說(shuō)求E(x|y)這種考慮條件的東西（事實(shí)上這種東西我也沒(méi)見(jiàn)過(guò)），所以我們完全可以單獨(dú)拿出i這個(gè)位置來(lái)分析，a[i] = i時(shí)，有n-1的全排列種情況，一共有n的全排列種情況，所以期望 = 1*(n-1)! / n!，也就是1/n。然后把n個(gè)位置累加起來(lái)，其實(shí)最后的結(jié)果就是1.（這里真的挺繞的）

例三.
有n種禮券，每次發(fā)一張，拿到每張的概率都是一樣的，設(shè)X次可以領(lǐng)到n種不同禮券的話(huà)，求X的期望。

如果按照上面那道題的想法的話(huà)，有一個(gè)直接的猜測(cè)，計(jì)算每一張禮券的期望，然后再合起來(lái)，就是所有禮券的期望（還是相當(dāng)于n張禮券是沒(méi)有任何關(guān)聯(lián)的）。但是這樣行不通！這是這道題最大的特點(diǎn)，它事件的總數(shù)是不確定的。(這里拿一次禮券就算一次事件）第一次拿禮券，肯定是一張沒(méi)拿到過(guò)的禮券；然后第二次拿，拿到之前拿到過(guò)的，這次相當(dāng)于是沒(méi)用的；理論上來(lái)說(shuō)，是存在一直拿不完n張不同的禮券，所以要一直拿的情況的。所以這里說(shuō)，事件的總數(shù)是不確定的。

上面那道題，可以不考慮任何順序的問(wèn)題，分析到i時(shí)，就只考慮i的情況，本質(zhì)上是因?yàn)榭偣仓挥衝!種情況，然后可以直接拿出來(lái)處理；但是這里是不可能直接拿出當(dāng)前的情況與總的情況來(lái)處理的，所以一定不能單獨(dú)分析第i張禮券拿的時(shí)候究竟是什么情況的，這里一定需要考慮之前的影響，來(lái)一步步地計(jì)算到n的。

這里說(shuō)一下正確的思路，要拿到第一張不同的禮券，必然只需要1次；然后拿第二張，E(x₂) = 1 * + 2 * * + 3 * * + m * ^m-1 * 。要求解這個(gè)式子，其實(shí)只要知道一下幾何分布的結(jié)論：1 * (1-p)⁰ * p + 2 * (1-p)¹ * p + ... + m * (1-p)^m-1 * p = 。上面那個(gè)式子其實(shí)就是一個(gè)幾何分布，所以E(x₂) = ，...E(x_n) = ，綜上E(X) = E(x₁) + E(x₂) + ... + E(x_n) = n()，這個(gè)式子，如果是以?xún)?nèi)的話(huà)，可以直接遍歷一遍得到結(jié)果。如果n是10¹⁸這個(gè)數(shù)量級(jí)的話(huà)，那肯定不能遍歷了。這個(gè)問(wèn)題一般是用 = ln(n+1) + r來(lái)實(shí)現(xiàn)。r是歐拉常數(shù)，一般取0.5772156649夠了。

其他還有指示器隨機(jī)變量的例題，比如說(shuō)雇傭問(wèn)題，上樓梯問(wèn)題，坐公交車(chē)問(wèn)題等，花樣很多，這里就不一一說(shuō)明了。個(gè)人認(rèn)為，如果考期望問(wèn)題，逃不過(guò)上面這三類(lèi)；如果考指示器隨機(jī)變量，大體就上面兩類(lèi)，即總方案數(shù)確定和總方案數(shù)不確定兩種。