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

markfang2050

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的呢？如何计算？

Ysu2008

这不就是高尔顿钉板实验真人版么？

luyuanhong

markfang2050

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%.

markfang2050

这道题目是很容易计算理论值的，显然.·.·.的条件是必须满足的，因为相遇时双方走的步数必须相等（时间要求同时）。
而双方到达反对角线上各点的分布是满足二项分布，同时到达各点的概率显然是各个概率的平方。
然后再求和，结果应该就是                                       

markfang2050

Alice跟Bob只能在 x+y=n 的反斜线上相遇

markfang2050

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 秒。

markfang2050

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

markfang2050

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.

markfang2050

第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 秒。