Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We recently saw a problem here about a taxicab driver who operates in a city with two zones $A$ and $B$, taking trips that may or may not take him to the other zone. The probabilities are such that if he is currently in zone $A$, his next trip takes him to a destination in $A$ with probability $6/10$ and to a destination in $B$ with probability $4/10.$ If he is in zone $B$, the next destination lies in $A$ with probablity $3/10$ and he stays in $B$ with probability $7/10.$ A trip within zone $A$ generates a profit of $\$6$, a trip between zones generates a profit of $\$12$ and a trip within $B$ generates an $\$8$ profit. We are asked to study the (expected) profit the driver makes after one trip, and more generally, after $n$ trips. I solved this problem using generating functions. My question would be, can anyone confirm my results by Markov chain models? I'm not even sure what I worked out is correct. I do think that since I have a generating function that encodes all factorial moments of the distribution of kinds of trips I have in a sense captured all there is to know about these distributions. Can you somehow shortcircuit the generating function method and find the expected profit after $n$ trips in an easier way? More importantly, how do you represent the profit concept in the Markov chain model? My solution follows. The recurrences were solved with the Gfun Package, authored by the INRIA symbolic computation group. Learn more about it here. EDIT: there must be a mistake here as all the averages for the profit are less than six, which is the minimum profit for any trip.

Let $p_A(n)$ and $p_B(n)$ be polynomials in $u, v$ and $w$, where the cofficient of $[u^k v^l w^m]$ gives the probability that we are in zone $A$ ($B$) after $n$ steps and $k$ of these were trips from zone $A$ to $A$, $l$ were trips from $A$ to $B$ or $B$ to $A$ and $m$ were trips from zone $B$ to $B$.

Then we have the following system of equations: $$ p_A(n) = u p_A(n-1) \frac{6}{10} + v p_B(n-1) \frac{3}{10} \\ p_B(n) = v p_A(n-1) \frac{4}{10} + w p_B(n-1) \frac{7}{10} .$$ Multiply by $z^n$ to get $$ z^n p_A(n) = uz z^{n-1} p_A(n-1) \frac{6}{10} + vz z^{n-1} p_B(n-1) \frac{3}{10} \\ z^n p_B(n) = vz z^{n-1} p_A(n-1) \frac{4}{10} + wz z^{n-1} p_B(n-1) \frac{7}{10} .$$ Now introduce the generating functions $$ P_A(z) = \sum_{n\ge 0} z^n p_A(n) \quad \text{and} \quad P_B(z) = \sum_{n\ge 0} z^n p_B(n) $$ and let $q$ be the probability that the driver starts in zone $A$. This gives the system of equations $$ P_A(z) - q = uz P_A(z) \frac{6}{10} + vz P_B(z) \frac{3}{10} \\ P_B(z) - (1-q) = vz P_A(z) \frac{4}{10} + wz P_B(z) \frac{7}{10}.$$ The solution is $$P_A(z)=-5\,{\frac {-3\,vz+3\,vzq+7\,wzq-10\,q}{-6\,{v}^{2}{z}^{2}+50-30\,uz-35\, wz+21\,w{z}^{2}u}}\\ P_B(z)=10\,{\frac {5-5\,q-3\,uz+3\,uzq+2\,vzq}{-6\,{v}^{2}{z}^{2}+50- 30\,uz-35\,wz+21\,w{z}^{2}u}} $$ The next step is to introduce the profit into the generating function, replacing $u$ by $u^6$, $v$ by $v^{12}$ and $w$ by $w^8$, giving $$ Q_A(z) = \left( \frac{d}{du} + \frac{d}{dv} + \frac{d}{dw} \right) P_A(z; u^6, v^{12}, w^8)_{u=1, v=1, w=1} \\ Q_B(z) = \left( \frac{d}{du} + \frac{d}{dv} + \frac{d}{dw} \right) P_B(z; u^6, v^{12}, w^8)_{u=1, v=1, w=1}.$$ This yields $$ Q_A(z) = 6\,{\frac {z \left( -32\,z+3\,{z}^{2}-4\,zq+4\,{z}^{2}q+60 \right) }{ \left( z-1 \right) ^{2} \left( 3\,z-10 \right) ^{2}}}\\ Q_B(z) =-8\,{\frac {z \left( -70 +10\,q-16\,zq-9\,{z}^{2}+6\,{z}^{2}q+48\,z \right) }{ \left( z-1 \right) ^{2} \left( 3\,z- 10 \right) ^{2}}}$$ Now to conclude we must assign the probability $q$. We have everything ready to treat the cases $q=1$ (driver starts in zone $A$) and $q=0$ (driver starts in zone $B$), but to keep it simple we will set $q=1/2$, with the driver equally likely to start in either zone.

