回答 - lethevert is a programmer

[id:lethevert:20070118:p2]
数学の才能がないので、上手く数式化できないけれど、次のようなところまで考えた。
とりあえず、M=4のケースで考える。つまりQueueが４本になるわけだけれど、これを、Queue１本で $\small{\frac14}$ の確率でput、 $\small{\frac14}$ の確率でgetというように読み替える。
$F_N(i)$ が、N回目の試行が完了したときのQueueの長さがiである確率を表すとする。また、 $G_N(i)$ が、N回目の試行でputが終わった後のQueueの長さがiである確率を表すとする。
すると、次のような漸化式で記述できる。

$G_{N+1}(0)=\frac34F_N(0)$

$G_{N+1}(i)=\frac14F_N(i-1)+\frac34F_N(i)$

$F_{N+1}(0)=\frac{13}{16}F_N(0)+\frac3{16}F_N(1)$

$F_{N+1}(i)=\frac3{16}F_N(i-1)+\frac{10}{16}F_N(i)+\frac3{16}F_N(i+1)$

さらに、 $F_0(0)=1$ かつ $F_0(i)=0 (i>0)$ であることを考えて、N回目の試行でgetが空になる確率は $\frac14G_N(0)$ ということになる。
さて、この関数がどういう概形になるのかを計算してみると、 $F_N(0)$ の値を $N=0\to9$ で計算してみた。

$N$	$F_N(0)$	分母	$F_0(0)$ の係数の分子	$F_0(1)$ の係数の分子	$F_0(2)$ の係数の分子	$F_0(3)$ の係数の分子
0	100%	1	1
1	81%	16	13	3	0	0
2	70%	256	178	69	9	0
3	62%	4096	2521	1251	297	27
4	56%	65536	36526	20964	6804	1161
5	51%	1048576	537730	339630	134415	32265
6	48%	16777216	8009380	5412735	2459835	738774
7	45%	268435456	120360145	85534995	43052877	15188607
8	42%	4294967296	1821286870	1345589016	732699576	292045068
9	40%	68719476736	27713496358	21117849498	12239898012	5370440292

ということで、getが空になる確率はだんだん減少して、Queueに含まれる要素数の期待値はだんだん大きくなるわけだけれど、シンプルな数式にまとめる方法はよく分からない。