91影视

The higher the probability that the advertisement will be chosen.

Consider a classified advertisement directory with m pages, where m is a very large number. Assuming that the quantity of adverts per page varies, the only way to determine how many advertisements are on a given page is to count them. Furthermore, imagine there are too many pages for a comprehensive count of the whole number of advertisements to be possible, and the goal is to select a directory advertisement in such a way that each of them has an equal probability of being chosen. Let $n_i$signify the number of advertisements on page i, and $i=1,.....,m$denote the number of advertisements on page i. Assuming that these values are unknown, we can assume that they are all less than or equal to n.

As a result, we were unable to achieve our goal because advertisements in this scenario do not have equal chances of being chosen.

Assume that we only have two pages, one of which contains a million adverts and the other of which contains only one advertisement.

As a result, it is evident that an advertisement on the second page has a significantly higher chance of being chosen than a specific one on the first page.

As a result, the advertisement on the second page has a significantly higher chance of being chosen.

The probability that an advertisement on a page will be accepted after a single iteration of the algorithm.

Consider the provided data. First, we must choose the page i; the probability for this test is $\frac{1}{m}$

Accept page i now, and the probability is $\frac{n\left(i\right)}{n}$

So the necessary probability is $$\begin{gathered} probability=P(Chosepagei)P(Accepypagei) \\ P=\frac{1}{m}脳\frac{n\left(i\right)}{n} \\ P=\frac{n\left(i\right)}{mn} \end{gathered}$$

As a result, the probability of an advertisement on page acceptance after a single iteration of the algorithm is$P=\frac{n\left(i\right)}{mn}$The probability that an advertisement on a page will be accepted after a single iteration of the algorithm.

The probability that an advertisement will be accepted after a single iteration of the algorithm.

Consider the following query:

Apply the law of total probability to the fact that a page must be selected.

As a result, the probability that a single iteration will result in acceptance is.probability$=\underset{i=1}{\overset{m}{鈭�}}鈥�P(chosepagei)P(Acceptpagei)$

Now substitute the value

$$\begin{gathered} P=\underset{i=1}{\overset{M}{鈭�}}P\frac{1}{m}脳\frac{n\left(i\right)}{n} \\ P=\underset{i=1}{\overset{M}{鈭�}}\frac{n\left(i\right)}{mn} \end{gathered}$$

Therefore the probability that an advertisement will be accepted after a single iteration of the algorithm is $P=\underset{i=1}{\overset{M}{鈭�}}\frac{n\left(i\right)}{mn}$

The probability that the algorithm goes through k iterations before accepting the $j^{th}$ ad on page i on the final iteration.

Consider the give information,

Firstly, k-1 iterations had to result with no acceptance.

So, we have to accept $i^{th}$page in the $K^{th}$iteration and choose $j^{th}$advertisement.

Thus probability is

$$\begin{gathered} P={\left(1鈭�\underset{i=1}{\overset{m}{鈭�}}鈥�\frac{1}{m}脳\frac{n\left(i\right)}{n}\right)}^{k鈭�1}\left(\frac{1}{m}\right)\left(\frac{n\left(i\right)}{n}\right)\left(\frac{1}{n\left(i\right)}\right) \\ P={\left(1鈭�\underset{i=1}{\overset{m}{鈭�}}鈥�\frac{1}{m}脳\frac{n\left(i\right)}{n}\right)}^{k鈭�1}\left(\frac{1}{mn}\right) \\ P=\left(1鈭�\underset{i=1}{\overset{m}{鈭�}}鈥�\frac{n\left(i\right)}{mn}\right)\left(\frac{1}{mn}\right) \end{gathered}$$

Hence The probability that the algorithm goes through k iterations before accepting the advertisement on page i on the final iteration is$P=\left(1鈭�\underset{i=1}{\overset{m}{鈭�}}鈥�\frac{n\left(i\right)}{mn}\right)\left(\frac{1}{mn}\right)$

The probability that the$j^{th}$advertisement on page i is the advertisement obtained from the algorithm.

Consider the question,

To get the $j^{th}$advertisement on page i, we need to select the page i randomly, accept that page and select the $j^{th}$advertisement.

So the probability is,

role="math" localid="1647491134996" $$\begin{gathered} P=\frac{1}{m}脳\frac{n\left(i\right)}{n}脳\frac{1}{n\left(i\right)} \\ \mathrm{P}=\frac{1}{\mathrm{mn}} \end{gathered}$$

The probability does not depend upon the number of the advertisement on the certain page.

Therefore,$\frac{1}{mn}$is the probability that the $j^{\text{th}}$advertisement on page i is the advertisement obtained from the algorithm.

The number of iterations that the algorithm goes through.

Consider the given information,

The random variable Y indicates how many iterations are required to obtain an advertising.

So,

We know that

$\mathrm{Y}~Geom\left(\underset{i=1}{\overset{m}{鈭�}}\frac{1}{m}脳\frac{n\left(i\right)}{n}\right)$

Calculate the mean $E\left(Y\right)=\frac{1}{P}$

role="math" localid="1647491726054" $$\begin{gathered} E\left(Y\right)=\frac{1}{\left({鈭�}_{i=1}^m\frac{1}{m}脳\frac{n\left(i\right)}{n}\right)} \\ \mathrm{E}\left(\mathrm{Y}\right)=\frac{1}{{鈭�}_{\mathrm{i}=1}^{\mathrm{m}}\frac{\mathrm{m}\left(\mathrm{i}\right)}{\mathrm{mn}}} \\ E\left(Y\right)=\frac{1}{\frac{1}{mn}{鈭�}_{i=1}^{m}n\left(i\right)} \end{gathered}$$

So number of iteration is

$\mathrm{E}\left(\mathrm{Y}\right)=\frac{\mathrm{mn}}{{鈭�}_{\mathrm{i}=1}^{\mathrm{m}n\left(\mathrm{i}\right)}}$

Hence$\frac{\mathrm{mn}}{{鈭�}_{\mathrm{i}=1}^{\mathrm{m}n\left(\mathrm{i}\right)}}$number of iterations taken by the algorithm.