(from Pittel 17) Telephone books, n in number, are kept in a stack. The probabil
ID: 2967121 • Letter: #
Question
(from Pittel 17) Telephone books, n in number, are kept in a stack. The probability that the book numbered i (where 1 less than equal to i less than equal to n) is consulted for a given phone call is pi > 0, where the pi's sum to 1. After a book is used, it is placed at the top of the stack. Assume that the calls are independent and evenly spaced. and that the system has been employed indefinitely far into the past. Let d, be the average depth of book i in the stack. Show that di less than equal to dj whenever pi greater than equal to pj. Thus, on the average, the more popular books have a tendency to be closer to the top of the stack. Hint: Let pij denote the probability that book i is above book j. Show that Pij = pij((1 - pj) + pjipi.Explanation / Answer
let us take two books i , j
probebility of taking book i = pi
probebility of taking book j = pj
probebility of i above j = pij
probebility of j above i = pji
letus assume that a book is picked
if i is above j then except when the picked book is j , the book i will be above j = pij * (1-pj)
if the j is above i then , i will be above j only if we pick book i = pji * pi
total probebility of pij= pji * pi + pij * (1-pj)
Now we have to show that
pij > pji if pi >pj
pij= pji * pi + pij * (1-pj) => pij * pj = pji * pi
=> pij/pji = pi/pj
since the pi >pj => pij > pji
hence probebility of i above j is more when pi > pj
hence di < dj when pi > pj
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.