|
|
13 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ans: 31.513956103964 You only have four things to pick from, so you can calculate each step explicitly. This equation follows the notation in the article: T is the time to collect all of the items, and ti be the time to collect the i-th item after i−1 items have been collected. E(T)=E(t1)+E(t2)+E(t3)+E(t4)=p1−1+p2−1+p3−1+p4−1. The probability p1 of picking a new one if you have picked none yet is 1. The probability p2 of picking a new one if you have picked one depends on which one you picked first. Let's call the items A through D and the probabilities of picking each item if they're all in the box pa through pd. Then p2 would be pa(pb+pc+pd)+pb(pc+pd+pa)+pc(pd+pa+pb)+pd(pa+pb+pc). The above expression is the probability of picking a new one given that A had been picked already, plus the probability of picking a new one given that B had been picked already, and so on. The expression for p3 will have six terms in the sum; one of these will be papb(pc+pd). The expression for p4 will have four terms in the sum (actually, it's the same term four times!) [DELETED] Edited by author 17.09.2022 01:09 When probability from 0~9 different, how to calculate the expected number??? Thank very much!! I have used Dynamic Programming. To do this, you need to store 2^10 states ... I have used Dynamic Programming to get probability. But don't know how to get EP. If probability is equal it's a coupon collector's problem? Please, explane this in more details. I calculated probability of appearance of digit 0~9 as last digit and for first sample: 0: 0.925... 1: 0.009... 2~9: 0.008... and expectation: 344.0203... However, if i set probability from 0~9: all 0.1 the expectation becomes correct: 29.2896825397 I probably am missing something or misinterpreted something. Please, help me someone. Many many thanks in advance. [AC] [Code Deleted] Edited by author 01.11.2011 10:19 Edited by author 01.11.2011 13:10 Edited by author 01.11.2011 13:25 When you have two modulo operations, you cannot just apply each of them on each step. You can take everything modulo 11 on each step, but only the last result may be taken modulo 10. If you fix it, you will get equal probabilities. P.S. hide your code - let other people solve this problem themselves. |
|
|