Assume a fixed set of message $D$ and an associated distribution for selecting each message $d_i$ such that the total probability $\sum_{i \in D} d_i = 1$. We create a cache with $M$ bits and $k$ caches, where each message from $D$ gets mapped to $k$ unique entries between $[1,M]$ (i.e., a Bloom Filter). We introduce a random variable $Y_j$ to represent the count of occupied slots in the cache at the $j$-th iteration. Furthermore, we assume that once $Y_j$ reaches or exceeds a threshold $\sigma$, the cache is reset, and the process concludes. I am interested in proving the following lemma:
Let $X_{j} = \mathbb{1}_{Y_j \geq \sigma \; \&\& \; Y_{j-1} < \sigma}$ (i.e. the $j+1$-st draw to result in a reset given that it did not in the $j$-th draw), then $P(X_j = 1) \leq P(X_{j+1} = 1)$.
I am finding it challenging to prove this lemma.I have verified its validity via simulations and it seems to hold. I can also brute force the computation for very simple cases and it also works.
Please note that this situation differs from demonstrating that for $X'_{j} = \mathbb{1}_{Y_j \geq \sigma}$, the probability $P(X'_j = 1) \leq P(X'_{j+1} = 1)$ is relatively simple to establish using a sample path argument. I mention this because I originally thought that the proof would be trivial using this argument. The main difficulty arises because, for any specified number of set bits, it's possible to construct sequences of messages of any length that have resulted in that filter being filled.
I would appreciate any help. A counter-example would also do the trick. Thanks!