The probabilities of being in either $A$ or $B$ are given by $$ D_A(z) = P_A(z; 1, 1, 1) = -5\,{\frac {2\,z-5}{15\,{z}^{2}+50-65\,z}} \\ D_B(z) = P_B(z; 1, 1, 1) = 10\,{\frac {5/2-1/2\,z}{15\,{z}^{2}+50-65\,z}} $$ and the coefficients are $$ [z^n] D_A(z) = 3/7+1/14\, \left( 10/3 \right) ^{-n} \\ [z^n] D_B(z) = 4/7-1/14\, \left( 10/3 \right) ^{-n}$$ and we can see that $[z^n] D_A(z) + [z^n] D_B(z) = 1,$ as it ought to. Asymptotically we find that $$ [z^n] D_A(z) \sim 3/7 \\ [z^n] D_B(z) \sim 4/7.$$ With $q=1/2$, the two profit generating functions become $$ F_A(z) = 6\,{\frac {z \left( -34\,z+5\,{z}^{2}+60 \right) }{ \left( z-1 \right) ^{2} \left( 3\,z-10 \right) ^{2}}}$$ and $$ F_B(z) = 8\,{\frac {z \left( 65-40\,z+6\,{z}^{2} \right) }{ \left( z-1 \right) ^{2} \left( 3\,z-10 \right) ^{2}}}.$$ The respective coefficients for the expected profit are $$[z^n] F_A(z) = -{\frac {108}{343}}+{\frac {4}{49}}\, \left( 10/3 \right) ^{-n} \left( n+1 \right) +{\frac {80}{343}}\, \left( 10/3 \right) ^{-n}+{\frac {186}{49}}\,n$$ and $$[z^n] F_B(z) = {\frac {80}{343}}-{\frac {4}{49}}\, \left( 10/3 \right) ^{-n} \left( n+1 \right) -{\frac { 52}{343}}\, \left( 10/3 \right) ^{-n}+{\frac {248}{49}}\,n .$$ Asymptotically we thus have for the expected profit after $n$ trips, given that we are in zone $A$ (or $B$), $$[z^n] F_A(z) \sim \frac{186}{49} n - \frac{108}{343}$$ and $$[z^n] F_B(z) \sim \frac{248}{49} n + \frac{80}{343}.$$ The grand average for the expected profit is thus $$ \frac{3}{7} \left( \frac{186}{49} n - \frac{108}{343} \right) + \frac{4}{7} \left( \frac{248}{49} n + \frac{80}{343} \right) = \frac{1550}{343} n - \frac{4}{2401}.$$ The reader is invited to confirm this result by giving a simpler derivation.

As for the original question, we get $$ [z^n] D_A(z) * [z^n] F_A(z) + [z^n] D_B(z) * [z^n] F_B(z) = \frac{1}{2} \frac{18}{5} + \frac{1}{2} \frac{26}{5} = \frac{22}{5}.$$ Keep in mind that this is for the driver being equally likely to be in zone $A$ or $B$ at the start of the process.

For the driver starting at $A$, the result is $$ \frac{3}{5} \frac{18}{5} + \frac{2}{5} \frac{24}{5} = \frac{102}{25}.$$

For the driver starting at $B$, we find $$ \frac{3}{10} \frac{18}{5} + \frac{7}{10} \frac{28}{5} = 5.$$

share|improve this question
1  
and the question is....? –  amWhy Jan 18 '13 at 3:50
    
Find the mistake in the profit calculation. –  Marko Riedel Jan 18 '13 at 3:52
    
Will do. I did accept anwers to my two bounty questions. I don't know why these aren't being counted. –  Marko Riedel Jan 18 '13 at 17:29
    
@Marko Riedel: You gave the bounties, but did not accept the answers. To accept an answer, click the check mark below the down arrow at the top left corner of a post. –  Eric Stucky Jan 18 '13 at 21:09
    
@EricStucky Okay, thanks for the pointer, I accepted those two answers. –  Marko Riedel Jan 18 '13 at 21:35

1 Answer 1

It seems to me that we can drop the conditioning from the profit calculation. This gives for the expected profit $$\left( \frac{186}{49} n - \frac{108}{343} \right) + \left( \frac{248}{49} n + \frac{80}{343} \right) = \frac{62}{7} n - \frac{4}{49}.$$

As for the original question (where I put $[z^n]$ instead of $[z^1]$), we get $$ [z^1] F_A(z) + [z^1] F_B(z) = \frac{18}{5} + \frac{26}{5} = \frac{44}{5}.$$

For the driver starting at $A$, the result is $$ \frac{18}{5} + \frac{24}{5} = \frac{42}{5}.$$

For the driver starting at $B$, we find $$\frac{18}{5} + \frac{28}{5} = \frac{46}{5}.$$

share|improve this answer
    
Looking at this it seems to me that it is probably a trivial calculation, setting up a system of equations without involving generating functions. Yes the generating function encodes more information but if we are only concerned about asymptotics rather than exact distributions, then we can do without the generating function, right? It is nice of course knowing that $[z^n] P_A(z)$ and $[z^n] P_B(z)$ produces the entire distribution for all $n$. Enter it into a symbolic calculator and get e.g. $[z^3] P_A(z).$ –  Marko Riedel Jan 18 '13 at 4:18
    
E.g. for $q=1/2$ and two trips, the distribution is $$[z^2] P_A(z) = {\frac {3}{50}}\,{v}^{2}+{\frac {9}{100}}\,vu+{\frac {21}{200}}\,vw+{\frac {9}{50}}\,{u}^{2}.$$ –  Marko Riedel Jan 18 '13 at 4:26
    
We also have $$[z^2] P_B(z) = {\frac {3}{50}}\,{v}^{2}+{\frac {3}{25}}\,vu+{\frac {7}{50}}\,vw+{ \frac {49}{200}}\,{w}^{2}$$ and of course $$[z^n] P_A(z;1,1,1) + [z^n] P_B(z;1,1,1) = 1.$$ –  Marko Riedel Jan 18 '13 at 21:46
    
I have treated another, simpler question by the same method which you may read should it be the case that the above is too opaque. That should clarify what is going on here -- this is the link. –  Marko Riedel Jan 19 '13 at 0:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.