A Waiting time in a Queue using Poisson arrival

[StoneTemplePython]

Btw, I'll tell you that I think the original problem is much easier if we reformulate it, and solve it in stages.

Stage 1: you are offering a prize of $1 multiplied by the time of arrival for K these packets (where each inter-arrival time is i.i.d. and characterized by an exponential distribution). You have no restrictions at all, except only the first K packets get paid. How much do you expect to pay? $1*\frac{K}{\lambda}$

Stage 2: you say you don't like waiting around too much, so you will stop your game and do payouts at time $T_{max}$. If otherwise qualifying arrivals haven't shown up by then, too bad -- they get nothing. So your expected payout is $1* \frac{K}{\lambda } F_{Y{_{K+1}}(T_{max})}$

Stage 3: you're feeling generous and decide that if otherwise qualifying arrivals show up after $T_{max}$, they should still get something just for 'trying'... so in those cases they get paid $T_{max}$. What is your expected payout? $1*p*T_{max} + 1* \frac{K}{\lambda } F_{Y{_{K+1}}(T_{max})}$

- - - - -
Maybe you can try to re-formulate you new variation of the problem into a 3 stage problem like the above?

 

[Mehmood_Yasir]

Hi. Let me check it, before that i forgot to upload this picture for better understanding.
We formulated expectation value of waiting time of first arrival previously which is the longest waiting arrival in the group of arrivals which are aggregated.
Now, I am further interested,
1) to find the expected waiting time of the second, third , fourth ... arrivals. How much they have waited. Surely, their waited time is less than the first arrival.
if we consdier poisson process in which arrivals experience exponential interarrival time with mean 1/lambda. I thought the expected waiting time of the second one should be (1/lambda) less than the first one. But for low lambda, it does not work as i showed in my previous figures. SImilarly, I want to find the expected waiting time of the third one, fourth, fifth and ...

2) secondly, I am interested to see find the average waiting time for an aggregated package. Assume, aggregated segment contains 4 arrivals, then average waiting time would be the waiting time calculated for all of them on average. Just an example , assume 'r' arrivals are aggregated. we want to find the average waiting time due to ;r; arrivals each carrying a different waiting time. out of these 'r', first arrivals will experience longest waiting time and the 'r' th arrival the shortest and in our case, 0 as it will not wait for clock and will get service. So, if we consider uniformly distributed waiting time then on average we can say the average waiting time would be (longest+shortest)/2. for 'r' arrivals being aggregated, shortest is 0 as we receive 'r' arrivals before timeout and we will not waiti and serve immediately. so 'r'th will not wait and average would be (longest+0)/2. And you saw results work very well but only for low lambda they do not match because aggregation not always contain 'r' segment and may contain less arrivals to aggregate.

sorry in the file, its not 1/lambda time, I mean I/lambda less than the first arrival waiting time

 

[StoneTemplePython]

The graphic you attached helps me figure out where your confusion is.

I fundamentally am unhappy, though, that you aren't taking advantage of the fresh start property here. I think the initial arrival you label as 1, should be labeled as 0, or dummy or even ignored. A Poisson process is defined as a counting process, but the fact that there is no clock running until the first arrival in your picture makes me uncomfortable.

My suggestion in your picture is relabel the far left blue arrow as "dummy", then relabel the next arrivals as 1, 2, 3, ..., k.

I think your fundamental problem is that the expected arrivals time between "dummy" and 1 (what you were calling 2) is not $\frac{1}{\lambda}$. For any arrival process where W arrivals occur, if there is a constraint that it only counts if it occurs at a time

$\leq T_{max}$, then you get an expected waiting time of $\frac{W}{\lambda } F_{Y{_{W+1}}(T_{max})}$. This is something I've stated and presented from many different viewpoints-- I really don't know what else to say about this. My concern is you seem to have some formulas in mind but still don't really understand where they came from or when they are or are not appropriate to use. The fact that exponential distributions are memoryless is a very big deal...

From here, I'd simply point out that you have linearity of expectations and overlapping subproblems. You can solve this top down or bottom up. The idea is quite simply that you have a formula $p*T_{max} + \frac{K}{\lambda } F_{Y{_{K+1}}(T_{max})}$ for arrivals, for some K. Try it with say K := 5. Now try it again with K := 4. The first result gives you the expected waiting time when you want 5 arrivals. The second gives you the expected waiting time when you want 4 arrivals. The difference between these two numbers must be the expected waiting time associated with wanting a 5th arrival. (Note it is vital you hold T_max constant for all these calculations.) Put differently if you know the expected waiting time associated with the first 4 arrivals, and the expected waiting time of the 5th arrival, the sum of those two items is the expected waiting time for K=5 arrivals.

