Блог пользователя sc0ut

Help in a class of problems on Expectation Value
Автор sc0ut, история, 5 лет назад, По-английски

Sometimes, to find $$$E(X)$$$, where $$$X = f(X_1,X_2,...X_n)$$$ and $$$X_1,X_2..$$$ are R.Vs, we may need to brute force on all possibilities. This may be done easily by a bitmask, but I face the trouble to calculate the final answer. In virtually every problem, we are needed to report $$$(PQ^{-1})\%mod$$$, which seems undoable to me (in case the probabilities are also fractions). Is there any work-around for this? Please share tips related to not only this, but in general for other $$$E(X)$$$ calculations.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

$$$PQ^{-1} = PQ^{mod - 2}$$$ for prime mod

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Sorry for not being able to state my problem correctly. I was aware of the fact in your comment, I wanted to know how to efficiently maintain the numerators and denominators of the expression(in case of $$$n$$$ $$$=$$$ 3)

    $$$ p_1p_2p_3 * x + (1 - p_1)p_2p_3 * y + p_1(1 - p_2)p_3 * z ...$$$

    Also, the final expression $$$p/q$$$ has to be of the lowest form, so taking $$$mod$$$ at every stage in numerator and denominator will not guarantee the final fraction having $$$gcd(p,q) = 1$$$

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      I'm fairly certain you can just apply the formula $$$\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}$$$, and if you multiply the appropriate numerators and denominators it will always reduce to the same value as if you had done it perfectly with the irreducible fractions.

      For example, in modulo 1e9 + 7:

      2 times mod inv 3 is 666666672

      6 times mod inv 9 is 666666672

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Let's say $$$gcd(p, q) = d$$$, that is $$$p = dx, q = dy$$$, where $$$x$$$ and $$$y$$$ are coprime.

      Then too $$$pq^{-1} = dx (dy)^{ - 1} = x dd^{-1}y^{-1} = xy^{-1}$$$ modulo prime.

      Thus, you can take modulo at each stage without worrying if $$$p, q$$$ are coprime or not.

      → Ответить