Expected running time

Question

Suppose A = A[1] . . .A[n] of length n (where A[i] is either 0 or 1). We want to determine if at least half the elements in A are 1’s.

HalfOnes( A ):
numOnes = 0
numZeros = 0
for i = 1 to n do
   if A[i] = 1 then
      numOnes++
      if numOnes >= n/2 then return true
   else
      numZeros++
      if numZeros > n/2 then return false

Question: What is the expected running time of the algorithm, assuming a uniform distribution?

Answer 1

I don’t have a closed form, but I was able to derive a recurrence.

Let $B_n$ be the set of binary strings of length $n$. For $\beta=b_1^\beta\ldots b_n^\beta\in B_n$ let

$$c_n(\beta)=\min\left\{k\in[n]:\sum_{i=1}^kb_i^\beta\ge\frac{n}2\text{ or }\sum_{i=1}^k\overline{b_i^\beta}>\frac{n}2\right\}\;,$$

where $\overline b=1-b$. It’s convenient to distinguish odd from even $n$:

$$c_{2n}(\beta)=\min\left\{k\in[2n]:\sum_{i=1}^kb_i^\beta\ge n\text{ or }\sum_{i=1}^k\overline{b_i^\beta}\ge n+1\right\}\;,$$

and

$$c_{2n+1}(\beta)=\min\left\{k\in[2n+1]:\sum_{i=1}^kb_i^\beta\ge n+1\text{ or }\sum_{i=1}^k\overline{b_i^\beta}\ge n+1\right\}\;.$$

We want $e_n$, the expected value of $c_n(\beta)$ when $\beta$ is chosen from $B_n$ with the uniform distribution, which is given by

$$e_n=\frac1{2^n}\sum_{\beta\in B_n}c_n(\beta)\;,$$

so we’re interested in $$s(n)=\sum_{\beta\in B_n}c_n(\beta)\;.$$

It will be useful also to have

$$s_i(n)=\sum\{c_n(\beta):b_{c_n(\beta)}^\beta=i\}$$

for $i=0,1$; clearly $s(n)=s_0(n)+s_1(n)$.

If $B_n(k)=\{\beta\in B_n:c_n(\beta)=k\}$, and $B_n^i(k)=\{\beta\in B_n(k):b_k^\beta=i\}$ for $i=0,1$, then

$$\begin{align*} |B_{2n}^0(k)|&=\binom{k-1}n2^{2n-k}\;,\\\\ |B_{2n}^1(k)|&=\binom{k-1}{n-1}2^{2n-k}\;,\\\\ |B_{2n+1}^0(k)|&=\binom{k-1}n2^{2n+1-k}=|B_{2n+1}^1(k)|\;,\\\\ |B_{2n}(k)|&=\binom{k}n2^{2n-k}\;,\text{ and}\\\\ |B_{2n+1}(k)|&=\binom{k-1}n2^{2n+2-k}\;. \end{align*}$$

so

$$\begin{align*} s_0(2n)&=\sum_{k=n}^{2n}k\binom{k-1}n2^{2n-k}\;,\\\\ s_1(2n)&=\sum_{k=n}^{2n}k\binom{k-1}{n-1}2^{2n-k}\;,\\\\ s_0(2n+1)&=\sum_{k=n+1}^{2n+1}k\binom{k-1}n2^{2n+1-k}=s_1(2n+1)\;,\\\\ s(2n)&=\sum_{k=n}^{2n}k\binom{k}n2^{2n-k}\;,\text{ and}\\\\ s(2n+1)&=\sum_{k=n+1}^{2n+1}k\binom{k-1}n2^{2n+2-k}\\\\ &=\sum_{k=n}^{2n}(k+1)\binom{k}n2^{2n+1-k}\\\\ &=\sum_{k=n}^{2n}k\binom{k}n2^{2n+1-k}+\sum_{k=n}^{2n}\binom{k}n2^{2n+1-k}\\\\ &=2s(2n)+2\sum_{k=n}^{2n}\binom{k}n2^{2n-k}\\\\ &=2s(2n)+2\sum_{k=n}^{2n}|B_{2n}(k)|\\\\ &=2s(2n)+2^{2n+1}\;. \end{align*}$$

It follows immediately that $$e_{2n+1}=\frac{s(2n+1)}{2^{2n+1}}=\frac{2s(2n)+2^{2n+1}}{2^{2n+1}}=\frac{s(2n)}{2^{2n}}+1=e_{2n}+1\;.$$

Since $s_0(2n+1)=s_1(2n+1)=\frac12s(2n+1)$, we also have $$s_0(2n+1)=s_0(2n)+s_1(2n)+2^{2n}\;.$$

Clearly $s_0(2n+1)=2s_0(2n)+(2n+1)\binom{2n}n$, so

$$s_0(2n)+(2n+1)\binom{2n}n=s_1(2n)+2^{2n}\;,$$

and hence

$$s_0(2n)=s_1(2n)+2^{2n}-(2n+1)\binom{2n}n\;.$$

Moreover,

$$s_1(2n)=2s_1(2n-1)+2n\binom{2n-1}{n-1}=2s_1(2n-1)+2n\binom{2n-1}n\;,$$

so

$$\begin{align*} s_0(2n)&=2s_1(2n-1)+2n\binom{2n-1}n+2^{2n}-(2n+1)\binom{2n}n\\\\ &=2s_0(2n-1)+2^{2n}+2n\binom{2n-1}n-(2n+1)\left(\binom{2n-1}n+\binom{2n-1}{n-1}\right)\\\\ &=2s_0(2n-1)+2^{2n}-\binom{2n-1}n-(2n+1)\binom{2n-1}n\\\\ &=2s_0(2n-1)+2^{2n}-(2n+2)\binom{2n-1}n\;, \end{align*}$$

and

$$\begin{align*} s(2n)&=2\left(s(2n-1)-\binom{2n-1}n\right)+2^{2n}\\\\ &=2s(2n-1)-2\binom{2n-1}{n-1}+2^{2n}\\\\ &=2s(2n-1)-\binom{2n}n+2^{2n}\;. \end{align*}$$

Finally, $$e_{2n}=\frac{s(2n)}{2^{2n}}=\frac{2s(2n-1)}{2^{2n}}-\frac1{2^{2n}}\binom{2n}n+1=e_{2n-1}+1-\frac1{2^{2n}}\binom{2n}n\;.$$

To summarize,

$$\left\{\begin{align*} e_{2n}&=e_{2n-1}+1-\frac1{2^{2n}}\binom{2n}n\\ e_{2n+1}&=e_{2n}+1\;. \end{align*}\right.$$

Of course $e_1=1$.

It’s an easy consequence of Stirling’s approximation that $$\binom{2n}n\sim\frac{4^n}{\sqrt{\pi n}}\;,$$ so $$\frac1{2^{2n}}\binom{2n}n\sim\frac1{\sqrt{\pi n}}$$

The approximation isn’t too bad: already for $n=10$ the lefthand side is about $0.1762$ and the righthand side about $0.1784$. Thus, for even moderately large $n$ we have

$$e_{2n}\approx e_{2n-1}+1-\frac1{\sqrt{\pi n}}\;.$$