2
$\begingroup$

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

            multiple IID binary sequences

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.

$\endgroup$
10
  • $\begingroup$ A nit: in step 4.2, you ought to find the first $1$ that appears strictly after $\hat{j}_1$ as you know there is not match at $\hat{j}_1$ That means step 1 doesn't need to know the result of step 4, it starts looking later in either case. Also the number of seeks and master seeks are equal, as they alternate. $\endgroup$ – Ross Millikan Jan 13 '16 at 2:30
  • $\begingroup$ seems the number of master seeks can be less than number of seeks when you have match and go via 4.1, which master seeks does not count. Also OP may have a little bit more clarification on $n$ is large (what requirement)? $S_i(j)$ are i.i.d. with probability $\mu_i$? Are those $\mu_i$ equal or distinct? $\endgroup$ – BGM Jan 13 '16 at 2:43
  • $\begingroup$ @BGM: It looks to me like 4.1 is also a master seek. We find a match and log it, then seek forward to the next 1 in $S_M$ $\endgroup$ – Ross Millikan Jan 13 '16 at 2:46
  • $\begingroup$ @BGM: the sequences are IID with 100% probability. The $\mu_i$ are the averages (i.e. the probability of any given element being a $1$). They're distinct. $\endgroup$ – COTO Jan 13 '16 at 2:46
  • $\begingroup$ @RossMillikan: There can be a match at $\hat{j}_1$. At that point we know there isn't a match at $j_1$, but $\hat{j}_1 > j_1$. Consider if $k = 1$, $S_M = \left\{ 1, 1, \ldots\right\}$, and $S_1 = \left\{ 0, 1, \ldots\right\}$ as an example. $\endgroup$ – COTO Jan 13 '16 at 2:49
1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Can it be that easy? I'll check it out in simulation. $\endgroup$ – COTO Jan 13 '16 at 3:29
  • $\begingroup$ I don't think this can be right. Consider when we have $k = 1$, $\mu_1 = \mu_M = 0.01$, and $n = 1000$. In this case, we expect the number of matches (from your formula) to be $n\mu_1\mu_M = 0.1$, but we perform $10$ seeks and $10$ master seeks with very high probability. $\endgroup$ – COTO Jan 13 '16 at 3:35
  • $\begingroup$ No, it isn't that easy. I thought a seek would get us to the next match. I"ll fix. $\endgroup$ – Ross Millikan Jan 13 '16 at 3:39
  • $\begingroup$ Actually in your example we perform on average five of each, as each one steps us forward $100$ spaces. My corrected version matches that. $\endgroup$ – Ross Millikan Jan 13 '16 at 3:46
  • $\begingroup$ I like the idea of computing the average step forward in both master and non-master sequences, and you're right about the average of $5$ seeks each. Computing the bitwise AND still doesn't make sense to me. For example, suppose we have $n = 1000$, $k = 20$ and $\mu_M = \mu_i = 0.1$ for all $i$. In this case, $p$ is effectively zero, giving us effectively zero seeks, but we only expect every step 2 to advance us by $\approx \frac{1}{\mu} = 10$, every step 4.1 to advance us by $10$, and every step 4.2 to advance us by $5$. As I see it, $n_{\rm seek}$ should be somewhere around $1000/15$. $\endgroup$ – COTO Jan 13 '16 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.