Your bullet points amount to saying that you're going to flip the coin until the number of heads exceeds the number of tails. Suppose that this happens on the $n$-th flip; then after $n-1$ flips you must have had equal numbers of heads and tails, so $n=2m+1$ for some $m$, you now have $m+1$ heads, and the ratio of heads to flips is $\frac{m+1}{2m+1}$. If $p_n$ is the probability of stopping after the $(2n+1)$-st flip, the expected ratio of heads to flips is $$\sum_{n\ge 0}\frac{p_n(n+1)}{2n+1}\;.$$ Thus, the first step is to determine the $p_n$.
Clearly $p_0=\frac12$: we stop after $1$ toss if and only if we get a head. If we stop after $2n+1$ tosses, where $n>0$, the last toss must be a head, half of the first $2n$ tosses must be heads, and for $k=1,2,\dots,2n$ the first $k$ tosses must not include more heads than tails. The problem of counting such sequences is well-known: these are Dyck words of length $2n$, and there are $C_n$ of them, where $$C_n=\frac1{n+1}\binom{2n}n$$ is the $n$-th Catalan number. Each of those $C_n$ sequences occurs with probability $\left(\frac12\right)^{2n}$, and each is followed by a head with probability $\frac12$, so $$p_n=C_n\left(\frac12\right)^{2n}\cdot\frac12\;,$$ and the expected ratio is $$\frac12\sum_{n\ge 0}C_n\left(\frac12\right)^{2n}\frac{n+1}{2n+1}=\frac12\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}n\;.$$
Very conveniently, the Taylor series for $\arcsin x$ is $$\arcsin x=\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}nx^{n+1}\;,$$ valid for $|x|\le 1$, so the expected ratio is $$\frac12\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}n=\frac12\arcsin 1\approx 0.7854\;.$$
Added: I should emphasize that this calculation applies only to the stated strategy. As others have noted, that strategy is known not to be optimal, though it's quite a good one, especially for being so simple.
"Show that the probability of a tie (we get the same number of heads) is the same as getting exactly 4 heads and 4 tails on 8 coin flips."
Let $H,T$ denote the number of heads and tails repectively flipped
by you in $4$ flips .
Let $H',T'$ denote the number of heads and tails respectively flipped
by your friend in $4$ flips.
Then the probability of a tie is $\Pr\left(H=H'\right)$.
But $T'$has the same distribution as $H'$ and there is independence, so we observe:
$\Pr\left(H=H'\right)=\Pr\left(H=T'\right)=\Pr\left(H=4-H'\right)=\Pr\left(H+H'=4\right)$
The last probability can be recognized as the probability of $4$
heads by $8$ flips (the flips of you and your friend taken together).
"Use this answer to calculate the probability of someone winning (getting more heads than the other person)."
Now we have:
- $\Pr\left(\text{tie}\right)=\Pr\left(H+H'=4\right)=2^{-8}\binom{8}{4}$.
- $1=\Pr\left(\text{you win}\right)+\Pr\left(\text{tie}\right)+\Pr\left(\text{friend wins}\right)$
- $\Pr\left(\text{you win}\right)=\Pr\left(\text{friend wins}\right)$
leading to: $$\Pr\left(\text{you win}\right)=\frac{1}{2}\left(1-2^{-8}\binom{8}{4}\right)$$
"Also, If I toss the coin 5 times, while my friend only tosses hers 4 times, calculate the probability that I will get strictly more heads than my friend."
If you toss $5$ times then think of it as a match1 as described above that is followed by an extra toss of you, and call the whole thing match2.
Now apply that:
$$\Pr\left(\text{you win match2}\right)=$$$$\Pr\left(\text{you win match1}\right)+\Pr\left(\text{match1 ends in a tie}\wedge\text{extra toss is a head}\right)=\Pr\left(\text{you win match1}\right)+\Pr\left(\text{match1 ends in a tie}\right)\Pr\left(\text{extra toss is a head}\right)=$$$$\frac{1}{2}\left(1-2^{-8}\binom{8}{4}\right)+2^{-8}\binom{8}{4}\times\frac12=\frac12$$
There is another (more elegant) route to this result.
Let $H,T$ denote the number of heads and tails repectively flipped
by you in $5$ flips .
Let $H',T'$ denote the number of heads and tails respectively flipped
by your friend in $4$ flips.
The probability of winning for you is $\Pr(H>H')$ and just as above we find:
$\Pr\left(H>H'\right)=\Pr\left(H>T'\right)=\Pr\left(H>4-H'\right)=\Pr\left(H+H'>4\right)$
The RHS is the probability that by $9$ flips there are more heads than tails. Symmetry then tells us that this equals $\frac12$.
Best Answer
To answer your question about the significance of restricted choice, and unpack that explanation, let's consider a simpler version of the example that Adam Sanjurjo and I shared with ESPN (we are following spaceisdarkgreen's lead here, but sticking with the approach in the ESPN article).
Imagine flipping a coin 3 times, and then selecting at random one of the flips that is immediately preceded by an $H$. You will select either flip 2 or flip 3, with equal chance. Let's say you selected flip 2 (analogous to flip 42). Well you know flip 1 is an $H$, because "preceded by $H$" was the selection rule. So you know you are in a sequence in which the outcomes of flip 1 and 2 are either $HH$, or $HT$. Why do we know $HT$ is more likely? Well, before flipping, the odds in favor of $HT$ relative to $HH$ were $1:1$, but the likelihood of selecting flip 2 (the flip we see) in world $HT$ is twice as likely when compared to world $HH$, because in world $HT$ you have to select flip 2 (i.e. $\mathbb{P}(flip\ 2|HT)=1$), whereas in world $HH$, you could selected flip 3 (i.e. $\mathbb{P}(flip\ 2|HH)=1/2$). So ex post, the odds in favor of $HT$ (relative to $HH$) double to $2:1$. With $2$ chances of $HT$ out of $3$ total chances, the probability of $HT$ becomes $2/3$, i.e. the probability flip 2 is a tails is $2/3$. This is Bayes rule, in odds form, which is simpler because it involves only multiplication. Dropping the verbiage, we have:
\begin{align} \frac{\mathbb{P}(HT|flip\ 2)}{\mathbb{P}(HH|flip\ 2)}& = \frac{\mathbb{P}(flip\ 2|HT)}{\mathbb{P}(flip\ 2|HH)}\times \frac{\mathbb{P}(HT)}{\mathbb{P}(HH)} \\ & = \frac{1}{1/2}\times\frac{\mathbb{P}(HT)}{\mathbb{P}(HH)} \\ & = 2\times\frac{1/2}{1/2} \\ & = 2 \end{align}
This gives the intuition behind the bias (for flips that are not the final flip). You are more likely to select the flip you selected, flip 2, in the world in which it is a $T$, because in that world you have to, whereas in the world in which it is an $H$, you are less restricted in your choice as there are more other flips to choose from -- you could have selected the next flip, flip 3.
Note that if flip $3$ were selected, than for the world in which flip 2 and 3 are $HT$, the likelihood of you selecting flip 3 is the same as in the world in which flip 2 and 3 are $HH$, because $HT$ doesn't exclude flip 4 as a possibility, becase there is no flip 4 (we can ignore the first flip here). That means the odds don't change.
So considering all three flips, we have found that $\mathbb{P}(HT|flip\ 2) =2/3$ and $\mathbb{P}(HT|flip\ 3) =1/2$. Because each flip is equally likely to be chosen we have
$$\mathbb{P}(T|\text{flip preceded by $H$})= 1/2\times 2/3 + 1/2\times 1/2 = 7/12$$
Note 1: The ESPN example is from this general interest write-up of ours---while more complicated with longer streak lengths, it gives intuition about strength of bias as streaks get longer. The simpler version presented here can be found in a paper by Adam Sanjurjo and myself, which connects restricted choice to the hot hand and other conditional probability problems. We borrowed one popular way of communicating the intuition for why, in the classic Monty Hall problem, the contestant should update his/her beliefs when a door is opened (see this StackExchange for the details).
Note 2: The response of spaceisdarkgreen is a good one, along with the extra details in the comments, but it doesn't answer Barry's specific question. Spaceisdarkgreen's focus is on the sampling distribution of the proportion and the calculation certainly demonstrates that the measure is biased, but it doesn't give an intuition for the direction of the bias.