Urban Operations Research Professor Arnold I. Barnett Lecture Note of 9/24/2001 Prepared by James S. Kang Crofton’s Method Let X 1 and X 2 be independent random variables that are uniformly distributed over the interval [0,a]. We are interested in computing E[|X 1 ?X 2 |]. For instance, in an urban setting, X 1 and X 2 may denote the location of an accident and the location where an emergency vehicle is currently parked in a road segment of length a, respectively. In this case, we want to know the distance (or the travel time) on average between the two locations, E[|X 1 ?X 2 |]. We may solve this question using a joint distribution of X 1 and X 2 , but Crofton’s method is quite useful for the question. Let G(a) ≡ E[|X 1 ?X 2 |]. Now consider the following question: If the interval were [0,a+ ε] where ε issmall, what would G(a+ε) be? Table 1 summarizes G(a+ε) depending on the locations of X 1 and X 2 . Table 1: G(a + ε) Case Probability of a case G(a + ε)givenacase 0 ≤ X 1 ≤ a,0≤ X 2 ≤ a a a+ε · a a+ε =( a a+ε ) 2 G(a) a<X 1 ≤ a + ε,0≤ X 2 ≤ a ε a+ε · a a+ε = εa (a+ε) 2 a+ ε 2 ? a 2 = a+ε 2 0 ≤ X 1 ≤ a, a<X 2 ≤ a+ ε a a+ε · ε a+ε = εa (a+ε) 2 a+ ε 2 ? a 2 = a+ε 2 a<X 1 ≤ a + ε, a<X 2 ≤ a+ ε ε a+ε · ε a+ε =( ε a+ε ) 2 We do not care. a0 εa+ X1 X2 Figure 1: Case where 0 ≤ X 1 ≤ a and a<X 2 ≤ a+ ε Note that we did not specify G(a + ε) for the case where a<X 1 ≤ a+ ε and a<X 2 ≤ a + ε, because the probability of that case, ( ε a+ε ) 2 , is negligible when ε is small (“If ε is small, ε 2 is pathetic.”). To compute G(a+ε) from Table 1, we invoke the total expectation theorem (or the conditional expectation rule). When a sample space is divided into A 1 ,A 2 ,...,A n that are mutually exclusive and collectively exhaustive events, the expected value of a random variable Z is computed by 1 E(Z)= n summationdisplay i=1 E(Z | A i )P(A i ) . Using the total expectation theorem, we obtain G(a + ε)=G(a) parenleftbigg a a+ ε parenrightbigg 2 + a+ ε 2 εa (a + ε) 2 + a+ ε 2 εa (a + ε) 2 + o(ε 2 ) = G(a) parenleftbigg a a+ ε parenrightbigg 2 + εa a+ ε + o(ε 2 ) , where o(ε 2 ) is a collection of terms of order ε 2 or higher. If ε is small, we can ignore o(ε 2 ). Hence we have G(a + ε) ≈ G(a) parenleftbigg a a+ ε parenrightbigg 2 + εa a+ ε . From the formula of the sum of an in?nite geometric series, we know a a +ε = 1 1+ ε a =1? ε a + parenleftBig ε a parenrightBig 2 ? parenleftBig ε a parenrightBig 3 +··· . Ignoring higher order terms of ε,weget a a+ ε ≈ 1? ε a . This gives the following approximations: parenleftbigg a a+ ε parenrightbigg 2 ≈ parenleftBig 1? ε a parenrightBig 2 =1? 2ε a + ε 2 a 2 ≈ 1? 2ε a , εa a+ ε ≈ ε parenleftBig 1? ε a parenrightBig = ε? ε 2 a ≈ ε. Therefore, we can rewrite G(a +ε)as G(a + ε) ≈ G(a) parenleftbigg 1? 2ε a parenrightbigg + ε. Rearranging terms, we have G(a + ε)?G(a)=ε parenleftbigg ? 2G(a) a +1 parenrightbigg . ? G(a + ε)?G(a) ε = ? 2G(a) a +1. 2 If ε → 0, we have the following di?erential equation: G prime (a)=? 2G(a) a +1. Now let us “guess” that G(a)=C + Ba,whereC and B are some constants. Since G(0) = 0, we have C = 0. From the di?erential equation above, we obtain B = ? 2Ba a +1 ? B = 1 3 . Therefore G(a)=E[|X 1 ?X 2 |]= a 3 . Crofton’s method can be used to compute E[max(X 1 ,X 2 )] as well. In this case, there are slight changes in G(a+ε) as shown in Table 2. Following a procedure similar to one we just used, we can show that G(a)=E[max(X 1 ,X 2 )] = 2a 3 . Table 2: G(a + ε) Case Probability of a case G(a + ε)givenacase 0 ≤ X 1 ≤ a,0≤ X 2 ≤ a a a+ε · a a+ε =( a a+ε ) 2 G(a) a<X 1 ≤ a + ε,0≤ X 2 ≤ a ε a+ε · a a+ε = εa (a+ε) 2 a+ ε 2 0 ≤ X 1 ≤ a, a<X 2 ≤ a+ ε a a+ε · ε a+ε = εa (a+ε) 2 a+ ε 2 a<X 1 ≤ a + ε, a<X 2 ≤ a+ ε ε a+ε · ε a+ε =( ε a+ε ) 2 We do not care. 3