sc0ut's blog

Help in a class of problems on Expectation Value
By sc0ut, history, 5 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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$$$

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply