There was some talk in the attack analysis group about permanent tips and orphaned transactions, and the following scenario is relevant.
Consider an immortal gardner who drinks too much. Every morning he digs two holes.After having too much beer for lunch, in the afternoon he randomly selects one of the empty holes in his garden, to plants a flower in it, and then falls asleep.
So, on day 1, he digs 2 holes and fills 1, leaving 1 hole empty. On day 2, he digs 2 more holes and fills 1, and so now there is a total of 4 holes with 2 filled and 2 empty. On day three he repeats, leaving a total of 6 holes, 3 of which are filled and 3 are empty. Continuing in this manner, on day n, there are 2n total holes with n empty holes. Thus the number of holes grows linearly.
However, the gardner eventually fills every hole gets almost surely. To see this, consider a hole dug on day m. The that it will be filled on that day is 1/m since there are m open hole). If it is not filled that day, the probability of filling it the next is 1/(m+1) since there will be m+1 holes. In short, for every day n>m, the hole will be filled with probability 1/n (assuming it hasnt been filled.
Thus the probability of the hole never being filled is:
\lim_{N\to \infty} \prod_{n=m}^N \frac{n-1}{n}=\lim_{N\to \infty} \frac{(N-1)(N-2)....(m-1)}{(N(N-1)....m}= \lim_{N\to \infty} \frac{m-1}{N}=0
Therefore, the probability of the hole not being filled is 0.
What can we learn form our poor gardner? The point is that simply observing that the number of tips in the tangle is increasing, does not imply that any tip will be left behind. On the other hand, in the example, a hole dug on day 1000 will probably take years to fill. Such a hole is “permanent” for all intents and purposes. The same may be for tips, and so we should find a pragmatic and mathematical way of defining effectively permanent tips.
