Let $B_{1},...,B_{n}\sim \mathrm{Bernoulli}(p)$ be independent random variables. \begin{alignat}{1} T_{0}&:=0,\\ T_{1}&:= \min\big\{k \geq 1 | B_{k}=1 \big\},\\ T_{2}&:=\min\big\{k > T_{1} | B_{k}=1 \big\},\\ &\vdots\\ T_{n}&:=\min\big\{k > T_{n-1} | B_{k}=1 \big\}. \end{alignat}
How to prove that increments $T_{1}-T_{0},T_{2}-T_{1},...,T_{n}-T_{n-1}$ are independent?
This task was in my uni exercise sheet. To be honest I have real doubts about whether it is true because for me intuitively at least $T_{2}-T_{1}$ and $T_{1}$ have to be dependent. I don't understand how these two variables can be independent. I've been staring at this exercise for more than 2 hour and still cannot understand the trick. If you do, I would really appreciate any help. By the way, I know how to prove that $T_{n}\sim\mathrm{NBinom}(n,p)$. And because every increment has geometric distribution with parameter $p$ the fact that sum of increments equals $T_{n}$ must lead us to a thought that they are independent according to properties of negative binomial distribution. But I just don't get it. How can $T_1$ have no influence on $T_{2}-T_{1}$?
Hi you have to rewrite the event to get it in a way that exhibit the independence with what you know is independent at hand, and the only independent variables at disposal are the $B_i$s.
$T_1-T_0=T_1$ so it's trivialy independent of $T_0$ that is constant(any random variable is independent of a constant variable).
Now $T_2-T_1$, let's fix $T_1 = k$. The trial of $B_{k+1}$ is independent of the k-first trials, so that the event $B_{k+1}=1$ is independent of the $k$ firsts Bernoullis, so $T_2-T_1= 1$ is independent of $T_1=k$ for any $k$. But the same is true for $B_{k+1}=0,B_{k+2}=1$, and any $B_{k+1}=0,...,B_{n-1}=0,B_{n}=1$, (and even to be complete $B_{k+1}=0,...,B_{n-1}=0,B_{n}=0$ which means by convention that $T_2-T_1=\infty$).
This shows independence of $T_2-T_1$ with $T_1$.
As you can reiterate the reasoning you show for that $T_{k}-T_{k-1}$ is independent of $T_0,T_{1}-T_{0},T_{2}-T_{1},...,T_{k-1}-T_{k-2}$ and you're done when $k=n$.
The intuitive idea is that everything is like it's starting afresh from $T_0$ when the Bernoulli equals 1. It is a very deep property that gives rise to the Markov property for stochastic processes.
(late) Addenda: I will try to answer your first comment. So let me try to rephrase it with my own words :you say if $T_2-T_1=k$ and $T_1=n$ and those events are independent then : $\mathbb P(T_2=n+k;T_1=n)=\mathbb P(T_2-T_1=k;T_1=n)=\mathbb P(T_2-T_1=k)\mathbb P(T_1=n) $ so that from this formula $\mathbb P(T_2-T_1=k)$ appears to depend on $n$ (i.e. on $T_1$'s value) as it's equal to $\frac{\mathbb P(T_2-T_1=k;T_1=n)}{\mathbb P(T_1=n)}$, so there must be a problem. The thing is although $n$ appears in the formula above in fact the formula, this formula is true for all $n$ and this is what the problem is about in fact. $T_2-T_1$ has the same law whatever the value of $T_1$ takes. So let's check that out. Here is the sequence of iid Bernoulli leading to $\mathbb P(T_1=n)$ : Value :(0,...,0 ,1,0 ,...,0 ,1 ) Index :(1,...,n-1,n,n+1,...,n+k-1,n+k) So as $B_i$ are iid the probability of this event is :
\begin{equation*}\mathbb P(T_2=n+k;T_1=n)=\Pi_{i=1}^{n-1}P(B_i=0).P(B_n=1).\Pi_{i=n+1}^{n+k-1}P(B_i=0).P(B_{n+k}=1)=(1-p)^{n-1}.p.(1-p)^{k-1}.p\end{equation*}
And in the same way :
$\mathbb P(T_1=n)=(1-p)^{n-1}.p$
so $\mathbb P(T_2-T_1=k)=\frac{\mathbb P(T_2-T_1=k;T_1=n)}{\mathbb P(T_1=n)}=\frac{(1-p)^{n-1}.p.(1-p)^{k-1}.p}{(1-p)^{n-1}.p}=(1-p)^{k-1}.p$
which doesn't depend on $n$ !!! QED
And for confirmatory purposes by expressing the event $T_2-T_1=k$ as : Value :(0 ,...,0 ,1 ) Index :(n+1,...,n+k-1,n+k) then we get from the independence of Bernoullis: $\mathbb P(T_2-T_1=k)=\Pi_{i=n+1}^{n+k-1}P(B_i=0).P(B_{n+k}=1)=(1-p)^{k-1}.p$