Saturday, February 24, 2007

The problem of unit in the relationship between backorder and waiting time

The formula for the relationship between backorder and waiting time is
V[B]=lambda E[BW] + lambda^2 V[BW]

I think there is exact same formula in queueing theory about the number in the queue and waiting time. But the puzzle to me is the match of unit. Suppose the unit of B, lambda, BW are item, item/day, day. V[B]=item^2, lambda E[BW] = item and lambda^2 V[BW]=item^2.

If it was me to derive this formula, I would throw it into garbage after this check. But sometimes, we cannot trust common sense.

Tuesday, February 20, 2007

The difference and similarity between Poisson and BM

The more I learn about BM, the more I feel there are strong connection between Poisson and BM. Last week, I ask a question. If we discrete Poisson process to small time interval, it behaves exactly as random walk with probablity lamda*h up by one and 0 otherwise. And counterpart of BM in discrete world is also random work with probability 0.5 up by 1 and probability 0.5 down by 1. Then I ask a question, what if we change the measure just like that we can change the BM with drift to BM without drift. Answer is obvious no, there are several differences.

  • discrete BM, up and down probability is fixed. the only scale factor is step size. But the scale factor of poisson process is probability up and step size is fixed
  • when we change the measure, we require that two probability measuresare equivalent which means the null space is the same. The null space of discrete one step of randome walke is R/{-1,1}. But poisson is R/{0,1}.

But when I ask Professor what is discrete case of BM with drift. Is it with the symmetric step size but different probability or different step size but the same probability or both or does not matter. I have not get answer yet.

Wednesday, February 07, 2007

IP homework is way too hard

The second set of homework takes me two days with 16+ hours to finish and without leaving a logic hole.
The last two logic gaps I filled just now are
1. LP relaxation of TSP formulation with subtour elimination constrainted is strictly contained in TSP formulation with subtour elimination constrainted replaced by $u_i-u_j-nx_{ij} \leq n-1$. This invovle how to scale up the problem then scale down.
2. Find as many affine independent points as possible for $P={x \in R^+ | \sum^n_{i=1} x_{ij}=1 for i=1,...n and \sum^n_{j=1} x_{ij}=1 for j=1,...n}$. It would be easy to see the rules by beginning with n=3 and 4.

In homework 1 of IP class, the following question is challenging.
1. show that $max{x_1 − \sqrt(2) x_2 | 1 \leq x1 \leq \sqrt(2) x_2 and x_1, x_2 is integer}$ is feasible and bounded, but has no optimal solution. I use the contradiction to show that there is no optimal solution.