Mathematical idea regarding solving "Not So Random" question asked in Google APAC Test 2015 Round E

I am trying to solve the Problem C titled "Not So Random" asked in Round E of Google APAC 2015 test (Link: https://code.google.com/codejam/contest/8264486/dashboard#s=p2). Following is the question:

My initial idea was to try to formulate a recursive equation for calculating the Expectation of a bit $$i$$ produced by an $$n^{th}$$ machine (denoted by $$E[f^{n}(i)]$$) given $$f^{n-1}(i)$$ and $$k(i)$$ ($$i^{th}$$ bit of $$k$$). The following is an equation I came up with (I am not completely sure about the correctness):

$$E[f^{n}(i)] = \frac{(B+C)}{100}*(f^{n-1}(i)\oplus k(i)) + \frac{(A+B)}{100}*(\neg (f^{n-1}(i) \oplus k(i))\ \ominus \ k(i))$$

, where $$\oplus$$ denotes the bitwise $$XOR$$ operation and $$\ominus$$ denotes the bitwise $$AND$$ operation.

The thing is I do not how to proceed from there. Some solutions to this are available online: http://massivealgorithms.blogspot.com/2016/07/not-so-random-round-e-apac-test-of.html and https://stackoverflow.com/questions/39430741/logic-behind-codejam-apac-practice-round-not-so-random, but they do not give a properly explained mathematical answer.

(I do not need the code -- I can type it down on my own. Some proper mathematical idea and pointers in the right direction will help)

• It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $X\wedge K$, $X\vee K$, $X\oplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– user856
Commented Nov 12, 2018 at 15:30
• @Rahul Thanks! Your idea was correct :) Commented Nov 15, 2018 at 14:55

Mathematical ideas

1. Linearity of expectation: for any coefficients $$a$$ and $$b$$, and any random variables $$X$$ and $$Y$$, we have $$\mathbb{E}[aX+bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]$$. This allows us to look at each bit separately, rather than the numbers as a whole, which greatly reduces the complexity.

2. (?) Markov Chains: The Markov chains used in this problem are so simple that no formal knowledge about them is required (and I don't actually use Markov chains terminology in the explanation below, except in a side note). However, they are very useful in more complex similar problems. A Markov Chain is a collection of states together with probabilities to transition from one state to another.

Solution

You can start by considering only one bit, say bit $$k$$. Let $$X_k$$ be the $$k^{\text{th}}$$ bit of $$x$$. Let $$Y$$ be the output, and $$Y_k$$ is its $$k^{\text{th}}$$ bit. Define $$K_k$$ similarly. Here, I index the lowest bit ($$0^{\text{th}}$$ power of 2) by 0, and the highest by $$l$$. If $$X$$ and $$K$$ are not the same length, we can add 0s in front.

Let's compute $$\mathbb{P}[Y_k=1]$$ for each $$k$$. Note that this gives us the expected value for this bit: $$\mathbb{E}[Y_k] = 1\mathbb{P}[Y_k=1] + 0\mathbb{P}[Y_k=0]$$

We'll need the probabilities of what we'll get out if either 1 or 0 is passed to the RGN in $$k^{\text{th}}$$ position. For this, we define a 2 by 2 matrix T:

Let $$T_{i,j}$$ be the probability that probability that, if we get input bit i in the $$k^{\text{th}}$$ position in our RNG, and $$K_k=j$$, we'll get 1 in the output.

This can be precomputed for all $$i$$, $$j$$. For example, $$T_{0,1} = \frac{A + C}{100}$$, as both XOR and OR with produce 1 given inputs 0 and 1.

Let $$P_{k, n}$$ be the probability that the $$k^{\text{th}}$$ bit is 1 after it's been passed through $$n$$ RNGs. Clearly, $$P_{k, 0} = X_k$$ (this is either 0 or 1, depending on our starting bit).

Each next RNG changes that probability as follows:

$$P_{k, d + 1} = P_{k, d}T_{1,K_k} + (1 - P_{k, d})T_{0, K_k}$$

($$1 - P_{k, d}$$ is the probability to have a $$0$$)

This can be computed using dynamic programming.

Note that the distribution of the output bit depends only on the input bit and the corresponding bit of $$K$$, so there are only four possibilities for it. That is, there's no need to repeat the whole computation for each bit, but we can do it once for each of the four possibilities.

Side note: This is where we have the Markov chains. We have two states, 0 and 1. We start on the state given by $$X_k$$. We have two possible transition matrices (they're not T, but can be computed from it), and which one we use depends on $$K_k$$. We're interested in the probability to be in state 1 after $$N$$ transitions.

Let's call the output Y. We know the probability that $$Y_k=1$$, namely $$P_{k, n}$$. The expectation of a binary variable is the probability to get 1, so $$\mathbb{E}[Y_k] = P_{k,n}$$.

Finally, we can use the linearity of expectation to compute the expectation of Y:

$$\mathbb{E}[Y] = \mathbb{E}[Y_0 + 2Y_1 + 2^2Y_2 + \dots + 2^lY_l] = \\ = \mathbb{E}[Y_0] + 2\mathbb{E}[Y_1] + \dots + 2^l \mathbb{E}[Y_l] = \\ = P_{0,n} + 2P_{1,n} + 2^2P_{2,n} + \dots + 2^lP_{l,n}$$

• Thanks a lot! (also for pointing out about Markov chains -- this is new to me). You explained it beautifully :) ! I am not sure how I could not figure it out earlier. Awarded with 50 bounty :). Commented Nov 15, 2018 at 14:52