How many “seeks” are there in these binary sequences?

Question

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:

1. finds the index of the first $1$ in $S_M$; call this $j_1$
2. 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\}$
3. computes the maximum $\hat{j}_1 = \max\left\{\hat{j}_{1,i}\right\}$
4. compares $j_1$ and $\hat{j}_1$:
   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$
   2. 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$
5. 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.

Answer 1

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)$