数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 251|回复: 29

A从 m×n 格子左下角起每步向右或向上,B从右上角起每步向左或向下,求途中相遇的概率

[复制链接]
发表于 2019-6-7 17:40 | 显示全部楼层 |阅读模式
本帖最后由 luyuanhong 于 2019-6-10 12:11 编辑

Points A and B are opposite corners of a 5×5 grid.
Alice starts at point A, and each second, walks one edge right or up (if a point has two options, each direction has a 50% chance) until Alice reaches point B.

At the same time, Bob starts at point B, and each second he walks one edge left or down (if a point has two options, each direction has a 50% chance) in order to reach point A.

What is the probability Alice and Bob meet during their random walks? (Meet means occupy the same point at the same time).

What is the probability for an n by n grid? What is the limiting probability as n goes to infinity?

计算机程序模拟或理论计算均可。
如果格子是5×9的呢?如何计算?
如果格子是m*n的呢?如何计算?

本帖被以下淘专辑推荐:

  • · 好貼|主题: 7, 订阅: 0
发表于 2019-6-8 18:05 | 显示全部楼层
宁愿怀疑你的数值,也不怀疑陆老师的,你肯定是错的
回复 支持 1 反对 0

使用道具 举报

发表于 2019-6-8 11:23 | 显示全部楼层
这不就是高尔顿钉板实验真人版么?
回复 支持 反对

使用道具 举报

发表于 2019-6-8 12:26 | 显示全部楼层
本帖最后由 luyuanhong 于 2019-6-8 12:36 编辑

A从m×n格子左下角起每步向右或向上,B从右上角起每步向左或向下,求途中相遇的概率.GIF

A从m×n格子左下角起每步向右或向上,B从右上角起每步向左或向下,求途中相遇的概率.rar (39.54 KB, 下载次数: 3)

点评

老陆,这下你是真错了!  发表于 2019-6-8 16:57
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:00 | 显示全部楼层
本帖最后由 markfang2050 于 2019-6-8 21:37 编辑

Alice初始位置在(0,0),Bob初始位置在(5,5)。

1000000次python3.6模拟Alice,Bob二人在[5×5]格子中按照一定规则随机行走相遇的概率=0.243623

程序运行时间 15.208696365356445 秒。


理论计算准确值:252/1024 = 63/256.

The probability they meet is approximately 24.6%.


Probability calculation

How many paths are there from A to a possible common meeting point? For a random walker, 2 possible paths for a step, so after k steps there are 2k possible paths. After 5 steps Alice has 25 paths, and so does Bob. thus, there are (2^5)*(2^5) = 4^5 total paths they could both take after 5 steps.

Furthermore, we have determined the point that is j units up from A and 5 – j units right from A has a number of paths equal to the binomial coefficient C(5, j), where C(n, k) = n!/[k!(n – k)!]. The same is true for Alice and Bob, so the number of ways that both meet at to a particular point is the square of a binomial coefficient.

As Alice and Bob can meet at any of the 6 points along the main diagonal, the total number of paths in which they could meet is the sum of the squares of the 6 binomial coefficients:

1^2 + 5^2 + 10^2 + 10^2 + 5^2 + 1^2 = 252*

This needs to be divided by the total number of paths they could take, which is 4^5 = 1024*.

252/1024 = 63/256.

The probability they meet is approximately 24.6%.
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:01 | 显示全部楼层
这道题目是很容易计算理论值的,显然.·.·.的条件是必须满足的,因为相遇时双方走的步数必须相等(时间要求同时)。
而双方到达反对角线上各点的分布是满足二项分布,同时到达各点的概率显然是各个概率的平方。
然后再求和,结果应该就是                                       
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:01 | 显示全部楼层
Alice跟Bob只能在 x+y=n 的反斜线上相遇
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:02 | 显示全部楼层
1Alice初始位置在(0,0),Bob初始位置在(9,5)。

100000次python3.6模拟Alice,Bob二人在[5×9]格子中按照一定规则随机行走相遇的概率=0.119790

程序运行时间 2.5395660400390625 秒。
Alice初始位置在(0,0),Bob初始位置在(5,6)。

100000次python3.6模拟Alice,Bob二人在[6×5]格子中按照一定规则随机行走相遇的概率=0.001560

程序运行时间 2.6504836082458496 秒。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:08 | 显示全部楼层
Generalizing to n by n board

On an n by n board, Alice and Bob could possibly meet at the points that are n steps away–along the diagonal of the grid.

As each walker has 2 choices in a step, there are 2n possible paths in n steps for each walker, making for a total of (2n)(2n) = 4n paths.

The number of paths for each walker to a point also follows a binomial distribution. The point that is j units up from A and n – j units right from A has a number of paths equal to the binomial coefficient C(n, j). The same is true for Alice and Bob, so the number of paths where they pick the same point is the square of each binomial coefficient. There are n + 1 points at which they could meet, and the number of ways they can meet is the sum of the squares of the binomial coefficients:


