x*****i
发帖数: 287 | 1 $R(n)$ is used to generate a discrete number following
uniform distribution U[0, n-1]. Let $x_0 = 10^{100}, x_i = R(
x_{i-1} )$, and let s is
the stopping time i.e. $x_s = 0$. Calculate $E[s].$ |
L**********u
发帖数: 194 | 2 用markov chain 来做。
如果起点x_0=n, 则markov chain 里有n+1 states,分别用0，1，2，。。。。n来表示
。transition matrix是如下：
1 1 1/2 1/3 ... 1/n
0 0 1/2 1/3 ... 1/n
0 0 0 1/3 ... 1/n
... ... ... ... ... ... ...
0 0 0 0 ... 0
记右下角n x n 矩阵为 Q， 计算I—Q的逆矩阵，注意这个矩阵是上三角，逆很好求，
答案就是逆矩阵最后一列entries的和。
希望我没有做错，呵呵。 |
M*******i
发帖数: 82 | |
L**********u
发帖数: 194 | 4 用数学归纳法也可以做。
【在 M*******i 的大作中提到】
: 1 + 1/2 + ... + 1/n
|
L**********u
发帖数: 194 | 5 刚才仔细算了我的markov chain 方法，和MarkJoshi的结果一样。
看来做对了。呵呵。 |
x*****i
发帖数: 287 | 6 zan，thanks a lot.
Just a typo. The right one should be
1+ 1 + 1/2 + 1/3 + ... + 1/n.
Like E[0,1] = 2, alright ? |
L**********u
发帖数: 194 | 7 不用多加1吧。呵呵
【在 x*****i 的大作中提到】
: zan，thanks a lot.
: Just a typo. The right one should be
: 1+ 1 + 1/2 + 1/3 + ... + 1/n.
: Like E[0,1] = 2, alright ?
|
D********n
发帖数: 978 | 8 如果题目没有告诉你x_0 = 10^100次方的话，应该像你这样答(更确切的说，应该是1+1
/2+...+1/x_0).
但如果告诉了你x_0 = 10^100的话，他们希望的答案是数值解。100*log(10). 或者更精
确点， 100*log(10) + 0.577.
【在 M*******i 的大作中提到】
: 1 + 1/2 + ... + 1/n
|
