Optimal speed for approaching red light to maximize velocity with non-uniform probability

holder-inequalityoptimal controloptimizationordinary differential equationsstatistics

Problem statement

When I cross red lights, my goal is to being going as fast as possible when the light turns green.

I am at distance $D$ from a traffic light when it turns red.

Let the time length of the red light be $t_{red}$ with probability density $ p$ on $[0,T_{max}]$.

My velocity $v(t)$ must be such that $\int_{0}^{T_{max}} v(t)dt \leq D$. ( I can't cross the light while it's red.)

Given any $C$, I would like to find $v$ to maximize $E(v(t_{red}))$ given $Var(v(t_{red})) < C$.

My best solution so far

What follows is my best family of solutions so far. I can show that it is optimal for $C=0$ and $C=\infty$ I would appreciate your help confirming or denying it is optimal for other values of $C$.

Let $F(a) = \int_0^{T_{max}}p^a(t)dt$

Note that $F(0)=T_{max}$ and $F(1)=1$

Let $v_a(t) = \frac{D}{F(a)}{p^a(t)}$.

We have

$\int_0^{T_{max}}v_a(t)dt=D$

$E(v_a(t_{red}))=\frac{D}{F(a)}\int_0^{T_{max}}p^{a}pdt=D\frac{F(a+1)}{F(a)}$

$E(v_a(t_{red})^2) =\frac{D^2}{F(a)^2}\int_0^{T_{max}}(p^a)^2pdt= D^2\frac{F(2a+1)}{F(a)^2} $

$Var(v_a(t_{red}))= D^2\frac{F(2a+1)-F(a+1)^2}{F(a)^2}$

To get a feel for the expected value and variance of this solution, I plotted it out for a simple example:

enter image description here


I can show you that this is optimal for at least two values of $a$.

$a=0$

if $a=0$ then $E(v_0(t_{red})) = D\frac{F(1)}{F(0)}=\frac{D}{T_{max}}$.

Also $Var(v_0(t_{red})) = D\frac{F(1)-F(1)}{F(0)}=0$.

This is optimal for $C=0$ since if $C=0$ then $v$ is constant, and must satisfy $\int_{0}^{T_{max}} v(t)dt \leq D$ while trying to maximize $E(v)$.

Side note: This is also the solution of the problem if you assumed uniform probability distribution from the get-go (which for practical purposes is a fair assumption).

$a=\infty$

I can also show that this is optimal for $a=\infty$ in this case $C=\infty$ and

this case this is simply the extremal Holder's equality

Holder's inequality says:

$D||p||_{\infty}=sup(\int_0^{T_{max}} vpdt: ||v||_1=D)$

and since $v_{\infty}$ essentially approaches a delta function around the supremum with weight $D$ we hit this upper bound at $v_{\infty}$

Side note: this solution is hilariously nonphysical. The driver waits for the moment where the light is most likely to turn and accelerates to an astronomic velocity towards the light for a split second and the halts to a dead stop. Thats what happens when we allow infinite variance.

Question

Of course I have just proved the two easiest cases. I would love to show that for any given $C$ the $v_a: Var(v_a) = C$ will maximize $E(v)$ for all $Var(v)\leq C$

What I've tried

One method I have been able to think of for proving optimality is to show
if

$g: E(g(t))=0, \int_0^{T_{max}}g = 0$

then

$E(v_a^2) \leq E((v_a+g)^2) \implies Var(v_a)\leq Var(v_a+g)$.

not much came out of this approach for me.

One promising approach

considering instead something like $E(v_ag) \geq E(v_a)$ and $ \int_0^{T_{max}}v_ag = \int_0^{T_{max}}v_a$ the problem turns into the following:

if $ \int_0^{T_{max}}p^ag = \int_0^{T_{max}}p^a$ and $ \int_0^{T_{max}}p^{a+1}g \geq \int_0^{T_{max}}p^{a+1}$

then does

$ \int_0^{T_{max}}p^{2a+1}g^2 \geq \int_0^{T_{max}}p^{2a+1}$ ?

this is nice as:
$p^{a}gp^{a+1}g= p^{2a+1}g^2$ and $p^{a}p^{a+2}= p^{2a+1}$.

So we almost want a rule like

$\int a \geq \int b, \int c = \int d \implies \int ac \geq \int cd$ under our assumptions.

Best Answer

Here’s a solution using variational calculus (though there isn’t really any calculus involved, since nothing depends on the derivative of $v$). As far as I can tell you don’t require $v$ to be non-negative, and indeed the solutions are sometimes negative.

We can initially replace the inequalities involving $D$ and $C$ by equations; once we have the solution for given $D$ and $C$, we can then maximize with respect to $D$ and $C$ subject to the inequalities.

Trying to directly formulate this as a variational problem with constraints runs into the problem that the variance isn’t linear and contains a square of an integral. We can get around this by considering the dual problem of minimizing the variance given $\mathsf E[t_{\text{red}}]$.

So assume $D$ and $E=\mathsf E[t_{\text{red}}]$ are given. Then we want to minimize

$$ \int v^2p\,\mathrm dt $$

subject to

$$ \int v\,\mathrm dt=D $$

and

$$ \int vp\,\mathrm dt=E\;. $$

Introducing Lagrange multipliers for the constraints and varying

$$ \int\left(v^2p-2\lambda vp-2\mu v\right)\mathrm dt $$

yields

$$ 2vp-2\lambda p-2\mu=0 $$

and thus

$$ v=\lambda+\frac\mu p\;. $$

Substituting into the constraints yields

$$ \int\left(\lambda+\frac\mu p\right)\mathrm dt=D\;,\\ \int\left(\lambda+\frac\mu p\right)p\,\mathrm dt=E $$

and thus

$$ \lambda T_{\text{max}}+\mu I=D\;,\\ \lambda+\mu T_{\text{max}}=E\;, $$

with

$$ I=\int\frac{\mathrm dt}p\;. $$

The Lagrange multipliers can be determined from this linear system of equations and substituted into the solution.

We recover your solution for $a=0$ and $C=0$ in the case $\mu=0$, with $v=\lambda=E=\frac D{T_{\text{max}}}$.

We don’t recover your solution for $a=\infty$ and $C=\infty$, I think because you implicitly used $v\ge0$ in deriving it.

But if $p$ is positive everywhere, there should be a neighbourhood of solutions around the solution for $C=0$ that have $v$ positive everywhere, and it doesn’t have the form you were hoping for, so I’m afraid this may be somewhat disappointing (unless I made a mistake...).

Related Question