Find the expected position of the next book requested when

Question

Problem 1:

Consider a train station to which customers arrive in accordance with a Poisson process with rate λ. A train is summoned whenever there are N customers waiting in the station, but it takes K units of time for the train to arrive at the station. When it arrives, it picks up all waiting customers. Assuming that the train station incurs a cost of nc per unit time when there are n customers present, find the long run average cost.

Problem 2:

Consider a model for inventory where inventory is depleted and replenished according to Poisson processes. Thus times between depletions are iid exponential with mean 1/μ and times between arrivals of new items are also iid exponential with mean 1/λ, and the two processes are independent. No backlogging is allowed, so unsatisfied demand just disappears.

Suppose that every unit of time that the inventory is out of stock a penalty C₂ is incurred. However, there is also a holding cost C₁n for every unit of time that there are n units of stock on hand, with C₂ > C₁. Assume that λ < μ.

(a) What is the long run average cost in the system?

(b) What is the optimal value of ρ = λ/μ?

Problem 3:

Consider the following simple birth-and-death processes.

(a) Let X₁(t) be a so-called death-only process, i.e. a birth and death process with zero birth rates. Assume that the state space is finite, S = {0, 1,... , N), and consider generic positive death rates μ₁, μ₂, μ₃......, μ_n. Let T_e be the extinction time, i.e. the time that it takes for X₁(t) to reach zero (the formal definition is T_e = inf{t > 0 : X₁(T_e) = 0)).

Compute the expected extinction time under the condition that X₁(0) = N, (i.e. E[T_e, X₁(0) = N]), which is the average time that it takes for X₁(t) to reach zero.

(b) Let X₂(t) be a birth-and-death process with state space S = {0,1, , 2N}, birth rates

            0 for   k = 0,...., N-1

λ_k =

            λ for k = 0,...., 2N-1

with λ > 0 and death rate

            μ for   k = 1,...., N

μ_k =

            0 for k = N+1,...., 2N

with μ > 0. Suppose we start from the middle state, X₂(0) = N. Let T be the first time that either state 0 or state 2N are hit (in other words, the first time that "the boundary" is hit).

Compute the mean of T given that we start in the middle, E[T]X₂ (0) = N, i.e. the average time that it takes for X₂(t) to reach the boundary.

Problem 4:

A professor has 2 umbrellas. She walks to the office in the morning and walks home.in the evening. If it is raining she likes to carry an umbrella, and if it is fine she does not. Suppose that it rains on each journey witt probability p, independently of past weather. What is the long run fraction of journeys on which the professor gets wet?

Problem 5:

A cobbler runs a shoe store by himself. Custoniers arrive to bring a pair of shoes to be repaired according to a Poisson process with rate A per hour.. The time required to repair an individual shoe has an exponential distribution with a mean of a hours, α < 1/(2λ).

(a) If Π_n, is the probability that n customers arrive during a service, find

A(z) = _n=0Σ^∞ Π_nzⁿ

explicitly in terms of α and λ.

(b) Find the long run average number of pairs of shoe at the cobbler's.

Problem 6:

Buses and trolleys stop on 4th Street in Dinkytown. Buses arrive according to a Poisson process with rate λ₁. Trolleys arrive according to a Poisson process with rate λ₂. Passengers arrive according to a Poisson process with rate μ. The three Poisson processes are independent. Whenever a bus or a trolley arrives, all of the passengers waiting get on and head downtown. Neither buses nor trolleys wait for passengers to arrive; they leave if no one is waiting.

(a) Alice arrives at 1pm, what is the probability that she is picked up by a bus?

(b) Bob arrives at 2pm, what is the distribution on the amount of time he waits until he is picked up?

(c) Imagine that each passenger decides with probability p to only take a bus and with probability 1 - p to only take a trolley. All passenger decisions are independent. What is the probability that there are k passengers on the mth trolley?

Problem 7:

A continuous time Markovian Branching process is a branching process where each individual waits an exponentially distributed amount of time (with parameter α) before dying and giving birth to a random number of offspring with p.m.f: {p_j}^∞_j=0. Each offspring then independently repeats this process. Consider a continuous' ime branching process {X_t; t ≥ 0} with X₀ = 1, offspring distribution p₀ = p, p₂ = q =1 -P and exponentially distributed times between births (with mean 1). If p ≥ 1/2 find.

P(max_t>0X_t = k)

for positive integer k.

Problem 8:

Consider an M/G/1 queue with the modification that the server may serve up to in customers simultaneously. If the queue length is less than or equal to m at the beginning of a service period then she serves everybody waiting at that time, and if there are more than in customers present she serves the in customers that have been waiting the longest. Find a formula for the probability generating function of the stationary queue length at times of departures. Evaluate this formula explicitly in the case m = 2 and exponential service time distribution.

Problem 9:

Suppose there are N books, B₁, B₂,..., B_N on a shelf. When a book is requested it is removed and replaced (before the next demand) on the left hand end of the shelf. For example if there are three boob ordered on the shelf as B₁, B₂, B₃ and book 3 is requested first, then at the time of the next request the order of the books will be B3, B₂, B₁. Note that the position of the book can be thought of as proportional to the time spent searching for the book.

Assume that requests are independent and that book B_i is chosen with probability p_i. You can view this system as a Markov chain on the space of possible permutations of { 1, ... , N}. It is possible to find the unique stationary distribution of this Markov chain, but in this problem you do not need to find this stationary distribution.

(a) Find the expected position of book B_i (as measured from the left) when the system is in its stationary distribution.

(b) Find the expected position of the next book requested when the system is in its stationary distribution, which we will call μ. Note that μ is a function of p₁, p_n.

(c) Suppose that books are left in place after each order. In this case it is natural to order the books with the most popular book first, in which case it is easy to see that the expected time to find the next book requested is

_{m = i=1}Σ^N ip(i),

Where P(1)=1 ≤ i ≤ n P_i, P(₂)

where p(1) = max₁

Compare m with your answer from (b). Based on this do you think it is better to return books to the front of the shelf or keep their order fixed?

(d) Suppose that we do not know the probabilities p = (p₁, ... ,p_N) and thus model them as a random variable on the simplex

Δ_N = {P ∈ R₊^N: p₁ + .......p_N = 1 }

with the joint probability density function (α > 0 parameter)

g(P) = T(N_α)/T(α)n(p₁p₂......p_n)^{α -1}

The marginals of this distribution can be calculated, in particular for each 1 < i ≤ N the marginal density of pi is given by

f_M(pi) = T(N_α)/T(α)T((N-1)α)p^α-1(1- p)^{(N-1)α -1}

In addition the joint distribution of pi and pi is given by

f_J(pi,pj) = T(N_α)/T(α)²T((N-2)α)(pipj)^α-1(1- p_i - p_j)^{(N-2)α -1}

Use f_M and f_J to derive expressions for E(μ(p)) and E[m(p)1, where p is sampled according to the density g(.).

(e) Suppose that N → ∞  and α → 0 such that Nα → λ > 0 as N → ∞. In this case find the limit of your expressions from part (d).