Exact probability for coin flip streaks
Your code looks good. It's a little hard to read, but given the context that is ok!
We can also see that if new_ending is never in needles then your code looks like it will run in \$O(f2^s)\$ time, where \$f\$ is flips and \$s\$ is streak.
Whilst I can see the code in if new_ending in needles: will reduce the the time your code takes to run.
For example when streak=2 it will allow your code to run in linear time, it's not going to help much on bigger numbers - the code will still tend to \$O(f2^s)\$.
We can see how you're performing this optimization in the following.
Since you are not searching the descendent of HH, TT, HTT, THH, etc. it cuts down how big the tree will get.

We can clearly see that tails is just the inverse of heads.
If we focus on heads and split the 'base' and 'tail' (the repeating results) we get the following:
     HH 1/2^2
H    TT 1/2^3
HT   HH 1/2^4
HTH  TT 1/2^5
HTHT HH 1/2^6

Whilst it's cool it runs in linear time, it's not really that interesting.
And so when streak=2 the total chance for \$f\$ flips is:
$$\Sigma_{n=2}^f \frac{2}{2^n}$$
However when we look at streak=3 we can see the start of a distinguishing pattern.
     HHH 1/2^3
H    TTT 1/2^4
HH   TTT 1/2^5
HT   HHH 1/2^5
HHT  HHH 1/2^6
HTH  TTT 1/2^6
HTT  HHH 1/2^6
HHTH TTT 1/2^7
HHTT HHH 1/2^7
HTHH TTT 1/2^7
HTHT HHH 1/2^7
HTTH TTT 1/2^7

If we take the count of each size then we get:
3: 1
4: 1
5: 2
6: 3
7: 5

This is cool because it's the start of the Fibonacci numbers.
I have verified that the first 30 values are the same.
And so we now can assume we have an equation for streak=3:
$$\Sigma_{n=3}^f \frac{2F(n-2)}{2^n}$$
Doing the same thing for streak=4,5,6,10 give the following sequences:

4 - Tribonacci
5 - Tetranacci
6 - Pentanacci
10 - Fibonacci 9-step

In all this is a pretty compelling pattern.
And so we can write an algorithm to run in \$O(fs)\$ time where \$f\$ is flips and \$s\$ is streaks.
import collections
import itertools
from fractions import Fraction


def fibonacci_nth(size):
    store = collections.deque([0] * size, size)
    store.append(1)
    while True:
        yield store[-1]
        store.append(sum(store))


def coin_chance(flips, streak):
    if streak &lt;= 0 or streak % 1:
        raise ValueError(&quot;streak must be a positive integer&quot;)
    if flips &lt; 0 or flips % 1:
        raise ValueError(&quot;flips must be a non-negative integer&quot;)
    if streak == 1:
        return Fraction(flips != 0, 1)
    sequence = (
        Fraction(2 * numerator, 2 ** exponent)
        for exponent, numerator in enumerate(fibonacci_nth(streak - 1), streak)
    )
    return sum(itertools.islice(sequence, flips - streak + 1))


# Code to get OEIS sequences
def funky_finder(depth, size):
    desired = (['H'] * size, ['T'] * size)
    stack = [iter(&quot;HT&quot;)]
    stack_value = []
    while stack:
        try:
            coin = next(stack[-1])
        except StopIteration:
            stack.pop()
            if stack_value:
                stack_value.pop()
            continue
        _stack_value = stack_value + [coin]
        if _stack_value[-size:] in desired:
            yield ''.join(_stack_value)
        elif len(stack) &lt; depth:
            stack_value.append(coin)
            stack.append(iter('HT'))


# I know, I know. But I was using this in a REPL!
size = 3; [i // 2 for i in sorted(collections.Counter(len(i) - size for i in funky_finder(20 + size, size)).values())]

&gt;&gt;&gt; 100 * fast(20, 6) / 2**20
23.687744140625
&gt;&gt;&gt; 100 * float(coin_chance(20, 6))
23.687744140625

&gt;&gt;&gt; 100 * fast(100, 6) / 2**100
80.68205487163246
&gt;&gt;&gt; 100 * float(coin_chance(100, 6))
80.68205487163246