麦克斯韦妖的熵减操作

KeyTo9_Fans

n个红球和n个蓝球的一个全排列，红蓝左右分离的状态被认为是熵最小的（零熵）。

所谓红蓝左右分离，即恰好n个红球位于左侧，n个蓝球位于右侧。

麦克斯韦妖总是力图将一个高熵排列操作成一个低熵排列，直至零熵，方为成功。

但这个麦克斯韦妖并不能直接捡球换位，它的操作只是区隔洗球。

即用若干个挡板把这排球分隔为或长或短的若干个区段，然后洗一次球。

洗球只在每个区段内，段间不会窜球。

每次洗球之前都可以随意增减、抽插档板，重作区隔。

麦克斯韦妖希望降至零熵所需的洗球次数的期望值尽可能小。

给定n，问麦克斯韦妖成功所需的洗球次数的期望值是多少？

#####

当n=1时，有1/2的概率就是零熵，有1/4的概率需要洗1次，有1/8的概率需要洗2次，有1/16的概率需要洗3次，……，依次类推。

所以当n=1时，洗球次数的期望值是1/2*0+1/4*1+1/8*2+1/16*3+……=1

当n=2时，只有1/6的概率就是零熵，有5/6的概率需要洗球，该怎么洗呢？

对于更大的n，情况就更复杂了，不知道有没有好方法求解期望洗球次数？

mathe

每个隔板必须左红又绿

mathe

如果把所有红球坐标之和看成一个局面的代价，我们每次计算如何插板使得一次变化后代价的期望最小，应该可以给出一种不错的方案

mathe

n=2是31/24

但KeyTo9_Fans的答案是9/4

1/6的0步，1/6的2步，1/3的2.5步
余下1/3mathe算的都是3.25步，区别是否在这里

mathe

隔板不是越多越好

mathe

我们可以先从残局入手，最简单情况是n-1个都已经归位，只留下1个游离在外的情况。那么这个游离者离其它红球还间隔k个篮球时，那么可以归纳算出平均还需要1+1/1+1/2+1/3+...+1/k步。
下一步可以考虑还有两个游离红球的情况，这时距离远的红球的距离决定了计算复杂度，我们需要根据此复杂度顺序计算。而另外一个距离更近的红球应该在距离充分近时需要挡板，而距离太远时不需要挡板。这时就需要通过穷举临界值的位置找到解。
但是三个以上游离红球的计算就复杂了

mathe

三个以上游离红球情况应该可以通过迭代的方法求解，不过计算量很难估计，但是不会小

mathe

两个游离红球的策略:
Level 3 Index 0 to 0 use extra baffle
Level 4 Index 0 to 0 use extra baffle
Level 5 Index 0 to 1 use extra baffle
Level 6 Index 0 to 1 use extra baffle
Level 7 Index 0 to 2 use extra baffle
Level 8 Index 0 to 2 use extra baffle
Level 9 Index 0 to 2 use extra baffle
Level 10 Index 0 to 3 use extra baffle
Level 11 Index 0 to 3 use extra baffle
Level 12 Index 0 to 4 use extra baffle
Level 13 Index 0 to 4 use extra baffle
Level 14 Index 0 to 5 use extra baffle
Level 15 Index 0 to 5 use extra baffle
Level 16 Index 0 to 5 use extra baffle
Level 17 Index 0 to 6 use extra baffle
Level 18 Index 0 to 6 use extra baffle
Level 19 Index 0 to 7 use extra baffle
Level 20 Index 0 to 7 use extra baffle
Level 21 Index 0 to 8 use extra baffle
Level 22 Index 0 to 8 use extra baffle
Level 23 Index 0 to 8 use extra baffle
Level 24 Index 0 to 9 use extra baffle
Level 25 Index 0 to 9 use extra baffle
Level 26 Index 0 to 10 use extra baffle
Level 27 Index 0 to 10 use extra baffle
Level 28 Index 0 to 11 use extra baffle
Level 29 Index 0 to 11 use extra baffle
Level 30 Index 0 to 12 use extra baffle
Level 31 Index 0 to 12 use extra baffle
Level 32 Index 0 to 12 use extra baffle
Level 33 Index 0 to 13 use extra baffle
Level 34 Index 0 to 13 use extra baffle
Level 35 Index 0 to 14 use extra baffle
Level 36 Index 0 to 14 use extra baffle
Level 37 Index 0 to 15 use extra baffle
Level 38 Index 0 to 15 use extra baffle
Level 39 Index 0 to 16 use extra baffle
Level 40 Index 0 to 16 use extra baffle
Level 41 Index 0 to 16 use extra baffle
Level 42 Index 0 to 17 use extra baffle
Level 43 Index 0 to 17 use extra baffle
Level 44 Index 0 to 18 use extra baffle
Level 45 Index 0 to 18 use extra baffle
Level 46 Index 0 to 19 use extra baffle
Level 47 Index 0 to 19 use extra baffle
Level 48 Index 0 to 20 use extra baffle
Level 49 Index 0 to 20 use extra baffle
Level 50 Index 0 to 20 use extra baffle

