In general, ignoring survival conditions, staying where you are should increase your odds of being found. A search party will systematically rule out locations where you are not, and you risk moving into a previously searched area or even away from the search party.
There is always a chance you will head towards the search party, or even back towards safety, but assuming there only a handful of directions that lead to safety (an entrance to the area you're lost in for example) then you have a low probability of heading in that direction.
If you can't be sure that a search party is coming, it changes things a bit.
I would refer you to what-if.xkcd.com, but this one is only in the book: If 2 people are dropped on an empty, Earthlike planet, what is the fastest way for them to find eachother? The answer there is to leave a trail of dated markings, resting two days for each day of travel. When you find a new trail you did not create, start following it as fast as possible.
If you realize you are lost the best thing to do is stop, do not keep wandering aimlessly. Take a look around, calmly, and try to determine the best area for some sort of shelter. Look around you for open areas, you want to be seen from the air. Make a big 'X' on the ground using contrasting color material (ie: green branches on snow). Also make something that you can wave in the air. Contrast and movement are the keys here. The international signs of distress are X's and anything in 3's (three lines, three fires, etc.).
The search teams will begin at your last known place (car) or place last seen (someone saw you on a trail) and work out from there. If you keep wandering around you are expanding the search area and decreasing your chances of a quicker rescue. Most searches, weather permitting, are started with a quick air search, followed by a hasty ground search using vehicles, followed by ground search teams. If you can find an open area or a trail, fire road, logging road nearby stay near those. If nothing like that is near you find the nearest 'open' area you can and park yourself there. If you have to relocate to a better position (necessary resources) leave obvious 'sign'. Broken branches, arrows made using rocks or sticks, showing which direction you went will help searchers looking for you. Be obvious and large with your 'sign', don't assume someone will see it, make it large enough that someone can't possibly miss it.
Anything reflective (mirror, watch, cell phone glass screen) can flash sunlight for miles. At night, anything than can create light (lighter, flashlight, glow stick) can also be seen for long distances. The thing to remember is people will be looking for you so make it easier for them to find you. Shout, wave something colorful, smack rocks together, anything...just don't sit around and play 'hide and seek'.
Source: Current Search and Rescue volunteer.
Vancouver, BC has inhospitable and dangerous wilderness areas literally less than twenty minutes' drive from its downtown core. Consequently, ill-prepared hikers who wander off marked trails and get themselves lost, or worse yet too injured to backtrack, are very common.
A large preponderance of those needing to be rescued are visitors who incorrectly assume the local mountains are just tamed urban parks, because they look so benign and inviting from the highrise hotel window. Not so; once an unaware or inexperienced person steps off the parking lot gravel and into the treeline, things can start going wrong for them very, *very* quickly - especially if they head out in flipflops and shorts, as some actually do. But to be fair, locals in Goretex and trail boots also need to be retrieved, sometimes.
[North Shore Rescue](http://www.northshorerescue.com/
), one of the world's busiest volunteer rescue organizations, gets nearly 3 calls a week, year round, to find or rescue people stuck in the bush, and will field as many as five calls a *day* over some summer weekends. Last year they spent over 10,000 rescuer hours on searches and recoveries. Often these SAR callouts require multi-day searches by a dozen or more highly trained and well-equipped volunteers; reports of missing hikers are typically made late in the day, often leaving only a few crucial hours to rally and search before nightfall requires ops to be suspended until first light. In short, these guys and gals are world experts at finding people in technically challenging, very dangerous terrain that is often heavily overgrown and lethally steep, then getting them out safely.
[North Shore Rescue unequivocally recommends *staying where you are!*](http://www.northshorerescue.com/education/avoid-getting-lost/
If where you are is safe, and has open visibility, then stay put. Water begets plant growth though, and you never want to be away from it, so observe the rule of threes.
3 minutes without air.
3 hours without shelter.
3 days without water.
3 weeks without food.
If your current location provides water and shelter, it'll provide food. As previous commenters have said, overhead coverage is a double-edged sword. It's shelter but it blocks airborne search and rescue. If you have to travel a few minutes to get water and food, it's worth it to camp on the edge of a tree line.
This is actually a fairly active area of research in distributed computing and other adjacent areas. There are various different versions of this problem:
k agents on a graph on n nodes. Agents can or cannot meet along edges. Agents do or do not have a synchronised clock. Nodes can or cannot be marked or distinguished. The agents can or cannot decide a strategy ahead of time/are or are not distinguishable.
Two agents are one mile apart on an infinitely long road or river, but neither knows the direction of the other. Same parameters as above, plus one other - the road/river has a consistent orientation (e.g. downstream).
The continuous version of this problem has applications in robotics, and also in the search for extra terrestrial life!
To answer your question, I will tell you about one version. Sometimes this is called the "Mozart Cafe" problem. Two people agree to meet at the Mozart Cafe, in Vienna, at sunset. Unfortunately there are several Mozart Cafes in Vienna, and furthermore they forgot to specify the day. So what is the best strategy? It turns out that when there are exactly 3 cafes, the best thing to do is:
* On day 1, pick a random Mozart Cafe and go there.
* On all subsequent days, flip a coin - if it comes up heads, go back to the same cafe. Otherwise switch (flipping a coin again to decide which to choose)
When I heard about this problem, I think the 4 cafe case was still open, but I seem to recall it has been solved now - I can't find a reference immediately though, this problem does have several different names in the literature. I know that Andrzej Pelc is very active in this field, and he refers to "rendezvous" and "gathering" problems.
But you also need a purpose in order to survive- there was a plane crash in South American where a 16-year-old girl with no survival training started walking and was rescued 11 days later. Everyone else who survived the crash stayed put and died.
Ok let's break this down: your lost, there is a search party looking for you but they don't know where you are or what your plan was/is/is going to be. Best way to be found as quickly as possible? Signal fire. Ignoring the environmental extremes of igniting a forest fire (and killing yourself in the process) or not being able to start a fire due to monsoon rains or tundra/desert devoid of vegetation to burn. Mathematically speaking starting a fire and staying by it is going to increase your chances of meeting a search party exponentially. While as wandering will decrease the chances of meeting a search party at all. Also, while wandering is the only time you would have to factor in relative speeds. If you become the destination and sit by a fire (increasing your own survival odds while you wait, another thing to factor into rescue) your odds should only depend on the skill of the rescue party, its size and how long they search for. It's a big world, I listen very closely to advice from the North Shore Rescue in Vancouver BC. As u/theartfulcodger correctly pointed out they are one of the worlds best and busiest. This is actually not their top advice. We have very severe forest fire seasons here in greater Vancouver as well as BC in general. But this would be a more "mathematically" appropriate response rather than a practical survival/rescue response. ...not that I did or am very good at much math. But the honest answer to the math on this is that you will never be able to identify all the variables of this problem to begin with.
And just to throw a little practical survival/rescue tip in here too (something North Shore Rescue or any SAR team would love to hear/see more people doing). Make a plan within your skill/ability limits and stick to it. Where your going, with who, to do what, with what gear. Leave copies of that plan with a family member and another point of contact (friend/work/neighbour) with a return by time and an activate SAR time on it.