subject

Suppose that a sequence of items passes by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen so far. Moreover we do not know the total number of items in advance and we cannot store more than one item at any time. (a) Consider the following algorithm. When the first item appears, we store it. When the k-th item appears, we replace the stored item with probability 1/k. Show that this algorithm solves the problem. (b) Now suppose that when the k-th item appears, we replace the stored item with probability 1/2. What is the distribution of the stored item in this case?

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 23.06.2019 07:00, schvox
1. you have a small business that is divided into 3 departments: accounting, sales, and administration. these departments have the following number of devices (computers, printers, etc.): accounting-31, sales-28, and administration-13. using a class c private network, subnet the network so that each department will have their own subnet. you must show/explain how you arrived at your conclusion and also show the following: all available device addresses for each department, the broadcast address for each department, and the network address for each department. also, determine how many "wasted" (not usable) addresses resulted from your subnetting (enumerate them).
Answers: 3
image
Computers and Technology, 23.06.2019 17:00, Need1ng
The more powerful, 60 volt cables and the main power shut-off on an hev are both colored orange.
Answers: 1
image
Computers and Technology, 24.06.2019 12:30, hilario4785
Why does the pc send out a broadcast arp prior to sending the first ping request
Answers: 1
image
Computers and Technology, 24.06.2019 17:00, 322993
Following are uses of spreadsheets. for each use, choose whether the use is a business use, consumer use, or student use. family budget: sales data: recording research data for science class:
Answers: 2
You know the right answer?
Suppose that a sequence of items passes by one at a time. We want to maintain a sample of one item w...

Questions in other subjects:

Konu
History, 23.09.2019 19:30
Konu
Advanced Placement (AP), 23.09.2019 19:30