It still isn't clear to me what your second question is asking, but I don't think further assistance from me here is helping. Your focus should be on building a foundation in probability in order to understand this.

 

[Mehmood_Yasir]

Thank you. I am sorry, Indeed I took a lot of your time, but I learned alot. I went through the lectures and revisited the way I was calculating the expected waiting time of the $1^{st}$ arrival, and also the way you proposed. Now, first I would like to mention the reason why I used $1/ \lambda$ time difference between $0^{th}$ and $1^{st}$ arrival (in simulator). Actually in simulator, I generated a series of i.i.d interarrival times using exponential distribution. For a particular lambda, inter arrival time of all arrivals is separated by the time difference which is on average 1/lambda, which is the expected value of an exponentially distributed time. Till now, I did not use any clock. Its means that if we have 1 million of packets they all on average will be separated by a distance of $1/ \lambda$. Now consider a timer/stop watch and we should also not the forget the fresh start in our process as you also mentioned. From any position in the list containing inter arrival time of all packets, we will start the clock whenever a $0^{th}$ arrival appears, but this has no impact on the average interarrival time differences, its mean that the expected waiting time till the $1^{st}$arrival is also $1/ \lambda$ on average (i am only talking about simulator) as i will not take care of any clock running or not, and we can repeat the process anywhere in the whole time wherever we will see an aggregated packet is sent and a new fresh start is needed i.e. $0^{th}$ arrival has approached, we will restart the clock. But that's how simulator is working. I was expecting the analytical should also give the same results but your argument of memoryless property is also correct. For analytical, I checked the way you mentioned.

But I used first $k=1$, which means It will give us the expected waiting time when we want $1^{st}$ arrival to approach, and infact it will be the waiting time to get the first arrival. Later, I again used $k=6$, and used the same approach to calculate expected waiting time to get 6 arrivals. from previous results I knew the expecting waiting time to get $1^{st}$ arrival, so i subtracted previous expected value when k=1 from the value when k is kept 6. This will give us the expected waiting time of the first arrival or waiting time to get 6-1 arrivals. I try to compare the results, although with low lambda, results do not fully agree like before, but yes the good thing is that i don't have any risk of negative values as it was before when i just used 1/lambda as a time difference to the first arrival after the oth arrival. I will further investigate it.

For the second question, what I wanted to find is the average waiting time of an aggregated packet due to ;k; arrivals. Simply, how much an arrival in the aggregated packet has waited on average. Its a bit different than the individual waiting times of separate arrivals. Just as an example, let's assume k=6, and assume a clock with timer expiry as 10ms, now e.g., the $0^{th}$ arrival has an expected waiting time 1oms, $1^{st}$ arrival as 8.1ms, $2^{nd}$ arrival 6ms and... $k^{th}$ arrival experiences e.g., 0ms as , I would like to find out the average of all these values which is infact the average waiting time due to k arrivals.
I am sorry once again for taking too much of your time, I am still learning and trying to model it, and hope fully I would be able to learn these guts even more quickly with such kind of assistance. Anyhow thanks alot.

 

[Mehmood_Yasir]

Thank you. I am sorry, Indeed I took a lot of your time, but I learned alot. I went through the lectures and revisited the way I was calculating the expected waiting time of the $1^{st}$ arrival, and also the way you proposed. Now, first I would like to mention the reason why I used $1/ \lambda$ time difference between $0^{th}$ and $1^{st}$ arrival (in simulator). Actually in simulator, I generated a series of i.i.d interarrival times using exponential distribution. For a particular lambda, inter arrival time of all arrivals is separated by the time difference which is on average 1/lambda, which is the expected value of an exponentially distributed time. Till now, I did not use any clock. Its means that if we have 1 million of packets they all on average will be separated by a distance of $1/ \lambda$. Now consider a timer/stop watch and we should also not the forget the fresh start in our process as you also mentioned. From any position in the list containing inter arrival time of all packets, we will start the clock whenever a $0^{th}$ arrival appears, but this has no impact on the average interarrival time differences, its mean that the expected waiting time till the $1^{st}$arrival is also $1/ \lambda$ on average (i am only talking about simulator) as i will not take care of any clock running or not, and we can repeat the process anywhere in the whole time wherever we will see an aggregated packet is sent and a new fresh start is needed i.e. $0^{th}$ arrival has approached, we will restart the clock. But that's how simulator is working. I was expecting the analytical should also give the same results but your argument of memoryless property is also correct. For analytical, I checked the way you mentioned.

