/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 8 Consider a directory of classifi... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 6: Problem 8

Consider a directory of classified advertisements that consists of \(m\) pages, where \(m\) is very large. Suppose that the number of advertisements per page varies and that your only method of finding out how many advertisements there are on a specified page is to count them. In addition, suppose that there are too many pages for it to be feasible to make a complete count of the total number of advertisements and that your objective is to choose a directory advertisement in such a way that each of them has an equal chance of being selected. (a) If you randomly choose a page and then randomly choose an advertisement from that page, would that satisfy your objective? Why or why not? Let \(n(i)\) denote the number of advertisements on page \(i, i=1, \ldots, m\), and suppose that whereas these quantities are unknown, we can assume that they are all less than or equal to some specified value \(n\). Consider the following algorithm for choosing an advertisement. Step 1. Choose a page at random. Suppose it is page \(X\). Determine \(n(X)\) by counting the number of advertisements on page \(X\). Step 2. "Accept" page \(X\) with probability \(n(X) / n\). If page \(X\) is accepted, go to step 3. Otherwise, return to step 1 . Step 3. Randomly choose one of the advertisements on page \(X\).

Short Answer

Expert verified
In summary, randomly choosing a page and then randomly choosing an advertisement from that page does not satisfy the objective of having each advertisement with an equal chance of being selected, as the probability depends on the number of advertisements on the chosen page. However, the given algorithm does satisfy the objective, as the overall probability of choosing any advertisement is \(\frac{1}{mn}\), which is independent of the number of advertisements on any particular page.

Step by step solution

01

(a) Discussing the Random Page, Random Advertisement method

In the first approach, we randomly choose a page and then randomly choose an advertisement from that page. Let's analyze the probability of choosing a specific advertisement using this method. 1. The probability of choosing a specific page (say, page i) is \(\frac{1}{m}\) as there are \(m\) pages. 2. Given that we picked page i, the probability of choosing a particular advertisement (say, ad A) present on that page is \(\frac{1}{n(i)}\) as there are \(n(i)\) advertisements on page i. So, the overall probability of choosing ad A using this method is \(P(A) = \frac{1}{m} \times \frac{1}{n(i)}\). Notice that this probability depends on the number of advertisements on page i. This means that advertisements on pages with different numbers of ads would have different probabilities of being chosen, contrary to our objective. Therefore, this method does not satisfy our objective.
02

Analyzing the Given Algorithm

Now, let's analyze the given algorithm and verify whether it satisfies our objective. Step 1: We choose a page at random with probability \(\frac{1}{m}\) and denote the chosen page number by X. We determine the number of advertisements, \(n(X)\), on that page by counting them. Step 2: We accept page X with probability \(\frac{n(X)}{n}\). With this step, pages with more advertisements have higher probabilities of being accepted. If page X is accepted, we proceed to Step 3. If not, we return to Step 1. Step 3: We randomly choose one of the advertisement on the accepted page X. Let's compute the overall probability of choosing a particular advertisement, say, ad A on page i: 1. Probability of choosing page i in Step 1: \(\frac{1}{m}\) 2. Probability of accepting page i in Step 2: \(\frac{n(i)}{n}\) 3. Probability of choosing ad A on page i in Step 3: \(\frac{1}{n(i)}\) The overall probability of choosing ad A using the given algorithm is \(P(A) = \frac{1}{m} \times \frac{n(i)}{n} \times \frac{1}{n(i)} = \frac{1}{mn}\). We can observe that this probability is the same for every advertisement in the directory, as it is independent of the number of advertisements (\(n(i)\)) on any particular page. Therefore, the given algorithm satisfies our objective of choosing a directory advertisement such that each of them has an equal chance of being selected.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Two dice are rolled. Let \(X\) and \(Y\) denote, respectively, the largest and smallest values obtained. Compute the conditional mass function of \(Y\) given \(X=i\), for \(i=1,2, \ldots, 6 .\) Are \(X\) and \(Y\) independent? Why?

An ambulance travels back and forth, at a constant speed, along a road of length \(L\). At a certain moment of time an accident occurs at a point uniformly distributed on the road. [That is, its distance from one of the fixed ends of the road is uniformly distributed over \((0, L)\).] Assuming that the ambulance's location at the moment of the accident is also uniformly distributed, compute, assuming independence, the distribution of its distance from the accident.

If \(X\) and \(Y\) are independent binomial random variables with identical parame ters \(n\) and \(p\), show analytically that the conditional distribution of \(X\), giver that \(X+Y=m\), is the hypergeometric distribution. Also, give a secons argument that yields the result without any computations. HINT: Suppose that \(2 n\) coins are flipped. Let \(X\) denote the number of head in the first \(n\) flips and \(Y\) the number in the second \(n\) flips. Argue that giver a total of \(m\) heads, the number of heads in the first \(n\) flips has the same distribution as the number of white balls selected when a sample of size \(n\) is chosen from \(n\) white and \(n\) black balls.

Consider an experiment that results in one of three possible outcomes, outcome \(i\) occurring with probability \(p_{i}, i=1,2,3\). Suppose that \(n\) independent replications of this experiment are performed and let \(X_{i}, i=1,2,3\) denote the number of times that outcome \(i\) occurs. Determine the conditional probability mass function of \(X_{1}\), given that \(X_{2}=m\).

Show that the jointly continuous (discrete) random variables \(X_{1}, \ldots, X_{n}\) are independent if and only if their joint probability density (mass) function \(f\left(x_{1}, \ldots, x_{n}\right)\) can be written as $$ f\left(x_{1}, \ldots, x_{n}\right)=\prod_{i=1}^{n} g_{i}\left(x_{i}\right) $$ for nonnegative functions \(g_{i}(x), i=1, \ldots, n\).
See all solutions

Recommended explanations on Math Textbooks

Statistics

Read Explanation

Discrete Mathematics

Read Explanation

Calculus

Read Explanation

Pure Maths

Read Explanation

Applied Mathematics

Read Explanation

Geometry

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.