I am trying to solve a combinatoric problem. The problem is the following: There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X and Y and they just stand in front of the box they have chosen.

The selection rule is the following: Type A people always select box X; Type B people always select the box that has the longest queue, e.g., when facing state $(n,m)$ such that $n>m$, where the 1st entry is the queue length at box X and the 2nd entry is the queue length at box Y. The B type people always chooses box X, which has $n$ people there. If the B type people is the first arrival or he sees two boxes have same queue length, then he chooses each box with 1/2 probability; Type C people always select the box that has positive queue length with equal probability, e.g., when seeing state $(n,0)$, type C people always chooses box X, the one with $n$ people; when seeing state $(n,m)$, with $n>0,m>0$, then type C people chooses each box with equal probability. If the type C people is the first arrival, then he chooses each box with equal probability.

Each arrival with probability $q_A$ of being A type, $q_B$ of being B type, $q_C$ of being C type, and $q_A+q_B+q_C=1$. Each arrival is independent of each other.

The question is to compute the probability $P\{(m,n)|(X,Y)\}$ where $0<m<n$.

This problem can be solved recursively, but I am struggling to obtain some analytical expression.

One thing is sure that the first arrival cannot be type A, since type A people will choose box X only, and then all the later people regardless of their type will all choose box X according to their selection rule.

  • $\begingroup$ What probability do you want to compute? The probability that $Y$'s queue is ever longer than $X$'s, the probability that $Y$'s queue is longer than $X$'s at some given time, or something else? And can you say something about why you are interested in this problem? $\endgroup$ – Ben Barber May 25 '16 at 10:07
  • $\begingroup$ Since FTXX is able to compute this quantity recursively, I'm guessing the question is asking for the probability of visiting the state $(m,n)$ as a function of $m$ and $n$ (as well as $q_A$, $q_B$, $q_C$); presumably $N = m+n$ and the queues are initially empty. It seems easier to think about the difference $m-n$ which is doing a version of a simple random walk, but I don't know of a nice exact expression for the distribution of a random walk whose transition probabilities depend on sign. There should be nice exact expressions for asymptotics such as $lim_{N \to \infty} P(m < n)$. $\endgroup$ – Elena Yudovina May 25 '16 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.