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.