Skip to content

Random bit flips on the 2x2 identity until singular

Question

Begin with the 2×22\times 2 identity matrix. At each step, one of its four entries is chosen uniformly at random and toggled (a 11 becomes 00 and a 00 becomes 11). What is the expected number of steps until the matrix first has determinant 00?

Short answer

127\tfrac{12}{7}. From II, toggling a diagonal entry makes it singular at once; toggling an off-diagonal entry gives a unit triangular matrix such as (1101)\left(\begin{smallmatrix}1&1\\0&1\end{smallmatrix}\right). From there three of the four toggles produce a singular matrix and one returns to II. So EI=1+12ETE_I=1+\tfrac12E_T and ET=1+14EIE_T=1+\tfrac14E_I, giving EI=127E_I=\tfrac{12}{7}.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free