Expected number of rounds for algorithm to terminate 
An algorithm terminates when the input size is less than $1$. For each iteration, there's $1/2$ chance that the input size gets halved, and $1/2$ chance it stays the same. What's the expected number of rounds to termination when the input is $n$?

I know that the intuitive answer of $\log_{4/3}n$ is not the correct answer, but I can't seem to convince myself why. Also, I was able to use Markov's inequality to upper bound the probability that the algorithm doesn't terminate after $k \log_{4/3}n$ rounds to be $\leq 1/n^{k-1}$, which is somewhat a good enough guarantee for runtime, but I'm just not sure the close form of the expectation, or if one exists, of the number of rounds.
 A: Given $n$ as a parameter, define a new parameter $ r\equiv \lceil \log_2 n \rceil$. For example, when $n = 8$ we have $r = 3$, and if $n = 10$ one will have seen at least $r = 4$ rounds at termination.
Denote the probability "the input size gets halved" as $p$. Here $p = 1/2$. Denote $X$ as the "total number of rounds when the algorithm terminates", then $X$ follows a Negative-Binomial distribution, with the following probability mass function:
$$\Pr\left\{ X = k\right\} = { k-1\choose r-1}p^r(1-p)^{k-r}~, \qquad k = r, r+1, r+2, \ldots$$
This is a standard discrete distribution, and it's expectation is well-known:
$$\mathbb{E}[X] = \frac{r}p = \frac{\lceil \log_2 n \rceil}p = 2\lceil \log_2 n \rceil$$
The above is the requested answer.
Below is a clarification in case of confusion.

There are at two common parametrizations of the Negative-Binomial distribution, besides simply switching $p \leftrightarrow q$ (and labeling which one as the "success"). Please be careful with the definition when reading materials from various sources.
Whenever you see the expectation expressed as $\mathbb{E}[Y] = r(1-p)/p$, it is parametrized as
$$Y \equiv \text{number of (rounds of) failure till the termination at the $r$ th success}$$
as opposed to here $X$ being the total number of rounds. Namely, $X = r+Y$ which means $$\mathbb{E}[X] = \mathbb{E}[r+Y] = r+\mathbb{E}[Y] = r+\frac{r(1-p)}p =\frac{r}p$$ that is necessarily consistent.
