Saturday, February 24, 2007
The problem of unit in the relationship between backorder and waiting time
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 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.