There is a nice simplification to this formula. First we use the property C(n, j) = C(n, n – j), and we write the product as:


Now imagine we have a group of n women and n men. How many ways are there to form a group of n people? The above sum counts this. The first term is the number of ways to have 0 women and n men, the next term is the number of ways to have 1 woman and n – 1 men, and so on.

But we also know the number of ways to pick n people from a group of 2n is equal to C(2n, n). Thus, the two ways to count are equal, and we have derived the identity:


We now divide the number of ways they could meet by the total number of paths 4n:

Pr(meet) = C(2n,n)/4n
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:10 | 显示全部楼层
The term C(2n, n) is known as the central binomial coefficient, and it has a rather interesting limit. As n goes to infinity, it is approximately 4n/√(π n).

Using this approximation, we have our probability is related to pi!

We could therefore approximate pi as follows. Simulate two random walkers on a large n by n grid.

As the probability approaches 1/√(π n), we can estimate by:

(1/Pr(meet)2 n) ~ π
Before you actually try to code this, the formula has very poor accuracy. Even on a 1000×1000 grid, it will only approximate pi to 2 decimal places accurately.
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-8 17:16 | 显示全部楼层
本帖最后由 markfang2050 于 2019-6-8 17:18 编辑

第1次实验

第1步行走,Alice位置(1,0),Bob位置(9,4)。

第2步行走,Alice位置(1,1),Bob位置(8,4)。

第3步行走,Alice位置(1,2),Bob位置(7,4)。

第4步行走,Alice位置(1,3),Bob位置(7,3)。

第5步行走,Alice位置(2,3),Bob位置(7,2)。

第6步行走,Alice位置(3,3),Bob位置(6,2)。

第7步行走,Alice位置(4,3),Bob位置(5,2)。

第8步行走,Alice位置(5,3),Bob位置(5,1)。

第9步行走,Alice位置(6,3),Bob位置(4,1)。

第10步行走,Alice位置(7,3),Bob位置(3,0)。

第11步行走,Alice位置(7,4),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第2次实验

第1步行走,Alice位置(1,0),Bob位置(9,4)。

第2步行走,Alice位置(1,1),Bob位置(8,4)。

第3步行走,Alice位置(2,1),Bob位置(8,3)。

第4步行走,Alice位置(2,2),Bob位置(7,3)。

第5步行走,Alice位置(3,2),Bob位置(7,2)。

第6步行走,Alice位置(4,2),Bob位置(6,2)。

第7步行走,Alice位置(4,3),Bob位置(5,2)。

第8步行走,Alice位置(5,3),Bob位置(4,2)。

第9步行走,Alice位置(6,3),Bob位置(3,2)。

第10步行走,Alice位置(6,4),Bob位置(3,1)。

第11步行走,Alice位置(7,4),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第3次实验

第1步行走,Alice位置(1,0),Bob位置(8,5)。

第2步行走,Alice位置(1,1),Bob位置(7,5)。

第3步行走,Alice位置(1,2),Bob位置(6,5)。

第4步行走,Alice位置(2,2),Bob位置(5,5)。

第5步行走,Alice位置(3,2),Bob位置(5,4)。

第6步行走,Alice位置(4,2),Bob位置(4,4)。

第7步行走,Alice位置(5,2),Bob位置(3,4)。

第8步行走,Alice位置(5,3),Bob位置(2,4)。

第9步行走,Alice位置(6,3),Bob位置(2,3)。

第10步行走,Alice位置(6,4),Bob位置(2,2)。

第11步行走,Alice位置(7,5),Bob位置(2,1)。

第12步行走,Alice位置(8,5),Bob位置(1,1)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第4次实验

第1步行走,Alice位置(1,0),Bob位置(8,5)。

第2步行走,Alice位置(1,1),Bob位置(8,4)。

第3步行走,Alice位置(2,1),Bob位置(7,4)。

第4步行走,Alice位置(3,1),Bob位置(6,4)。

第5步行走,Alice位置(4,1),Bob位置(5,4)。

第6步行走,Alice位置(5,1),Bob位置(5,3)。

第7步行走,Alice位置(6,1),Bob位置(4,3)。

第8步行走,Alice位置(7,1),Bob位置(4,2)。

第9步行走,Alice位置(7,2),Bob位置(4,1)。

第10步行走,Alice位置(7,3),Bob位置(3,0)。

第11步行走,Alice位置(8,3),Bob位置(2,0)。

第12步行走,Alice位置(8,4),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第5次实验

第1步行走,Alice位置(0,1),Bob位置(8,5)。

第2步行走,Alice位置(1,1),Bob位置(8,4)。

第3步行走,Alice位置(2,1),Bob位置(7,4)。

第4步行走,Alice位置(2,2),Bob位置(6,4)。

