1) Due to an obiwan error, that bound should be $n+2$ (since we don't start culling until step 2) 2) Numerically, the expected amount of time it takes to go from 2 to 1 relevant things appears to be about 3.3 steps (3.279 after taking into account results of no more than 9 steps). This is probably a good way to sanity-test my analysis against your Monte Carlo guy.
Re: almost...
1) Due to an obiwan error, that bound should be $n+2$ (since we don't start culling until step 2)
2) Numerically, the expected amount of time it takes to go from 2 to 1 relevant things appears to be about 3.3 steps (3.279 after taking into account results of no more than 9 steps). This is probably a good way to sanity-test my analysis against your Monte Carlo guy.