Thread: what is the best method for police officer to use to determine which way to go?

A police officer is located in the block shown in the pictjure. He visits the corrnors numbered 1 to 6. He stays at a cornor for an hour, and then decides to go to another one or stay at the one he's currently at. Since randomly selectnig has a low steady state (if numbers are approximated to a couple of decimals) it's not good to randomly choose where to go next. What stratgey should the police officer use so that people can't predict where he will be? I was thinking of things like, not allowing the police officer to stay in the same spot, and also always making the path to 4 heavier wated, for exampel there's a 0.5 chance he'd go to 4 because 4 has many routes he can go to from there. That's no good because then people can expect him to be at 4

There's some information missing - does he have to go to an adjacent corner, or for example, can he go from corner 2 to corner 6? Also, I don't see what you're trying to optimize - do you want him to divide his time as equally as possible between the corners, or do you want him to be as unpredictable as possible?

If you want him to be unpredictable, you have to choose randomly with equal probabilities from among all the possibilities. I think that can be demonstrated by example. Suppose you require him to move at each hour - he can't stay in the same place. Then someone (a criminal?) could be completely safe by always moving to the place he moved from. No matter what scheme the policeman cooks up, the criminal can better his odds because he can (at least partially) predict where the policeman will be.

The problem only becomes interesting if he has to move to an adjacent corner, and you want him to spend as close to 1/6 of his time as possible on each corner.

Here is one way to spend exactly 1/6 of his time on each corner. Starting from corner 4, choose from the following options with equal probability:
1. Go to corner 3, stay there 5 hours, and go back to corner 4.
2. Go to corner 6, stay there 5 hours, and go back to corner 4.
3. Go to corner 1 (1 hour), corner 2 (3 hours), corner 5 (1 hour), then back to corner 4.
4. Go to corner 1 (2 hours), corner 2 (1 hour), corner 5 (2 hours), then back to corner 4.
5. Go to corner 5 (2 hours), corner 2 (1 hour), corner 1 (2 hours), then back to corner 4.
If you take all five tours, you spend 5 hours in each corner.

I'm not sure that answers your question. Please post again if you still need help.

Optimize as to be as unpredictable as possible.
I need to find the transition matrix for the strategy.
The police can only move to adjacent squares or stay on the same one. So no he can't go from 2 to 6.

Ok. He wants to be as unpredictable as possible, and he can only go to adjacent squares or stay put.

So his best strategy is to choose randomly between his available choices, giving equal probablility to each choice. For example, if he is at corner 1, he should stay put 1/3 of the time, go to 2 1/3 of the time, and go to 4 1/3 of the time. Anything else would be "more predictable" in the sense that there is a corner that is "safer" than the other two (for the criminal, that is). Of course, the criminal is completely safe at 3, 5, or 6.

Is that what you're looking for?

sort of. with the method you described isn't it not very good because it reaches the steady state matrix very fast?

I guess I don't see what you're looking for.

If you have a transition matrix , then the steady state vector is defined by the equation . If you then define a sequence of vectors starting with with having one element 1 and the rest 0, and the rest defined by , it sounds like you're looking for a that gives a sequence that approaches as slowly as possible.

But it's easy to define transition matrices that never reach a steady state vector. A simple example is "always go to corner 4 or 5, if on 4 or 5 then switch to the other" The steady state is (0 0 0 0.5 0.5 0), but the sequence of vectors will oscillate between (0 0 0 1 0 0) and (0 0 0 0 1 0).

Could you provide some background (what class are you in? what are you studying?) Or maybe a similar problem that is easy to solve, so you can show me what you want the solution to look like?

Thanks,
Hollywood

This was for a linear algebra class and the question came from a lab assignment. The lab provided an introduction Markov chains, and I am new to transition/steady state matrices.

In short the question asks develop a method for the police to use so that he is (close to) equally likely to be found at all squares. Find the transition matrix for this method.

I have handed in the assignment so I can't be very specific at the moment. When I get it back I can post the question and the surrounding information. May I send you a private message once I get back my assignment and post the question?

I know it screws people up when the entire question wasn't posted, but the part of the question I was stuck on made refrence to a number of previous problems and there result

Yes, please do post the question and surrounding information. And the answer, too, if you get it. I get an e-mail if you post in this thread, so a PM is redundant for just telling me that something new is here.

It still seems like some variation of my first answer works, but I'll wait for the additional details.

Ok here it is. Sorry it took me so long. could you start by telling me how to do 2 b)? Sorry that this is so big...would you like me to change it some how?

Yeah, those scans are really big, but it doesn't bother me. I asked about the best way to post those large files here:

http://www.mathhelpforum.com/math-he...tml#post481556

Anyway, on to question 2(b). You got the idea on 2(a), just slipped up on the one column.

For 2(b), I think the idea is to start with:



and repeatedly apply until you reach a steady state. After all, it is a lab, right?

The vectors should get closer and closer to the solution of , which is:



There is, of course, no way you can intelligently answer 2(c) without getting 2(b), so, um, good job getting the 2 points. But with the correct answer to 2(b), you can see that in the steady state vector, element 4 is larger at the expense of elements 3 and 6. And you would expect the policeman to be at corner 4 more since it's easier to get to, and corners 3 and 6 less since they're hard to get to. So this strategy is not "good" in the sense that he should be spending the same amount of time on each corner ("good" is not actually defined until question 3).

In 2(d), you're supposed to start with and keep applying . You can see the two are equivalent even though matrix multiplication is non-commutative, right? Anyway, after multiplying by P enough times, it converges on a matrix Q, which is just the steady state vector repeated in 6 columns.

Good job getting the 2 points for 3(a). Of course, what you wrote is the goal of the strategy, but how do you achieve it? Check out my solution in the second post in the thread. If instead of saying "stay 5 hours at x, then go to y", you say "stay at x with probability 5/6 and go to y with probability 1/6", you have an optimal strategy, I think. Try setting up the transition matrix for it and see if approaches the all-(1/6) matrix, or take a random vector and multiply it by P a whole bunch of times and see if you get the all-(1/6) vector.

I suppose you've moved on to new material and don't have time for this any more. Let me know if you do any more work on the problem.

It's been nice working with you.

- Hollywood

Originally Posted by superdude

Ok here it is. Sorry it took me so long. could you start by telling me how to do 2 b)? Sorry that this is so big...would you like me to change it some how?

OK, it's pretty clear that your questions are from an assignment that most likely counts towards your final grade. MHF policy is to not knowingly help with such questions - it's meant to be your own work.

Thread closed.

Originally Posted by pm from superdude

I believe this thread has wrongfully closed. The question is from a homework assignment however it allready has been marked, hence the red ink on the page.

If the assignment has been marked then you should make an appointment with your teacher to discuss the things about this assignment that you still don't understand and get additional feedback. You should also ask your teacher for the solutions.

Your teacher is paid to do this as part of his/her job - it's not the role of unpaid volunteers at MHF to do his/her job.

You can continue this discussion with me via pm if you want.