# Markov Processes – Determining the Closed Form for a Markov Chain with Transition Probabilities Dependent on $n$

markov-processprobability

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})$$?

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

$$\Pr(A_{n+d}) = 1 - 2^{-n}\prod_{k=d}^{n+d-1} [k]_{1/2} = 1 - 2^{-n}\binom{n+d-1}{n}_{1/2}\,[n]_{1/2}!$$

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.