exact value runtime for coin flip algorithm So I have an algorithm like this:
inc = 10 
for num in Array:
    if num == 1:
        return inc
    else: 
        inc += 1 
inc += 1 
return inc

I want to compute the expected runtime (exact value, not asymptotic) of this, based on the each element in the array having a 0.5 change to be a 1. 
I know that I can say Pr(ending at iteration i) = P(not i)^(i-1)(P(i) 
   = (1/2)^(i-1)(1/2)
But I don't know where to go from here to get an expected runtime for this algorithm on array of length k. 
 A: For notational simplicity, I'll define the size of the array as $A = |\text{Array}|$. As you note, the probability of finishing at step $i$ (for $i\in\{1, 2, \ldots, A-1\}$) is $(1/2)^i$. By summing these values, we see that the probability of finishing in steps 1 through $A-1$ is $1 - (1/2)^{A-1}$. As a result, the probability of finishing in the last step is $(1/2)^{A-1}$.
The expected number of iterations is therefore:
\begin{align*}
\mathbb{E}[\text{iterations}] &= \sum_{i=1}^{A-1} i(1/2)^{i} + A(1/2)^{A-1} \\
&= 2-(1/2)^{A-2} - (A-1)(1/2)^{A-1} + A(1/2)^{A-1} \\
&= 2-(1/2)^{A-1}
\end{align*}
The second step comes from the following identity (see https://math.stackexchange.com/questions/129302/finite-sum-sum-i-1n-frac-i-2i for a derivation):
$$
\sum_{i=1}^n it^i = t\frac{1-t^n}{(1-t)^2} - \frac{nt^{n+1}}{1-t}
$$
If we had an array of infinite length ($A=\infty$) we know from the negative binomial distribution that the expected number of iterations is 2, so it makes sense that the expected value is smaller than 2 but approaching that value as $A$ becomes large.

A less algebraic way to think about this is as follows: we know asymptotically ($A\rightarrow\infty$) that the expected number of iterations before a success is 2. We know that after $A$ iterations, $(1/2)^A$ proportion of the time we have never drawn a success (so if $A$ were larger we would continue drawing from the array). By the memorylessness of our process, the expected number of iterations before successes in these cases is still 2. As a result, the total expected number of iterations is the asymptotic estimate (2) minus the expected number of iterations we miss out on due to our finite array size ($2\times(1/2)^A = (1/2)^{A-1}$), yielding our final expected iteration count $2 - (1/2)^{A-1}$.
A: Let p = probability of array element i being a 1, independent and identical for all i from 1 to k. In your example, this is 0.5.
The probability that the ith element is a 1 = $(1-p)^{i-1}p$
If k were infinity, then the expected number of array elements until the 1st 1 would be $\sum_{i=1}^{\infty}{(1-p)^{i-1}pi} = \frac{1}{p}$.
However, there is a truncation and lump at $i = k$, so the number of array elements which are examined will be $k$ if none of the 1st $k-1$ elements are 1. The probability of that $= 1 - \sum_{i=1}^{k-1}{(1-p)^{i-1}p} = (1-p)^{k-1}$
So the expected number of array elements which will be examined, i.e., the expected running time, $= \sum_{i=1}^{k-1}{[(1-p)^{i-1}pi] + (1-p)^{k-1}k} = \frac{1 - (1-p)^k}{p}$
As you can see, this approaches $\frac{1}{p}$ as k increases toward $\infty$
Edit:l I didn't see josliber's answer until I posted mine. Out solutions are essentially the same, except that I did mine for a general $p$, not just $p = 0.5$.
