How many "seeks" are there in these binary sequences? Consider a set of $k \geq 1$ random, IID binary sequences of length $n$, denoted $S_i,\;i = 1\ldots k$, and a "master sequence", also of length $n$, and denoted $S_M$ (see figure for $k = 4$).
            
Suppose $n$ is large and the probability of any given element in $S_i$ being a $1$ is given by the density $\mu_i$ (and $\mu_M$ in the case of the master sequence).
A subroutine is written to determine the set of indices $\left\{j\right\}$ such that both $S_M\left(j\right) = 1$ and $S_i\left(j\right) = 1\;\forall\, i = 1\ldots k$. In plain terms, we want to find the set of indices where all sequences have a $1$.
To do this, it:


*

*finds the index of the first $1$ in $S_M$; call this $j_1$

*polls all sequences $S_i$ simultaneously to determine the index of the first $1$ in each sequence that appears at or after $j_1$; call this set $\left\{\hat{j}_{1,i}\right\}$

*computes the maximum $\hat{j}_1 = \max\left\{\hat{j}_{1,i}\right\}$

*compares $j_1$ and $\hat{j}_1$:


*

*if $\hat{j}_1 = j_1$, a "match is found"; the subroutine returns to step 1, only now to find $j_2$, the index of the first $1$ that appears in $S_M$ strictly after $j_1$

*if $\hat{j}_1 > j_1$, no match is found; the subroutine returns to step 1, only now to find $j_2$, the index of the first $1$ that appears in $S_M$ at or after $\hat{j}_1$


*the subroutine continues through steps 1 thru 4 iteratively (finding $j_1,j_2,j_3,\ldots$), and terminates when either step 2 or step 4 can no longer find any $1$s


Let step 2 be called a "seek" and let step 4.2 (not 4.1) be called a "master seek". Let $n_{\rm seek}$ (a random variable) be the number of seeks run by the subroutine, and let $n_{\rm ms}$ be the number of master seeks run by the subroutine.
My question is this: Given a set of densities $\mu = \left\{\mu_i,\mu_M\right\}$, is there a way to compactly compute two functions, $\xi_{\rm seek}$ and $\xi_{\rm ms}$ such that $$E\left[n_{\rm seek}\right] \approx n\xi_{\rm seek}\left(\mu\right)$$ and $$E\left[n_{\rm ms}\right] \approx n\xi_{\rm ms}\left(\mu\right)$$ for any $k \geq 1$?
By "compactly", I mean with a few hundred multiplications, additions, branches, etc. and not involving numerical integration or large lookup tables.
By "approximately" ($\approx$), I mean within $\pm 30\%$ of the actual value.
Any assistance would be greatly appreciated.
 A: The key is how far we step on average on a normal seek.  I will do the special case where all the non-master sequences have the same density $\mu$  We want to know how many places we have to look before all the sequences have a $1$.  A heuristic is that you start with $n$ sequences.  After one cell you have $(1-\mu)n$ that have not seen a $1$.  After two cells you have $(1-\mu)^2n$ that have not seen a $1$.  We keep going like this until we have just one sequence that has not seen a $1$.  That will be after $k$ cells where $(1-\mu)^k=\frac 1n, k=\frac {-\log n}{\log(1-\mu)}$ then we need to wait $\frac 1\mu$ for the last one to get a $1$.  Each normal seek therefore advances us $L=\frac {-\log n}{\log(1-\mu)}+\frac 1\mu$  
Having done a normal seek, with probability $\mu_M$ we have a match and do not advance further.  Otherwise we do a master seek and advance $\frac 1{\mu_M}$.  Each normal seek plus the following master seek advance us $LL=\frac {-\log n}{\log(1-\mu)}+\frac 1\mu+\frac{1-\mu_M}{\mu_M}$.  The expected number of normal seeks is $\frac n{LL}$ and of master seeks is $\frac n{LL}(1-\mu_M)$
