n******t
发帖数: 189 | 1 we try to toss a fair die, let Sn is the sum of the first n tosses result,
what is the probability that Sn is divisible by 13 as n goes to infinity? | d********t
发帖数: 9628 | 2 Markov chain?
【在 n******t 的大作中提到】
: we try to toss a fair die, let Sn is the sum of the first n tosses result,
: what is the probability that Sn is divisible by 13 as n goes to infinity?
| r*******y
发帖数: 1081 | 3 1/ 13 ?
【在 n******t 的大作中提到】
: we try to toss a fair die, let Sn is the sum of the first n tosses result,
: what is the probability that Sn is divisible by 13 as n goes to infinity?
| l******i
发帖数: 1404 | 4 首先感谢楼主贡献，
如果可以的话，希望楼主最好能在帖子标题里加上问题的类别和关键词，
例如该帖名字可为：【Probability】a problem
这样方便我们工作人员整理，谢谢啦。
我已经把标题改了。 | n******t
发帖数: 189 | 5 it should be 1/13 by MC.But how?
【在 d********t 的大作中提到】
: Markov chain?
| d********t
发帖数: 9628 | 6 math induction?
【在 n******t 的大作中提到】
: it should be 1/13 by MC.But how?
| n******t
发帖数: 189 | 7 I got the idea. Write the MC tran matrix and get the stationary probability.
..
【在 d********t 的大作中提到】
: math induction?
| d********t
发帖数: 9628 | 8 I thought about that. But I doubt if that's the interviewer's intention
since the matrix could be big and multiplying it to get stationary may not
be easy.
probability.
【在 n******t 的大作中提到】
: I got the idea. Write the MC tran matrix and get the stationary probability.
: ..
| n******t
发帖数: 189 | 9 luckily, the tran prob matrix is a double stochastic one...
【在 d********t 的大作中提到】
: I thought about that. But I doubt if that's the interviewer's intention
: since the matrix could be big and multiplying it to get stationary may not
: be easy.
:
: probability.
| d********t
发帖数: 9628 | 10 what's a "double stochastic one"?
Could you write down the matrix, please?
Thanks.
【在 n******t 的大作中提到】
: luckily, the tran prob matrix is a double stochastic one...
| k*****y
发帖数: 744 | 11 I guess the intuitive way to see this is the Central Limit Theorem:
Let m and var be the mean and variance of S_1.
When N is large enough, (S_N-N*m)/sqrt(N*var) is roughly the standard
normal distribution N(0,1) in distribution.
So P( S_N = 0 mod 13 ) roughly equals to the sum of some 1/13 piece in every interval of length 13/sqrt{N*Var} (which goes to 0).
Since the pdf of N(0,1) is continuous and integrable, the limit is strictly
equal to 1/13. | r********a
发帖数: 139 | 12 P(Sn mod 13 = i) = P_i (i=0,...,12)
transition matrix {a_ij} = {1/6, when 0
P_i = Sum P_j * a_ij (j=0,...,12)
12 rotationally symmetrical equations, intuitive guess is all P_i are equal,
therefore 1/13 | y**k
发帖数: 222 | 13 Let me try.
Let T[n, i] = #{Sn| Sn == i mod 13} ( we consider i and 13 + i the same
if they are the second indexes of T[n, i]), and A[n, i] = (T[n, i+1] - T[n,
i])/6^n.
We have A[n+1, i] = (A[n, i-1] + A[n, i-2] + ... + A[n, i-6])/6, which is
not interesting by itself. But if go one step further, we have
A[n+2, i+1] = (A[n, i-1] +2 A[n, i-2] + 3 A[n, i-3] + ... + 6 A[n, i-6]
+ ... + 3A[n, i-9] + 2 A[n, i-10] + A[n, i-11])/36.
Note that there are 36 A[n, j]'s ( 1 + 2 +...+ 5 + 6 + 5 + ..+ 2 + 1 =36
), which again seems not interesting. However, note A[n, 0] + A[n, 1] + ...
+ A[n, 12] = 0, we can write
A[n+2, i+1] = (sum of 25 A[n, j]'s - A[n, i-12] -A[n, i-13])/36.
Thus we have max (|A[n+2, j]|) <= 27/36 * max(|A[n, j]|), which yields A
[n, j] --> 0. | n******t
发帖数: 189 | 14 the sum of row and sum of col is all 1. then, it is ergodic and stat prob is
1/n..
Thanks for discussion. this is my hw...
【在 d********t 的大作中提到】
: what's a "double stochastic one"?
: Could you write down the matrix, please?
: Thanks.
|
|