But I used first $k=1$, which means It will give us the expected waiting time when we want $1^{st}$ arrival to approach, and infact it will be the waiting time to get the first arrival. Later, I again used $k=6$, and used the same approach to calculate expected waiting time to get 6 arrivals. from previous results I knew the expecting waiting time to get $1^{st}$ arrival, so i subtracted previous expected value when k=1 from the value when k is kept 6. This will give us the expected waiting time of the first arrival or waiting time to get 6-1 arrivals. I try to compare the results, although with low lambda, results do not fully agree like before, but yes the good thing is that i don't have any risk of negative values as it was before when i just used 1/lambda as a time difference to the first arrival after the oth arrival. I will further investigate it.
View attachment 112693
For the second question, what I wanted to find is the average waiting time of an aggregated packet due to ;k; arrivals. Simply, how much an arrival in the aggregated packet has waited on average. Its a bit different than the individual waiting times of separate arrivals. Just as an example, let's assume k=6, and assume a clock with timer expiry as 10ms, now e.g., the $0^{th}$ arrival has an expected waiting time 1oms, $1^{st}$ arrival as 8.1ms, $2^{nd}$ arrival 6ms and... $k^{th}$ arrival experiences e.g., 0ms as , I would like to find out the average of all these values which is infact the average waiting time due to k arrivals.
I am sorry once again for taking too much of your time, I am still learning and trying to model it, and hope fully I would be able to learn these guts even more quickly with such kind of assistance. Anyhow thanks alot.

I made a small mistake in the legends of the above graph. Its reverse. The blue curve depicts analytical results and black shows the results from simulator.

 

[Mehmood_Yasir]

Hi. My apologizes for bothering your again. I spent a lot of time to figure out the reason for discrepancies between sim and ana results for lower values of lambda, while calculating the expected waited time of the second arrival. Unfortunately, its still the same discrepencies for lower values of lambda.
I attached figure. I tried for every way by seeing the possible logic. I kept k=1 (expected time for wanting 1 arrival) and K=2 (expected time for wanting 2 arrivals) and the difference gives the expected time associated for wanting a second arrival. Later, I subtracted the difference from the max. waiting time of first arrival. The outcomes are below. Still not good (magenta and blue curves).

I used another way to find out this delay as shown in the below picture in (2) outcomes are still same.

 

[StoneTemplePython]

Let me try to recap this. You originally asked one and only one question and this was answered many different ways.

You then proceeded two ask two new questions, for which you already have asymptotically correct answer(s).

With respect to your second question, you’ve made statements like “For the second question, what I wanted to find is the average waiting time of an aggregated packet due to k arrivals. ”. There are some major subtleties related to conditioning here, but literally interpreted, with respect to your question, I’d point out:

On page 1 of this thread I mentioned chapter two of:
https://ocw.mit.edu/courses/electri...tochastic-processes-spring-2011/course-notes/

The literally interpreted second question is directly addressed in the notes. The fact is that if you condition on the total number of arrivals at some time period $\tau$, you get a uniform distribution between the arrivals. This has the key to your second question. You’ve said you studied these notes. Did you do any of the exercises at the end? If so, how many? I am getting the feeling that you want answers and don’t want to put in the work.

In summary I have 3 major concerns. (1) There is considerable mission creep going on in this thread. (2) There are serious subtleties related to conditioning that I’m not convinced you appreciate. (3) It’s feeling like you aren’t interested in learning and just want someone else to solve your problems for you.

If you put in the work and solve a majority of those chapter 2 exercises or complete 6.041x, I may change my mind. Otherwise I have little further interest in this thread.

 

[Mehmood_Yasir]

Dear friend, Thanks a lot for your kind advice and help, as well as time.
Its correct I did not solve the exercises given in the notes. But, I read the early part of notes even before this thread. Based on your advice, I revisited again the notes. Thanks for the advice. The good news is for the above figure where I plotted the mistmatch b/w analytical and simulation for the waiting time of the second segment is corrected now. The only issue was that in our case, the expectation value until getting another arrival must be also conditioned for $X<= T_{max}$ as in our case the expectation value cannot exceed $T_{max}$, I recalculated the expectation value with this conditioning and used for calculating the expected waiting time for the second segment.