Further thoughts on traffic lights
Dec. 1st, 2012 07:13 pmYes, really. Also, I've edited the previous traffic-light entry to change the meaning of n; now n is the number of road segments, and n+1 is the number of traffic lights. I decided I liked it this way better.
Anyway! So a lot of these problems I posed about traffic lights seem... well, not actually hard. But harder than I want to think about in my spare time right now. Things seem to depend a lot on things like is t/(T1+T2) rational and blech.
Still, here's some more thoughts.
1. I guess the lights being "stacked against you" could just mean you hit every red light (since that would be annoying by itself). Call such a configuration "bad". Then we can also consider questions like, what's the probability that the reverse of an optimal configuration is a bad configuration?
2. Obviously t, T1, and T2 can be scaled without affecting things, so I'm going to apply the normalization that T1+T2=1. So we have 0<T1<1 (I'm going to disallow the cases where the light is always green or always red), and since t only matters modulo T1+T2, we can assume 0≤t<1 (nothing wrong with the car being infinitely fast). This allows us to also talk about picking T1 and t randomly, so we can consider what happens with generic ones.
3. I don't think we really want to consider so much what happens for given n so much as we want to consider what happens for *large* n (if n=0 things are pretty stupid). So to the extent I've been thinking about this stuff I've been thinking in terms of large n.
4. The one of the problems I've mentioned I have really thought about is the probability of optimal reversing to optimal; this one's not too hard. Not going to bother to reproduce the reasoning here, but it is pretty unlikely for optimal to reverse to optimal: Under the assumptions above, unless t=0 or t=1/2, as n→∞, the probability approaches 0. (So for generic t and T1, it approaches 0.) For t=0, obviously optimal always reverses to optimal, and for t=1/2, there is no one long term behavior, but rather it depends on the parity of n; for n even optimal always reverses to optimal, but for n odd the probability goes to 0.
5. Also for generic t and T1 and large n, pessimal will not reverse to optimal. At least, for one formalization of that statement. :P
I think that's really all I have to say on the matter for now.
-Harry
Anyway! So a lot of these problems I posed about traffic lights seem... well, not actually hard. But harder than I want to think about in my spare time right now. Things seem to depend a lot on things like is t/(T1+T2) rational and blech.
Still, here's some more thoughts.
1. I guess the lights being "stacked against you" could just mean you hit every red light (since that would be annoying by itself). Call such a configuration "bad". Then we can also consider questions like, what's the probability that the reverse of an optimal configuration is a bad configuration?
2. Obviously t, T1, and T2 can be scaled without affecting things, so I'm going to apply the normalization that T1+T2=1. So we have 0<T1<1 (I'm going to disallow the cases where the light is always green or always red), and since t only matters modulo T1+T2, we can assume 0≤t<1 (nothing wrong with the car being infinitely fast). This allows us to also talk about picking T1 and t randomly, so we can consider what happens with generic ones.
3. I don't think we really want to consider so much what happens for given n so much as we want to consider what happens for *large* n (if n=0 things are pretty stupid). So to the extent I've been thinking about this stuff I've been thinking in terms of large n.
4. The one of the problems I've mentioned I have really thought about is the probability of optimal reversing to optimal; this one's not too hard. Not going to bother to reproduce the reasoning here, but it is pretty unlikely for optimal to reverse to optimal: Under the assumptions above, unless t=0 or t=1/2, as n→∞, the probability approaches 0. (So for generic t and T1, it approaches 0.) For t=0, obviously optimal always reverses to optimal, and for t=1/2, there is no one long term behavior, but rather it depends on the parity of n; for n even optimal always reverses to optimal, but for n odd the probability goes to 0.
5. Also for generic t and T1 and large n, pessimal will not reverse to optimal. At least, for one formalization of that statement. :P
I think that's really all I have to say on the matter for now.
-Harry
