Let $A_n$ be an event whose success probability $P(A_n)$ depends on the size, $n\in \mathbb{N}$, of a given sample.
Let $d$ be a fixed positive integer.
For the problem I am working on I can assume a sequential sample and derive – via a geometric argument – the following recurrence relation:
$$ P(A_{n+1}) = P(A_{n+1}|A_n)P(A_{n}) + P(A_{n+1}|A_{n}^c)P(A_{n}^c)\\
= P(A_{n}) + 2^{-n}(1 – P(A_{n}))$$
with the initial conditions $P(A_d) =0$, $P(A_{d+1}) = 2^{-d}$.
I am interested in whether it is possible to obtain a simple closed form expression for $P(A_n) = P(A_{d+k})$?
Best Answer
Let $a_{n+1} = \log(1 - \Pr(A_{n+1}))$ for $n=d, d+1, \ldots.$ In these terms the recurrence reads
$$\begin{aligned} a_{n+1} &= \log(1 - [\Pr(A_n) + 2^{-n}(1 - \Pr(A_n))])\\ &= \log((1-2^{-n})(1 - \Pr(A_n))\\ &= \log(1 - 2^{-n}) + \log(1-\Pr(A_n)) \\ &= \log(1 - 2^{-n}) + a_n \end{aligned}$$
with initial condition $a_{d+1} = \log(1 - 2^{-d}).$
An easy induction now gives
$$\begin{aligned} a_{n+d} &= \sum_{i=1}^{n-1} \log\left(1 - 2^{-(d+i)}\right) + a_{d+1}\\ &= \sum_{i=0}^{n-1} \log\left(1 - 2^{-(d+i)}\right). \end{aligned}$$
Returning to the original formulation,
$$\Pr(A_{n+d}) = 1 - \exp(a_{n+d}) = 1 - \prod_{i=0}^{n-1} \left(1 - q^{-(d+i)}\right)= 1 - \prod_{k=d}^{n+d-1} \left(1 - q^{-k}\right)$$
where $q=1/2.$ Using the conventional notation for q-numbers
$$[k]_q = \frac{1 - q^k}{1-q} = 1 + q + q^2+ \cdots + q^{k-1}$$
we may write this as
where the $q$ analogs to the Binomial coefficients and factorials are the Gaussian Binomial coefficients
$$\binom{m}{r}_q = \frac{[m]_q [m-1]_q \cdots [m-r+1]_q}{[r]_q [r-1]_q \cdots [2]_q [1]_q}$$
and their related factorials
$$[k]_q! = [k]_q [k-1]_q \cdots [2]_q [1]_q.$$
I believe this won't simplify further, but clearly the product converges rapidly and therefore is straightforward to compute and analyze. In particular, these $q$-numbers have combinatorial interpretations (closely related to sampling without replacement) and enjoy many beautiful mathematical properties that can help with that analysis.