4 ms·
Is this roughly saying that when a random choice is more likely to be close to an ideal median (e.g. the center-ish edge in a graph) than the effort in finding
by schuyler2d 4y ago
Is this roughly saying that when a random choice is more likely to be close to an ideal median (e.g. the center-ish edge in a graph) than the effort in finding a median choice (e.g. determining which edges are in the "center" of a graph), then use randomness?
- dellamonica 4y agoThere are lots of techniques that use randomness to show the existence of objects with desired properties. Some of them rely on the "first moment" (expectation) which seems to be what you are saying. These tend to be the simpler ones. A good book on the topic is The Probabilistic Method by Alon and Spencer. To give you some hint of what randomness can get you, look at the most typical random graph model, which for a probability p selects an edge uniformly and independently with that prob. With overwhelming probability, this graph is extremely uniform, meaning that in every set you look (other than then very tiny ones) the density of edges is very close to p. Actually constructing such a graph, either symbolically or by an algorithm is a very hard problem and even the best known results don't get us close to the real random model.