2
$\begingroup$

I'm totally a newbie in this community. I would like to ask for help in a modeling question. Thanks for your time and patience in advance.

Assume I have N unique items and I access T items per second. The access pattern follows some distribution (e.g., Zipfian distribution). I'm wondering at what time can I successfully cover all the unique items (i.e., the relationship between number of accessed unique items and time)? Can anyone help me build functions on this problem?

$\endgroup$
  • $\begingroup$ @MorganRodgers but I may always access redundant not unique items. That's why I said the access pattern follows Zipfian distribution and asked when to cover all unique items. $\endgroup$ – Cheng Wang May 18 at 6:36
0
$\begingroup$

$\large{\mathbf{Probability~Estimate}}$

Based on a probabilistic point of view, an approximate bound can be derived for the probability of the string generated by reading distinct elements of an infinite dictionary at a given rate as follows.

First we note that after time t, then the software generates a string of length $M=tT$, that may or may not contain all the possible distinct dictionary elements. We would like to calculate the probability that it does. The probability that elements numbered $I_k~~,~~ k=1...N$ occurs $m_k$ times in a string of total length $M\geq N$ is given by the multinomial distribution:

$$P(\{\#I_k=m_k\})=\frac{M!}{m_1 !\dots m_N!}p_1^{m_1}...p_N^{m_N}$$

To obtain the probability of obtaining strings that contain at least one occurence of every distinct element of the dictionary we just need to consider all strings with more than one occurence of every element, in other words:

$$P(m_1\neq 0,..., m_N\neq 0;M)=\sum_{\sum m_i=M~,~m_k \geq1}\frac{M!}{m_1 !\dots m_N!}p_1^{m_1}...p_N^{m_N}$$

Evaluating this sum is not entirely trivial but based on repeated applications of the recursion relation (true for $n\geq 2$)

$$\small{P(m_1\neq 0,..., m_n\neq 0;M)=(p_1+...+p_n)^M-\sum_{i,cyc}P(m_1\neq 0,..., m_i=0,..., m_n\neq 0;M)}$$

we can reduce this problem further and further until only two non-zero variables are left, and that result is easy to compute:

$$P(m_1\neq 0, m_2\neq 0)=(p_1+p_2)^M-p_1^M-p_2^M$$

We find the following result:

$$P(m_1\neq 0,..., m_N\neq 0;M)=\sum_{n=0}^{N-1}(-1)^n \sum_{P_{S_n}}(\sum_{k\in S_n}p_k)^M$$

where the set $S_n$ is constructed by deleting $n$ elements from the set $\{1,2,...,N\}$ arbitrarily and then sums over $P_{S_n}$, all ${N}\choose{n}$ possible choices of indices to delete. To wit:

$$\small{P(m_1\neq 0, m_2\neq 0, m_3\neq 0)=(p_1+p_2+p_3)^M-((p_1+p_2)^M+(p_2+p_3)^M+(p_3+p_1)^M)+(p_1^M+p_2^M+p_3^M)}$$

I haven't been able to simplify this formula significantly. However, for probability distributions like Zipf's law, this cumbersome expression allows simplification for large $M$, where we can approximate it by it's dominant term :

$$P(m_1\neq 0, m_2\neq 0, m_3\neq 0)\approx 1-(1-p_N)^M$$

where $p_N=\frac{1}{NH_N}$ represents the smallest probability in the Zipf distribution Then if we demand that the probability for being very unlucky and getting strings that do not contain all entries for large $M$ is smaller than some number $\epsilon$ we obtain that for $N$ large:

$$t\approx\frac{1}{T}\frac{\ln\epsilon}{\ln(1-p_N)}\approx\frac{\ln(1/\epsilon)}{T}N\ln N$$

and the algorithm seems to be of order $\mathcal{O}(N\ln N)$.

$\large{\mathbf{Arrival~Time~Statistics}}$

We could also perform an arrival time style analysis to the algorithm, where it's nature as a stochastic process becomes evident. we ask the question, what is the probability that the time $M=Tt$ is the first time we get all $N$ unique elements of our dictionary in our string? We know this cannot happen for $t<N$ and thus $P(t=M<N)=0$. We can calculate the probability distribution for $t\geq N$ by observing that 1)the last element of the string is fixed, but we have to sum over it at the end 2)the rest of the string is arbitrary, but with the restriction that all elements except the one that appeared at time $M$ have to occur at least once.

We can write

$$P(t=M;N)=\sum_{cyc}p_N\Big(\sum_{m_i\geq 1~,~ \sum m_i=M-1}\frac{(M-1)!}{m_1!...m_{N-1}!}p_1^{m_1}...p_{N-1}^{m_{N-1}}\Big)$$

However the sum in the parentheses was done before:

$$P(t=M;N)=\sum_{cyc}p_N\sum_{n=0}^{N-2}(-1)^n \sum_{P_{S_n}}(\sum_{k\in S_n}p_k)^{M-1}$$

One must be able to check that this probability distribution is indeed normalized (I checked up to N=3 for all M). The expectation value of the arrival time therefore is given by a simple exponential generating function calculation:

$$\mathbb{E}[M-2]=\sum_{cyc}p_N\sum_{n=0}^{N-2}(-1)^n \sum_{P_{S_n}}\frac{(\sum_{k\in S_n}p_k)^2}{(1+\sum_{k\in S_{n}}p_k)^2}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.