第5步行走,Alice位置(3,2),Bob位置(6,3)。

第6步行走,Alice位置(3,3),Bob位置(5,3)。

第7步行走,Alice位置(3,4),Bob位置(5,2)。

第8步行走,Alice位置(4,5),Bob位置(4,2)。

第9步行走,Alice位置(5,5),Bob位置(4,1)。

第10步行走,Alice位置(6,5),Bob位置(3,0)。

第11步行走,Alice位置(7,5),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第6次实验

第1步行走,Alice位置(1,0),Bob位置(9,4)。

第2步行走,Alice位置(1,1),Bob位置(9,3)。

第3步行走,Alice位置(2,1),Bob位置(8,3)。

第4步行走,Alice位置(3,1),Bob位置(8,2)。

第5步行走,Alice位置(3,2),Bob位置(8,1)。

第6步行走,Alice位置(4,2),Bob位置(7,0)。

第7步行走,Alice位置(5,2),Bob位置(6,0)。

第8步行走,Alice位置(5,3),Bob位置(5,0)。

第9步行走,Alice位置(5,4),Bob位置(4,0)。

第10步行走,Alice位置(6,5),Bob位置(3,0)。

第11步行走,Alice位置(7,5),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第7次实验

第1步行走,Alice位置(1,0),Bob位置(8,5)。

第2步行走,Alice位置(2,0),Bob位置(7,5)。

第3步行走,Alice位置(3,0),Bob位置(6,5)。

第4步行走,Alice位置(3,1),Bob位置(6,4)。

第5步行走,Alice位置(4,1),Bob位置(5,4)。

第6步行走,Alice位置(5,1),Bob位置(5,3)。

第7步行走,Alice位置(5,2),Bob位置(4,3)。

第8步行走,Alice位置(5,3),Bob位置(3,3)。

第9步行走,Alice位置(5,4),Bob位置(3,2)。

第10步行走,Alice位置(6,4),Bob位置(2,2)。

第11步行走,Alice位置(7,5),Bob位置(2,1)。

第12步行走,Alice位置(8,5),Bob位置(1,1)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第8次实验

第1步行走,Alice位置(1,0),Bob位置(9,4)。

第2步行走,Alice位置(1,1),Bob位置(9,3)。

第3步行走,Alice位置(1,2),Bob位置(9,2)。

第4步行走,Alice位置(1,3),Bob位置(9,1)。

第5步行走,Alice位置(2,3),Bob位置(8,1)。

第6步行走,Alice位置(3,3),Bob位置(7,1)。

第7步行走,Alice位置(4,3),Bob位置(6,1)。

第8步行走,Alice位置(5,3),Bob位置(5,0)。

第9步行走,Alice位置(5,4),Bob位置(4,0)。

第10步行走,Alice位置(6,5),Bob位置(3,0)。

第11步行走,Alice位置(7,5),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第9次实验

第1步行走,Alice位置(1,0),Bob位置(8,5)。

第2步行走,Alice位置(2,0),Bob位置(8,4)。

第3步行走,Alice位置(2,1),Bob位置(8,3)。

第4步行走,Alice位置(2,2),Bob位置(8,2)。

第5步行走,Alice位置(3,2),Bob位置(7,2)。

第6步行走,Alice位置(3,3),Bob位置(7,1)。

第7步行走,Alice位置(3,4),Bob位置(6,0)。

第8步行走,Alice位置(4,4),Bob位置(5,0)。

第9步行走,Alice位置(5,5),Bob位置(4,0)。

第10步行走,Alice位置(6,5),Bob位置(3,0)。

第11步行走,Alice位置(7,5),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

第10次实验

第1步行走,Alice位置(0,1),Bob位置(8,5)。

第2步行走,Alice位置(1,1),Bob位置(8,4)。

第3步行走,Alice位置(1,2),Bob位置(8,3)。

第4步行走,Alice位置(1,3),Bob位置(8,2)。

第5步行走,Alice位置(2,3),Bob位置(8,1)。

第6步行走,Alice位置(3,3),Bob位置(7,1)。

第7步行走,Alice位置(3,4),Bob位置(6,1)。

第8步行走,Alice位置(4,4),Bob位置(5,0)。

第9步行走,Alice位置(5,4),Bob位置(4,0)。

第10步行走,Alice位置(6,5),Bob位置(3,0)。

第11步行走,Alice位置(7,5),Bob位置(2,0)。

第12步行走,Alice位置(8,5),Bob位置(1,0)。

第13步行走,Alice位置(9,5),Bob位置(0,0)。

第14步行走,Alice位置(9,5),Bob位置(0,0)。

Alice初始位置在(0,0),Bob初始位置在(9,5)。

10次python3.6模拟Alice,Bob二人在[5×9]格子中按照一定规则随机行走相遇的概率=0.000000

程序运行时间 2.1711037158966064 秒。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2019-6-26 20:16 , Processed in 0.240756 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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