数学研发论坛

 找回密码
 欢迎注册
查看: 884|回复: 22

[原创] 麦克斯韦妖的熵减操作

[复制链接]
发表于 2019-6-1 00:20:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
n个红球和n个蓝球排成一行,一开始是随机排列的。

如果恰好n个红球位于左侧,n个蓝球位于右侧,

那么麦克斯韦妖就获胜了。

否则麦克斯韦妖可以在这排球之间放置若干个挡板,然后洗一次球。

没有被挡板隔开的球会被洗乱,被挡板隔开的球不会被洗乱。

严格地讲,假设一共放了m-1块挡板,就会把一排球隔开成m组球,每组球的个数分别为n1、n2、……、nm个。

洗球之后,只是每组球分别被打乱顺序,而组与组之间的球是不会被洗在一起的。

每次洗球之前都可以随意添置或抽走任意多块挡板。

麦克斯韦妖希望获胜所需的洗球次数的期望值尽可能小。

给定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,情况就更复杂了,不知道有没有好方法求解期望洗球次数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-1 13:35:09 来自手机 | 显示全部楼层
每个隔板必须左红又绿
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-1 13:42:22 来自手机 | 显示全部楼层
如果把所有红球坐标之和看成一个局面的代价,我们每次计算如何插板使得一次变化后代价的期望最小,应该可以给出一种不错的方案

点评

……好像没想错,右移10000格的红球,操作两次之后应该变成右移2500格左右的样子,而100个右移100格的红球不可能操作两次之后变成50个右移50次的红球  发表于 2019-6-1 17:28
……等等好像想错了什么,我再看看  发表于 2019-6-1 17:24
这个想法应该不可行——1个红球右移100格,100个红球右移1格,10个红球右移10格,这三个状态的代价一样,但最后那一种比前两个更难恢复  发表于 2019-6-1 17:23
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-1 14:58:57 来自手机 | 显示全部楼层
n=2是31/24

但KeyTo9_Fans的答案是9/4

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

点评

口算算错了:(  发表于 2019-6-1 16:57
1/6 * 0 + 1/6 * 2 + 1/3 * 2.5 + 1/3 * 3.25 = 2.25  发表于 2019-6-1 16:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-1 16:55:48 | 显示全部楼层
yg2.jpg
隔板不是越多越好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-1 21:19:49 来自手机 | 显示全部楼层
我们可以先从残局入手,最简单情况是n-1个都已经归位,只留下1个游离在外的情况。那么这个游离者离其它红球还间隔k个篮球时,那么可以归纳算出平均还需要1+1/1+1/2+1/3+...+1/k步。
下一步可以考虑还有两个游离红球的情况,这时距离远的红球的距离决定了计算复杂度,我们需要根据此复杂度顺序计算。而另外一个距离更近的红球应该在距离充分近时需要挡板,而距离太远时不需要挡板。这时就需要通过穷举临界值的位置找到解。
但是三个以上游离红球的计算就复杂了

点评

k=0是例外,只需0步,而不是1步。其余k都成立。  发表于 2019-6-2 19:37
2球逃逸好像总是不需要隔板  发表于 2019-6-2 15:51
n=2,状态是“红蓝红蓝”,符合“n-1个都已经归位,只留下1个游离在外的情况”,这个游离者离其它红球还间隔k=1个篮球,明明平均需要2步的  发表于 2019-6-2 12:21
还间隔k个蓝球时……平均需要的步数并不是调和级数,比如按这个公式k=1平均一步——显然错了  发表于 2019-6-1 23:35
这调和级数我也归纳了一下,确实如此。所以1球归位就完美解决了。2球的临界点应该是有规律的。比如:总是在1/e的位置(我乱猜的)。  发表于 2019-6-1 21:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-2 11:41:42 来自手机 | 显示全部楼层
三个以上游离红球情况应该可以通过迭代的方法求解,不过计算量很难估计,但是不会小
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-3 08:55:45 | 显示全部楼层
两个游离红球的策略:
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-3 08:58:03 | 显示全部楼层
两个游离红球需要移动的平均步数(其中第二个参数为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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-3 12:53:05 | 显示全部楼层
本帖最后由 zeroieme 于 2019-6-4 02:45 编辑

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

11情形。存在1/2机会已经排好。按前面设计用挡版隔离后中央区域为00;1/2机会没排好。先进行一次洗球,看结果继续。所以有  F(1,1)=1/2  F(0,0)+1/2(1+ F(1,1))。 F(0,0)=0,解方程得 F(1,1)=1。
21,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)。
.....
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-12 20:47 , Processed in 0.065486 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表