13.
將寫有自然數
1
2



6的6張紙條隨機排放成一列,先將第一張紙條拿在手中,然後從第二張紙條開始,依序看下去,直到第6張。依序看到第6張的過程中,如果看到紙條上的數目字比手中的大,就放下手中的紙條,把數目字大的那張換到手中,直到看到第6張。試求更換次數的期望值。
[解答]
第13題鋼琴老師的方法真的太漂亮了
每次期望值的題目,總是可以看到非常漂亮、抓住期望值核心的手法。
這裡我也分享我自己的作法,可能也是比較多人用的手法
設
En為總共發1,2,3,...,n張牌時,換牌次數的期望值,
當n號牌(最大號)排在第k張位置時,不論前面的牌,看牌看到第k張,必定要換牌一次,而且之後就不會再換牌了。
所以當n號牌排在第k張位置時,換牌次數為前k-1張牌換牌次數再+1,
故n號牌排在第k張位置時的換牌次數期望值為
Ek−1+1
n號牌排在第k張位置的機率為
1n,
故
Ek=n1
0+n1(E1+1)+n1(E2+1)+n1(E3+1)+

+n1(En−1+1)
E1=0、E2=21(E1+1)=21、E3=31(E1+1)+31(E2+1)=65
E4=1213、E5=6077、E6=360522=2029