I have a biased coin which comes up heads with probability $p$. I know the value of $p$, but I want to falsely claim that the coin has a different probability of heads, $q$, where $q > p$.
To support my claim I decide to produce some false evidence: I flip the coin repeatedly and record the fraction of flips that were heads, and keep flipping until the fraction is at least $q$. I also make sure I flip the coin at least $100$ times before stopping (so I flip $100$ times initially, then I keep flipping until the fraction of heads so far is at least $q$). I report the total number of flips, and the fraction of heads, as evidence that the coin has probability of heads (approximately) $q$.
In terms of $p$ and $q$, what is the probability that I can successfully produce evidence for my false claim? (I.e. what is the probability that after $100$ initial flips, my repeated flipping will eventually terminate with a fraction above $q$ in a finite amount of time?)
Given that I do successfully produce the false evidence, what is the expected number of flips required?
I thought of this question out of curiosity, when pondering about how we can soundly use data to infer unknown probabilities.
For Question 1, the probability is positive: in fact, it's at least $p^{100}$ since the first $100$ flips could all be heads. It's less clear if the probability is $< 1$, but I think it is. The question can be phrased as a random walk in two dimensions, where the false evidence is produced if the random walk enters into the region of points $(x,y)$ where $y > q \cdot (x + y) \text{ and } x + y \ge 100$.
For Question 2, probably thinking about it as a random walk is also the first step.
For either question, I would be happy with upper/lower bounds or approximations, if an exact answer is not easy.
A few thoughts on your question 1
The number $S_n$ of heads after $n$ flips follows a standard binomial distribution with parameters $n$ and $p$. Alternatively, the sequence $(S_n)$ is a Bernoulli process.
A larger lower bound
We can use this to somewhat sharpen the lower bound of $p^{100}$ you give in your question. Namely, while getting 100 successes in the first 100 trials (let's set $n_0=100$) is sufficient, so would be getting only $\lceil qn_0\rceil$. The probability for this is the upper tail probability of our binomial distribution,
$$ P(S_{n_0}\geq qn_0) = \sum_{k=\lceil qn_0\rceil}^{n_0}{n\choose k}p^k(1-p)^{n-k}. $$
Now, Wikipedia tells us (quoting chapter 11 of Elements of Information Theory by Cover and Thomas, which I admittedly haven't looked at) that
$$P(S_n\geq k) \geq \frac{1}{n+1}\exp\bigg(-nD\Big(\frac{k}{n}\,||\,p\Big)\bigg) \text{ if }p<\frac{k}{n}<1, $$ where $$ D\Big(\frac{k}{n}\,||\,p\Big) = \frac{k}{n}\ln\frac{k}{np}+\Big(1-\frac{k}{n}\Big)\ln\frac{1-\frac{k}{n}}{1-p} $$ is the relative entropy between the $\frac{k}{n}$-coin and the $p$-coin. We note that with $k=\lceil qn_0\rceil$ with $q>p$, the condition $p<\frac{k}{n_0}=\frac{\lceil qn_0\rceil}{n_0}<1$ is satisfied, so we get a lower bound for your probability (resulting solely from the probability of having enough successes in the inital $n_0$ flips of)
$$ \begin{align*} &\frac{1}{n_0+1}\exp\bigg(-n_0D\Big(\frac{\lceil qn_0\rceil}{n_0}\,||\,p\Big)\bigg) \\ =& \frac{1}{n_0+1}\exp\bigg(-n_0\frac{\lceil qn_0\rceil}{n_0}\ln\frac{\lceil qn_0\rceil}{n_0p}-n_0\Big(1-\frac{\lceil qn_0\rceil}{n_0}\Big)\ln\frac{1-\frac{\lceil qn_0\rceil}{n_0}}{1-p}\bigg) \\ =& \frac{1}{n_0+1}\bigg(\frac{\lceil qn_0\rceil}{n_0p}\bigg)^{-\lceil qn_0\rceil} \bigg(\frac{1-\frac{\lceil qn_0\rceil}{n_0}}{1-p}\bigg)^{\lceil qn_0\rceil-n_0}, \end{align*} $$ which should be larger than $p^{100}$ - for instance, if $p=0.4$ and $q=0.5$, then $p^{100}\approx\exp(-91.6)\approx 1.6\times 10^{-40}$, while this expression comes out to about $\exp(-6.7)\approx 0.0013$.
An upper bound
Next, as noted in a comment, Hoeffding's inequality may be helpful. We have $E(S_n)=pn$, and Hoeffding's inequality yields (see the "Proof" section for the statement) that $$ P(S_n>qn) = P(S_n-E(S_n)\geq qn-pn) \leq\exp\big(-2n(q-p)^2\big). $$
As you write, we can use the union bound to get a very crude bound on the probability we are interested in: $$ \begin{align*} & P(\exists n\geq n_0\colon S_n\geq qn) \\ \leq & \sum_{n=n_0}^\infty P(S_n>qn) \text{ by the union bound} \\ \leq & \sum_{n=n_0}^\infty \exp\big(-2n(q-p)^2\big) \text{ by Hoeffding, above} \\ = & \sum_{n=n_0}^\infty \Big(\underbrace{\exp\big(-2(q-p)^2\big)}_{=:x}\Big)^n \\ = & \frac{x^{n_0}}{1-x}\text{ as a geometric series} \\ = & \frac{\exp\big(-2n_0(q-p)^2\big)}{1-\exp\big(-2(q-p)^2\big)}. \end{align*} $$
As an example, for $p=0.4$ and $q=0.5$ as above, this comes to about $6.83$. Hum. It gets more useful for larger $q$, e.g., $q=0.6$ yields a bound of about $0.0044$.
Finally, here is a little simulation. I simulated 100,000 trajectories of our Bernoulli process with $p=0.4$ and calculated the running success probabilities $(\frac{S_n}{n})$. Below, I plot 10 random trajectories, as well as the trajectory of the maximum of our 100,000 running probabilities. The initial $n_0=100$ steps are plotted in gray. I also included a horizontal line at $q=0.5$ in red. It seems like the initial steps dominate the question. (Incidentally, out of our 100,000 trajectories, 2,682 had a quotient of $\frac{S_{n_0}}{n_0}\geq 0.5$ after the initial $n_0=100$ steps, where the bound above would have predicted at least 130.)
R code: