URBAN OPERATIONS RESEARCH PROFESSOR ARNOLD I BARNETT LECTURE NOTE OF 9/24/2001 PREPARED BY JAMES S. KANG Crofton's Method Let XI and X2 be independent random variables that are uniformly distributed over the interval [0,a]. We are interested in computing EllX1-X2l. For instance, in an urban setting, X1 and X2 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, EllX1-X2l. We may solve this question using a joint distribution of X1 and X2, but Crofton's method is quite useful for the question Let G(a)=ElX1-X2l. Now consider the following question: If the interval were [ 0, a+e where e is small, what would G(a+e) be? Table 1 summarizes G(a+a) depending on the locations of X1 and X Table 1: G(a+e) Probability of a case G(a+e)given a case a=(a a<X1≤a+E,0≤X2≤a (a+e) a 0≤X1≤ X2≤a+E <X1<a+E,a<X2≤a+E We do not care Figure 1: Case where0≤X1< a and a<X2≤a+e Note that we did not specify G(a +a) for the case where a< Xi <a+E and a< X2 <a+E, because the probability of that case,(_2)2, is negligible when e is small ("If e is small, e2 To compute G(a+a) from Table 1, we invoke the total expectation theorem(or the conditional xpectation rule). When a sample space is divided into A1, A2, .. An that are mutually exclusive and collectively exhaustive events, the expected value of a random variable Z is computed by
Urban Operations Research Professor Arnold I. Barnett Lecture Note of 9/24/2001 Prepared by James S. Kang Crofton’s Method Let X1 and X2 be independent random variables that are uniformly distributed over the interval [0, a]. We are interested in computing E[|X1 − X2|]. For instance, in an urban setting, X1 and X2 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[|X1 − X2|]. We may solve this question using a joint distribution of X1 and X2, but Crofton’s method is quite useful for the question. Let G(a) ≡ E[|X1 − X2|]. Now consider the following question: If the interval were [0, a + ε] where ε is small, what would G(a+ε) be? Table 1 summarizes G(a+ε) depending on the locations of X1 and X2. Table 1: G(a + ε) Case Probability of a case G(a + ε) given a case 0 ≤ X1 ≤ a, 0 ≤ X2 ≤ a a a+ε · a a+ε = ( a a+ε )2 G(a) a<X1 ≤ a + ε, 0 ≤ X2 ≤ a ε a+ε · a a+ε = εa (a+ε)2 a + ε 2 − a 2 = a+ε 2 0 ≤ X1 ≤ a, a<X2 ≤ a + ε a a+ε · ε a+ε = εa (a+ε)2 a + ε 2 − a 2 = a+ε 2 a<X1 ≤ a + ε, a<X2 ≤ a + ε ε a+ε · ε a+ε = ( ε a+ε )2 We do not care. 0 a a+ε X1 X2 Figure 1: Case where 0 ≤ X1 ≤ a and a<X2 ≤ a + ε Note that we did not specify G(a + ε) for the case where a<X1 ≤ a + ε and a<X2 ≤ 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 A1, A2,... ,An that are mutually exclusive and collectively exhaustive events, the expected value of a random variable Z is computed by 1
EZ)=∑E(Z|A)P( Using the total expectation theorem, we obtain a+e Ea G(a+e=G(a) a+ (a+E)2 2(a+e)2+o(e2) G(a) o(e2) a+ a+E where o(e )is a collection of terms of order e or higher. If E is small, we can ignore o(e ) Hence we have G(a+)≈G(a From the formula of the sum of an infinite geometric series, we know no ing higher order terms of E, we get E This gives the following approximation 2E ≈E(1--)=E--≈E Therefore, we can rewrite G(a+a)as G(a+e)≈G(a Rearranging terms, we have G(a+a-G(a) 2G(a) G(a+e)-G(a)
E(Z) = n i=1 E(Z | Ai)P(Ai) . Using the total expectation theorem, we obtain G(a + ε) = G(a) a a + ε 2 + a + ε 2 εa (a + ε)2 + a + ε 2 εa (a + ε)2 + o(ε2) = G(a) a a + ε 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) a a + ε 2 + εa a + ε . From the formula of the sum of an infinite geometric series, we know a a + ε = 1 1 + ε a = 1 − ε a + ε a 2 − ε a 3 + ··· . Ignoring higher order terms of ε, we get a a + ε ≈ 1 − ε a . This gives the following approximations: a a + ε 2 ≈ 1 − ε a 2 = 1 − 2ε a + ε2 a2 ≈ 1 − 2ε a , εa a + ε ≈ ε 1 − ε a = ε − ε2 a ≈ ε . Therefore, we can rewrite G(a + ε) as G(a + ε) ≈ G(a) 1 − 2ε a + ε . Rearranging terms, we have G(a + ε) − G(a) = ε −2G(a) a + 1 . ⇒ G(a + ε) − G(a) ε = −2G(a) a + 1 . 2
If E-0, we have the following differential equation 2G(a) Now let us"guess"that G(a)=C+ Ba, where C and B are some constants. Since G(0)=0,we have C=0. From the differential equation above, we obtain Therefore G(a)=ElX1-X2ll Crofton's method can be used to compute E max(X1, X2) as well. In this case, there are slight changes in G(a+a) as shown in Table 2. Following a procedure similar to one we just used, we can show that G(a)=Emax(X1, X2) Table 2: G(a+a) Probability of a case G(a+e) given a case 0≤X1<a,0≤X2≤a +·a+=(a+g) G(a) a<X1<a+E,0<X2<a ateate (a+e) 2 0≤X1 X2≤a+6az:a a a<X1≤a+E,a<X2≤a+E (n)2 We do not care
If ε → 0, we have the following differential equation: G (a) = −2G(a) a + 1 . Now let us “guess” that G(a) = C + Ba, where C and B are some constants. Since G(0) = 0, we have C = 0. From the differential equation above, we obtain B = −2Ba a + 1 ⇒ B = 1 3 . Therefore G(a) = E[|X1 − X2|] = a 3 . Crofton’s method can be used to compute E[max(X1, X2)] 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(X1, X2)] = 2a 3 . Table 2: G(a + ε) Case Probability of a case G(a + ε) given a case 0 ≤ X1 ≤ a, 0 ≤ X2 ≤ a a a+ε · a a+ε = ( a a+ε )2 G(a) a<X1 ≤ a + ε, 0 ≤ X2 ≤ a ε a+ε · a a+ε = εa (a+ε)2 a + ε 2 0 ≤ X1 ≤ a, a<X2 ≤ a + ε a a+ε · ε a+ε = εa (a+ε)2 a + ε 2 a<X1 ≤ a + ε, a<X2 ≤ a + ε ε a+ε · ε a+ε = ( ε a+ε )2 We do not care. 3