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.