mathe

两个游离红球需要移动的平均步数(其中第二个参数为0代表这个球不是游离的，退化为一个游离红球情况）
States[2,0]=2
States[2,1]=5/2
States[3,0]=5/2
States[3,1]=13/4
States[3,2]=13/4
States[4,0]=17/6
States[4,1]=79/21
States[4,2]=79/21
States[4,3]=79/21
States[5,0]=37/12
States[5,1]=391/98
States[5,2]=29219/7056
States[5,3]=29219/7056
States[5,4]=29219/7056
States[6,0]=197/60
States[6,1]=109373/26460
States[6,2]=228409/51408
States[6,3]=228409/51408
States[6,4]=228409/51408
States[6,5]=228409/51408
States[7,0]=69/20
States[7,1]=1237937/291060
States[7,2]=322286353/69272280
States[7,3]=1040561915/221671296
States[7,4]=1040561915/221671296
States[7,5]=1040561915/221671296
States[7,6]=1040561915/221671296
States[8,0]=503/140
States[8,1]=5494367/1261260
States[8,2]=2203210487/463914360
States[8,3]=9316240966457/1898337561120
States[8,4]=9316240966457/1898337561120
States[8,5]=9316240966457/1898337561120
States[8,6]=9316240966457/1898337561120
States[8,7]=9316240966457/1898337561120

zeroieme

设计一个容许红蓝球数量不相等的状况下，洗球次数期望值函数F(x,y)。其中红球x个，蓝球y个。
显然，区间内只有单球色时。有F(x,0)=0、F(0,y)=0。
x个红球与y个蓝球进行一次洗球，如果洗球后最左侧连续有i个红球;最右侧连续有j个蓝球，可用挡版隔离它们。下次洗球只考虑F(x-i,y-j)。

1红1蓝情形。存在1/2机会已经排好。按前面设计用挡版隔离后中央区域为0红0蓝；1/2机会没排好。先进行一次洗球，看结果继续。所以有  F(1,1)=1/2  F(0,0)+1/2(1+ F(1,1))。 F(0,0)=0，解方程得 F(1,1)=1。
2红1蓝，1/3完全排好，1/3排好1红，1/3完全没排好。 F(2,1)=1/3 F(0,0)+1/3 (1+F(1,1))+1/3(1+ F(2,1))，解方程得 F(2,1)=3/2。
.....
\(F(n,1)=\sum _{i=1}^n \frac{F(i,1)+1}{n+1}+\frac{F(0,1)}{n+1}=\frac{\sum _{i=0}^{n-1} F(i,1)}{n}+1=F(n-1,1)+\frac{1}{n}=H_n\)
调和级数
.....
x个红球与y个蓝球进行一次洗球，如果洗球后最左侧连续有i个红球,第i+1个为蓝球 ;最右侧连续有j个蓝球,第j+1个为红球 。这个几率怎么算？
x个红球与y个蓝球分配位置有\(C_{x+y}^x\)种方式，最左与最右确定了i+1红球与j+1个蓝球，中央可变区域分配有\(C_{x+y-i-j-2}^{x-i-1}\)种方式
\(F(x,y)=\frac{(x y) (F(x,y)+1)}{(x+y-1) (x+y)}+\frac{(x y) F(x-1,y-1)}{(x+y-1) (x+y)}+\frac{((x-1) x) F(x-1,y)}{(x+y-1) (x+y)}+\frac{((y-1) y) F(x,y-1)}{(x+y-1) (x+y)}=\frac{x y F(x-1,y-1)}{x^2+x (y-1)+(y-1) y}+\frac{(y-1) y F(x,y-1)}{x^2+x (y-1)+(y-1) y}+\frac{(x-1) x F(x-1,y)}{x^2+x (y-1)+(y-1) y}+\frac{x y}{x^2+x (y-1)+(y-1) y}\)
讨论最两端球的颜色，
右蓝球左红球：没有简化。
双红球：可隔离左红球，问题退化为F(x-1,y)
双蓝球：可隔离右蓝球，问题退化为F(x,y-1)
左红球右蓝球：可同时隔离两端，问题退化为F(x-1,y-1)。
.....