読者です 読者をやめる 読者になる 読者になる

shaitan's blog

長文書きたいときに使う.

本文と無関係なブログタイトルって見るたびに謎だったんだけど腑に落ちた。


席替えはいったん全員が席から立ち、一人ずつランダムに空いている席に座るとしてよい。
k番目に座る人をp(k)、その人が最初に座っていた席をs(k)、その席が空いていないことをa(k)と書く。
p(i) (i≦m)が最初と異なる席に座っている、という条件付のa(k)の確率をQ(i;j,n)と書く。
ここで、対称性よりQ(i;j,n)のj依存性はjがiより大きいかi以下かの二通りしかない。
Q(i;i,n)とQ(i;i+1,n)の大小関係を考える。
p(i)が座る前の状態ではa(i)とa(i+1)の確率は等しい。p(i)はs(i)には座らないがs(i+1)には座る可能性があるため、p(i)が座った後はa(i)の確率よりa(i+1)の確率のほうが大きい。
すなわちQ(i;i,n)<Q(i;i+1,n)。
ここで、p(i)が座った後に空いていない席はi個であるから、i=iQ(i;i,n)+(n-i)Q(i;i+1,n)。
従ってQ(i;i+1,n)>i/n。
よって、p(i) (i≦k)が全員異なる席に移っている状態で、p(k+1)がランダムに座ったときにs(k+1)に座らない確率q(k)は
{q(k)=Q(k;k+1,n)+(1-Q(k;k+1,n))\dfrac{n-k-1}{n-k}=\dfrac{Q(k;k+1,n)-1}{n-k}+1>1-\dfrac1n}
これより、{\displaystyle P(n)=\prod_{k=1}^nq(k)>\left(1-\dfrac1n\right)^n\to\dfrac1e\quad(n\to\infty)}
さて、Q(i+1;1,n+1) (i<n)は、p(1)が座った後、この人および座った席を無視すればQ(i;i+1,n)と等しい。
ここで、{Q(i;i+1,n)=Q(i+1;1,n+1)<\dfrac{i+1}{n+1}}であることに気をつけると、
{q(k)=\dfrac{Q(k;k+1,n)-1}{n-k}+1<1-\dfrac1{n+1}}
従って、{\displaystyle P(n)=\prod_{k=1}^nq(k)<\left(1-\dfrac1{n+1}\right)^n\to\dfrac1e\quad(n\to\infty)}
はさみうちの原理により{\displaystyle\lim_{n\to\infty}P(n)=\frac1e}