Trajectory detection in noise - the probability of at least one random point being within epsilon distance of the trajectory?
So I have a sequence of n_t frames and each frame has n dots with coordinates (x_n,y_n). Most of the points are drawn at random, but there are two points are actually not random and move with constant speed along the whole sequence. My goal is to find these two trajectories. It did this in matlab and it was fine (the teacher suggested doing it by looping through all points in the first frame and all points in the last frame, and test the possibility that these two points are actually the first and last positions of a point moving at constant speed in the sequence.)
Now my problem is to find and expression for the probabilities of at least one random point being within epsilon distance of the trajectory? We assume that the random points in the sequence are all independent and their coordinates follow uniform distributions in [0, 1].
What is the probability, depending on n_t, n and epsilon, that given a straight trajectory, there is at least one random point at each time t which is within epsilon distance to the trajectory and what is the maximal value for epsilon which ensures that we have at least 95% probability that no false detection will occur when looping through all initial and final points?
I have started by thinking that the probability of a single random point not being in a circle with epsilon radius from a point on the trajectory is 1-epsilon^2*pi but I haven't gotten much further, is anyone able to give me some insight that can help me move along with this problem?
Answer
- The questioner was satisfied with and accepted the answer, or
- The answer was evaluated as being 100% correct by the judge.
1 Attachment
Cmartman
Can you clarify what you mean by a frame? It is a 1*1 square?
Is the locations of those two points moving with constant speed fixed with respect to the frame?
The question is not clear to me. This is what I understand: For each timestamp (frame) t (t = 0, 1, ..., T) there are n points in [0,1]x[0,1]. n-2 of those points are chosen uniformly on [0,1]x[0,1] and independently of other points and other frames (times). 2 other points determine two different lines on [0,1]x[0,1] across time. They will basically have a very strong linear correlation with their counterparts across time but you don't know which points are those. and two points There are
My questions are: what if a straight line hits a boundary of [0,1]? Or will this never be the case? Also, what is your algorithm for detecting lines? Do we have to work with your same solution or can we come up with one of our own?
Yes there are n independent points on [0,1]x[0,1] and in each timestep (frame) we generate new random ones but infact 2 points in each frame are not actually random. The straight line could in theory hit the boundary but in this case it would only happen in the last frame so it wouldn't matter for the solution of the problem. The points also don't have to move with a constant speed and they can stray a little from a straight trajectory so that is why we need this probability calculation.
And no you don't have to work with my solution, but the only thing I have so far is the 1-epsilon^2*pi thing and I am pretty sure that it should be in there. I have done the algorithm and it works fine.
Could you give more detail on the testing procedure you use as you're 'looping through all the points'? It sounds like in your second question, finding a max epsilon such that you have (effectively) a .95 alpha level test, that you would like us to work with your testing procedure. Otherwise, your first question may be the only question I / we can answer so far.