Probability problems

prob.md

Useful facts

• E - is linear operator, eg E(x + y) = Ex + Ey and we don't care about independence of the events
• If the problems is like find expectation of the maximum value in N tries you can use the following fact:

P(outcome == k) = P(outcome is at most k) - P(outcome is at most k-1)
P(outcome is at most k) = (k/m)^n

For instance, if the problem "You roll a 6-sided die twice. Find EV of the bigger of two scores.":

P(outcome = 3) = P(at most 3) - P(at most 2) = (3/6)^2 - (2/6)^2

Simple ones

1. pony and expectation. Taken from Errichto stream

Solution

      double res = 0.0;
    for (int k = 1; k <= m; ++k) {
        res += k * (pow(k/m, n) - pow((k-1)/m, n)); 
    }

2. dreamoon and wifi.

Solution

Combinatorial solution, one need to understand that P = Number of ways we get + from given number of ? / Total number of ways we can replace ? with something (2^m).

3. expectation while deleting tree nodes Think from each vertex position.

Find rand10 using rand7

    int rand10() {
        // rejection sampling algorithm
        //
        // idea is that we generate a random index in some table
        // so we increase dimension of the search space.
        // This index will have uniform distribution. So we can reject it 
        // if the value is greater than some c*10 (c = 4 in our case);
        // More formally, given M (=10) and N (=7) | M > N
        // find min x | N^x >= M
        // generate w = sum_i {N^i * (rndN - 1)}
        // find min c | N^x < (c+1)*M
        // result will be (w(mod N))+1
        int idx = 40; 
        while (idx >= 40) {
            int row = rand7() - 1;
            int col = rand7() - 1;
            idx = row * 7 + col;
        }
        return idx%10 + 1;
    }

A possible improvement in terms of number of calls to rand7() is instead of rejecting some numbers use them as one of the dimension in of the table on the next iteration.

Generate numbers with blacklist

uniformly generate numbers within the range [0, N) with given blacklist. lc

class Solution {
public:
    int n;
    unordered_map<int, int> black;
    
    random_device re;

    Solution(int N, vector<int>& blacklist)  : n(N) {
        // nlogn
        /*sort(blacklist.begin(), blacklist.end());
        for (int i = (int)blacklist.size() - 1; i >= 0; --i) {
            black.emplace(blacklist[i], n-1);
            --n;
        }*/
        // n
        for (int i : blacklist)
            black.emplace(i, -1);
        
        int m = n - black.size();
        for (int i : blacklist) {
            if (i < m) {
                while (black.count(n-1))
                    --n;
                black[i] = n - 1;
                --n;
            }
        }
        n = m;
    }
    
    int pick() {
        uniform_int_distribution<> ud(0, n-1); // generates in closed interval
        int i = ud(re);
        if (black.count(i))
            return black[i];
        return i;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(N, blacklist);
 * int param_1 = obj->pick();
 */

Random flip matrix

The solution using Fisher-Yates shuffle. Basically, we swap a random element with the last and store information about these swaps in the map. LC

class Solution {
    int n_0s;
    int rows, cols;
    unordered_map<int, int> swapped;
public:
    Solution(int n_rows, int n_cols) 
        : n_0s(n_rows*n_cols),
          rows(n_rows), cols(n_cols) {
    }
    
    vector<int> flip() {
        if (n_0s == 0) throw "aaa";
        int i = rand() % n_0s;
        int ri = i;
        --n_0s;
        auto it = swapped.find(i);
        if (it != swapped.end())
            i = it->second;
        
        swapped[ri] = swapped.count(n_0s) ? swapped[n_0s] : n_0s;
        return {i / cols, i % cols};
    }
    
    void reset() {
        n_0s = rows*cols;
        swapped.clear();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(n_rows, n_cols);
 * vector<int> param_1 = obj->flip();
 * obj->reset();
 */