Random bit flips on the 2x2 identity until singular
Question
Begin with the identity matrix. At each step, one of its four entries is chosen uniformly at random and toggled (a becomes and a becomes ). What is the expected number of steps until the matrix first has determinant ?
Short answer
. From , toggling a diagonal entry makes it singular at once; toggling an off-diagonal entry gives a unit triangular matrix such as . From there three of the four toggles produce a singular matrix and one returns to . So and , giving .
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 solutionLessons behind this question
- The Determinant: Defining Properties
- Conditional Probability, Total Probability, and Bayes' Rule
- Worked Examples — Probability Trees, Monty Hall, and Bayesian Updating
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