Random OR
Today I’ll discuss a probability problem from CodeChef. The problem is as follows: we have an $N$-bit number $S$ which is initially $0$. At each step, we pick an $N$-bit number $X$ uniformly randomly and set $S := S \mid X$ (the symbol $\mid$ denotes bitwise-or). The process terminates when $S$ becomes $2^N - 1$ (that is, it is impossible to increase it any further because every bit is 1). What is the expected number of steps until termination? ...