Probability of overwriting repeatedly chosen $\binom{n}{k}$ elements. Suppose we have an array $M$ of memory cells with $n$ cells represented by $M = [c_1;...;c_n]$, and suppose we will repeat the following process in every time $t$: 


*

*Choose a new (unique for every $t$) message $m_t$;

*Uniformly choose a subset $C_t$ of size $k$, among these $n$ cells:  $C_t = [c_{t1};...;c_{tk}] \subset [c_1;...;c_n]$; 

*Copy the message $m_t$ on every memory cell in the subset $C_{t}$: $[c_{t1}=m_t;...;c_{tk}=m_t]$; 


By repeating the above experiment, there is a probability of overwriting a cell: update an already written cell with a new message. So, in a after time $t+i$, we can lose some (or all) message copies on $C_t$. 
So, what the probability of at least one message $m_t$, written in $t$, remain in any of $c_{tk}$ cell after $i$ more repetition of this experiment? 
Please, I need some help in how to make an analysis of the relation of the size of memory $n$, the size of the subset of copies $k$, and the number of repetitions $i$.

Approximate solution.  (My gut feel is that this should be a good approximation if $k \ll n$...?)
The approximation: assume each copy is erased independently.  (In the exact model, erasures of different copies are "negatively" correlated, i.e. conditioning on a copy $A$ being erased at time $t$ will slightly decrease the probability that a copy $B$ will also be erased at time $t$.)


*

*At any time, a surviving copy will be erased with prob $p = {k \over n}$.  


*

*I.e. it continues to survive with prob $1 - p$.


*A copy will survive for $i$ timeslots with prob $(1 - p)^i$.  


*

*I.e. a copy will fail to survive for $i$ timeslots with prob $1 - (1 - p)^i$.  (This is the prob it will be overwritten during any of those $i$ timeslots.)


*No more surviving copies means all $k$ copies fail to survive.  This is where we bring in the independence approximation: the prob that all $k$ copies fail to survive $\approx (1 - (1-p)^i)^k$.


*

*In the exact model, conditioning on a copy $A$ failing to survive will slightly decrease the prob that copy $B$ also fails to survive.  So my guess is that the true value of $Prob(\text{no survivors}) $ is slightly $< (1 - (1 - p)^i)^k$.


*Finally, prob that some copy will survive $\approx \fbox{$1 - (1 - (1 - p)^i)^k$}$
