W**********r
发帖数: 68 | 1 一个4x4的board，t=0的时刻，每个格子里都有一只老鼠，每一秒，老鼠会随机跳到相
邻的格子，问：
（1）t=1的时刻，没有老鼠的格子的数量（expectation）？
这个做出来了，就是设Xi = 1，（i = 1，2，。。。，16）如果格子里有老鼠，没有Xi
= 0，可以计算出E（Xi）= P（Xi = 0），根据格子所处位置的不同有三种情况，一种
是四个角的格子（4个），一种是边上的格子（8个），一种是中间的格子（4个）
（2）t = 无穷大时，空格子的数量的stationary distribution，问计算的思路？
这个没想出来，应该是要用Markov Chain算，但是没有想出来合适的state variables
去计算transition probability，要求只是说出计算的思路，真计算可能需要很长时间
。。。
看看有没有大哥会？ |
T********g
发帖数: 42 | 2 感谢楼主分享。这个老鼠题还挺好玩的。俺觉得你的第一部分做法很好。
至于第二部分，版上牛人众多，俺还是抛砖引玉。
如果按照你的思路用Markov Chain，大概有两种层次考虑States吧。
第一种比较暴力，看作16个不同的格子，每个格子里老鼠的数量从0到16，那么总的可
能性个数为17的16次方。这个数字貌似比较大，实际操作比较困难。可以考虑加上个
Constraint such that the sum of numbers of mice in each cell is equal to 16.
第二种跟第一种等价。仍然看作16个不同的格子，那么一共有16只老鼠往这里面放，一
共有多少种放法。可考虑迭代法，这里有三个变量：
N(x,y): x为格子的数量，y为老鼠的数量, N为所求数目.那么N满足的关系为：
N(x,y) = N(x-1,y) + N(x-1,y-1) + ... + N(x-1,0)
N(1,y) = 1.
第三种，把16个格子里面分为三类。分类如楼主所说，角，边，内部分别有4，8，4个
格子。那么一共有多少种放法，可以这样计算：
先考虑16个老鼠放到三个格子里面的数量分别为(x,y,16-x-y).那么如果有n个相同的格
子，往里面放z个相同的老鼠，方式共有 c^z_(n+z-1) = (n+z-1)!/z!/(n-1)! 种。
Then you sum this expression over all values of (x,y,16-x-y) such that x, y
\in {0,1,2,...}.
俺想到的办法都比较土，还请高手指点有木有简便方法。 |
x******a
发帖数: 6336 | 3 for (2), let me guess it is (3/4)^4... |
W**********r
发帖数: 68 | 4 怎么guess的，那个面试的人说算起来很复杂，应该不是这么简单的答案吧，我也不知
道怎么做还。。。
【在 x******a 的大作中提到】
: for (2), let me guess it is (3/4)^4...
|
W**********r
发帖数: 68 | 5 怎么guess的，那个面试的人说算起来很复杂，应该不是这么简单的答案吧，我也不知
道怎么做还。。。
【在 x******a 的大作中提到】
: for (2), let me guess it is (3/4)^4...
|
n*********e
发帖数: 3 | 6 Just a thought. Please correct if this is not right.
If use Markov transition matrix, we may calculate the probability that a
mouse jump from cell i to j after N iterations.
The transition matrix A is built as follows:
There are 36 status. 4x4 of them are the board; 20 of then are the outside
cells around the board. The transition matrix is a 36x36 matrix.
One element in the matrix A, A_ij means the probability at a time that a
mouse jumps from cell i to j, where i,j range from 1 to 36.
You can also calculate the limit of A^N, as N -> inf.
A matlab simulation code looks like
%transition matrix
A = zeros(36,36);
% outside
out = [1:6 7 12 13 18 19 24 25 30 31:36];
for idx = 1:numel(out)
A(out(idx),out(idx)) = 1; % once jump to outside cell, stay with
probability 1.
end
% inside
in = [8:11, 14:17, 20:23, 26:29];
for idx = 1:numel(in)
left = in(idx) - 1;
right = in(idx) + 1;
up = in(idx) - 6;
down = in(idx) + 6;
A(in(idx), left) = 0.25;
A(in(idx), right) = 0.25;
A(in(idx), up) = 0.25;
A(in(idx), down) = 0.25;
end
%initial vector
A0 = ones(1,36);
A0(1,out) = 0;
N = 100; % iteration times; a large number
B = A0*A^N; |
W**********r
发帖数: 68 | 7 我觉得你这个思路很有意思，不过那个老鼠是不能跳出board的，只能调到临近的格子
，所以不同位置的 老鼠跳到临近格子的概率是不一样的，但是你的这个方法还是可以
work的~
【在 n*********e 的大作中提到】
: Just a thought. Please correct if this is not right.
: If use Markov transition matrix, we may calculate the probability that a
: mouse jump from cell i to j after N iterations.
: The transition matrix A is built as follows:
: There are 36 status. 4x4 of them are the board; 20 of then are the outside
: cells around the board. The transition matrix is a 36x36 matrix.
: One element in the matrix A, A_ij means the probability at a time that a
: mouse jumps from cell i to j, where i,j range from 1 to 36.
: You can also calculate the limit of A^N, as N -> inf.
: A matlab simulation code looks like
|
l********m
发帖数: 284 | 8 The transition matrix should be 4*4 matrix. And the probability from one
cell jump into the adjunct cell?
My knowledge has digest with meal.... |
n*********e
发帖数: 3 | 9 理解题意有误...如果不跳出的话，那就是16x16的矩阵
转移概率每次不变（不知对不对）.好像还是没有直接回答“空格子的数量的
stationary distribution”的问题。。。wondering
%transition matrix
A = zeros(16,16);
% corner/side
corner = [1 4 13 16];
side = [2 3 9 12;5 8 14 15];
for idx = 1:numel(corner)
A(corner(idx),side(:,idx)) = 0.5;
end
% side
side = side(:);
for idx = 1:numel(side);
row = ceil(side(idx) / 4);
col = rem(side(idx), 4);
left = side(idx) - 1;
right = side(idx) + 1;
up = side(idx) - 4;
down = side(idx) + 4;
if rem(left,4) > 0 && ceil(left/4) == row
A(side(idx), left) = 1/3;
end
if rem(right,4) < 5 && ceil(right/4) == row
A(side(idx), right) = 1/3;
end
if ceil(up/4) > 0 && rem(up,4) == col
A(side(idx), up) = 1/3;
end
if ceil(down/4) < 5 && rem(down,4) == col
A(side(idx), down) = 1/3;
end
end
% inside
in = [6,7,10,11];
for idx = 1:numel(in)
left = in(idx) - 1;
right = in(idx) + 1;
up = in(idx) - 4;
down = in(idx) + 4;
A(in(idx), left) = 0.25;
A(in(idx), right) = 0.25;
A(in(idx), up) = 0.25;
A(in(idx), down) = 0.25;
end
%initial vector
A0 = ones(1,16);
N = 300;% 较大的一个数；N在10+的时候，At已经较收敛了。
At = A0;
for idx = 1:N
At = At * A; % find number of mouse after one iteration
end
% sum(At) == 16 |
m****z
发帖数: 15 | 10 这个想法真好！
算空格子的话，可以先求出求出每只老鼠在每个格子的stationary distribution，例
如对于最开始在第一个格子上的老鼠，initial distribution 是p1_0= [1, 0, 0, ...
, 0]^T, stationary distribution 是p1_t=p1_0*A^N (N 趋向无限大) 。
同样可以知道p2_t=[0,1,0,...,0]^T*A^N, 以及p3_t,....p16_t. 每只老鼠的
stationary distribution。（这些stationary distribution应该是相等的。）
然后就可以求空格子的数量的分布了，虽然比较麻烦。例如空格子数为0的概率就是每
个格子上都至少有一只老鼠的概率，prod_（i=1）^16 (1-prod_（j=1）^16(1-p_j(i))
) 。
（空格子的数量的期望倒是好求一些）
【在 n*********e 的大作中提到】
: 理解题意有误...如果不跳出的话，那就是16x16的矩阵
: 转移概率每次不变（不知对不对）.好像还是没有直接回答“空格子的数量的
: stationary distribution”的问题。。。wondering
: %transition matrix
: A = zeros(16,16);
: % corner/side
: corner = [1 4 13 16];
: side = [2 3 9 12;5 8 14 15];
: for idx = 1:numel(corner)
: A(corner(idx),side(:,idx)) = 0.5;
|
|
|
l*********g
发帖数: 1899 | 11 这道题的转移概率如果能每次不变，我认为这题就直接用马可夫矩阵可解。
而个人认为这道题的每次的转移概率不仅是变化的而且是不确定的，举个例子，就看16
个格子里第二行第二列那个格子，在t=0时，这里头是一只老鼠，而当t=1时，这格子里
的老鼠数可以等于0，1,2,3,4都有可能，而当t=2时，t=1时可能的每种状态都能又分别
对应可能的几种状态。而如果要用马可夫矩阵（链）去解，每秒钟，格子之间老鼠的转
移概率（或者说这个系数）须是个常数，而不是像这里这种不确定的情况。
因此我认为这道题可能不是直接用马可夫矩阵（链）可解。
【在 n*********e 的大作中提到】
: 理解题意有误...如果不跳出的话，那就是16x16的矩阵
: 转移概率每次不变（不知对不对）.好像还是没有直接回答“空格子的数量的
: stationary distribution”的问题。。。wondering
: %transition matrix
: A = zeros(16,16);
: % corner/side
: corner = [1 4 13 16];
: side = [2 3 9 12;5 8 14 15];
: for idx = 1:numel(corner)
: A(corner(idx),side(:,idx)) = 0.5;
|
b*******4
发帖数: 65 | 12 Let X_i be the static distribution of number of mouse is block i for i=1...
16 and X be the vector.
Matrix A 16 by 16 be the transition matrix with A_ij representing the
probability that mouse in block i will transit to block j. For static
distribution, we will have
X=AX
Then the distribution will be the eigenvector of A with the corresponding
eigenvalue having one.
This is a standard control theory (linear dynamical system) problem.
一个4x4的board，t=0的时刻，每个格子里都有一只老鼠，每一秒，老鼠会随机跳到相
邻的格子，问：（1）t=1的时刻，没有老鼠的格子的数量（expectation）？这个做出.
.......
【在 W**********r 的大作中提到】
: 一个4x4的board，t=0的时刻，每个格子里都有一只老鼠，每一秒，老鼠会随机跳到相
: 邻的格子，问：
: （1）t=1的时刻，没有老鼠的格子的数量（expectation）？
: 这个做出来了，就是设Xi = 1，（i = 1，2，。。。，16）如果格子里有老鼠，没有Xi
: = 0，可以计算出E（Xi）= P（Xi = 0），根据格子所处位置的不同有三种情况，一种
: 是四个角的格子（4个），一种是边上的格子（8个），一种是中间的格子（4个）
: （2）t = 无穷大时，空格子的数量的stationary distribution，问计算的思路？
: 这个没想出来，应该是要用Markov Chain算，但是没有想出来合适的state variables
: 去计算transition probability，要求只是说出计算的思路，真计算可能需要很长时间
: 。。。
|
l*********g
发帖数: 1899 | 13 可以列一下你以下提到的这个16*16的矩阵的第一行（共16个元素）吗？
谢谢。
【在 b*******4 的大作中提到】
: Let X_i be the static distribution of number of mouse is block i for i=1...
: 16 and X be the vector.
: Matrix A 16 by 16 be the transition matrix with A_ij representing the
: probability that mouse in block i will transit to block j. For static
: distribution, we will have
: X=AX
: Then the distribution will be the eigenvector of A with the corresponding
: eigenvalue having one.
: This is a standard control theory (linear dynamical system) problem.
:
|
q*****t
发帖数: 152 | 14 你们转移矩阵的态是什么？
如果你定义转移矩阵的态是空格子的数量
我也觉得转移矩阵是随时间变化的 |
W**********r
发帖数: 68 | 15 是不是应该是X = A^T X 啊？
【在 b*******4 的大作中提到】
: Let X_i be the static distribution of number of mouse is block i for i=1...
: 16 and X be the vector.
: Matrix A 16 by 16 be the transition matrix with A_ij representing the
: probability that mouse in block i will transit to block j. For static
: distribution, we will have
: X=AX
: Then the distribution will be the eigenvector of A with the corresponding
: eigenvalue having one.
: This is a standard control theory (linear dynamical system) problem.
:
|
q*****t
发帖数: 152 | 16 题目问得是空格子的distribution
没有你想得这么简单
【在 b*******4 的大作中提到】
: Let X_i be the static distribution of number of mouse is block i for i=1...
: 16 and X be the vector.
: Matrix A 16 by 16 be the transition matrix with A_ij representing the
: probability that mouse in block i will transit to block j. For static
: distribution, we will have
: X=AX
: Then the distribution will be the eigenvector of A with the corresponding
: eigenvalue having one.
: This is a standard control theory (linear dynamical system) problem.
:
|
x*******9
发帖数: 1 | 17
Yes. Even if you've got the stationary dist, it's just half way down.
Now simplify the question to: putting 16 balls into 16 boxes with equal prob
, what's the dist. of the No. of empty box?
My simplification might be wrong, depends on whether I got the stationary
dist. right.
【在 q*****t 的大作中提到】
: 题目问得是空格子的distribution
: 没有你想得这么简单
|
c**********e
发帖数: 534 | |
m***8
发帖数: 8 | 19 第二个部分可不可以这样算 也是接着第一部分的想法 四个角的叫做A类 八个靠边的叫
做B类 四个中心的叫做C类
不同类之间的transition prob应该好算
A->B: 1
B->C: 1/3
B->B: 1/3
B->A: 1/3
C->B: 1/2
C->A: 1/2
然后得出stationary distr.
然后相同类的格子应该是平均分布 继而得出整个的stationary distr. |
q*****t
发帖数: 152 | 20 你计算的是各个类之间的transition prob
题目问题的空格子的distribution，所以根本不是题目想要的东西
【在 m***8 的大作中提到】
: 第二个部分可不可以这样算 也是接着第一部分的想法 四个角的叫做A类 八个靠边的叫
: 做B类 四个中心的叫做C类
: 不同类之间的transition prob应该好算
: A->B: 1
: B->C: 1/3
: B->B: 1/3
: B->A: 1/3
: C->B: 1/2
: C->A: 1/2
: 然后得出stationary distr.
|
|
|
b*******4
发帖数: 65 | 21 拿到所有格子静态分布老鼠数量。 对于每一个格子来讲，你知道了它周围老鼠数，就
可以算出静态时刻没有老鼠跳进来的概率，
Joint probability that none of adjacent mouse jump in.
题目问得是空格子的distribution没有你想得这么简单
【在 q*****t 的大作中提到】
: 题目问得是空格子的distribution
: 没有你想得这么简单
|
b*******4
发帖数: 65 | 22 X是静态时刻老鼠数量vector
算出X，就知道对于每个格子而言，静态时周围有多少老鼠，也就知道了none of 这些
老鼠跳进来的概率，即这个格子空的概率
一己愚见，希望大家多交流
X=AX是因为X进入静态 转移一步也不会变
是不是应该是X = A^T X 啊？
【在 W**********r 的大作中提到】
: 是不是应该是X = A^T X 啊？
|
q*****t
发帖数: 152 | 23 题目问得是空格子数目的概率分布
不是每个格子是不是空的概率分布
【在 b*******4 的大作中提到】
: X是静态时刻老鼠数量vector
: 算出X，就知道对于每个格子而言，静态时周围有多少老鼠，也就知道了none of 这些
: 老鼠跳进来的概率，即这个格子空的概率
: 一己愚见，希望大家多交流
: X=AX是因为X进入静态 转移一步也不会变
:
: 是不是应该是X = A^T X 啊？
|
m***8
发帖数: 8 | 24 得到一只小老鼠情况下的4*4的棋盘中的stationary distr之后
你应该问自己的问题是
如果有16个小老鼠在这个4*4的棋盘 那么空格个数的distribution的个数要怎么算
这个既然已经是stationary的
那么这16个小老鼠就是被一个一个
以stationary distr被扔在棋盘上
这个可以这样算出来
【在 q*****t 的大作中提到】
: 你计算的是各个类之间的transition prob
: 题目问题的空格子的distribution，所以根本不是题目想要的东西
|
f*******a
发帖数: 663 | 25 一点看法，供参考
这里只考虑第2问
其实t无穷时，很显然所有老鼠在棋盘上的分布是一样的（可以通过转移矩阵来直接计
算）
对于每个格子而言，空的概率是 一个老鼠不在该格点的16次方
那么总的期望就很容易求 |
b*******4
发帖数: 65 | 26 你拿到每个格子是否空之后怎么算？ 每个格子是否空不独立
一点看法，供参考这里只考虑第2问其实t无穷时，很显然所有老鼠在棋盘上的分布是一
样的（可以通过转移矩阵来直接计算）对于每个格子而言，空的概率是 一个老鼠不在
该格点的16次方那么总........
【在 f*******a 的大作中提到】
: 一点看法，供参考
: 这里只考虑第2问
: 其实t无穷时，很显然所有老鼠在棋盘上的分布是一样的（可以通过转移矩阵来直接计
: 算）
: 对于每个格子而言，空的概率是 一个老鼠不在该格点的16次方
: 那么总的期望就很容易求
|
f*******a
发帖数: 663 | 27 你再想想这些事件的关联性
不是每一步都关联
【在 b*******4 的大作中提到】
: 你拿到每个格子是否空之后怎么算？ 每个格子是否空不独立
:
: 一点看法，供参考这里只考虑第2问其实t无穷时，很显然所有老鼠在棋盘上的分布是一
: 样的（可以通过转移矩阵来直接计算）对于每个格子而言，空的概率是 一个老鼠不在
: 该格点的16次方那么总........
|
