Randomized algorithms - Revision history

Tom.Reding: +{{Redirect category shell}} using AWB

2017-06-06T15:19:22Z

← Previous revision		Revision as of 15:19, 6 June 2017
Line 1:		Line 1:
	#~~redirect~~ [[Randomized algorithm]] ~~{{R from plural}}~~		#REDIRECT [[Randomized algorithm]]

			{{Redirect category shell\|1=
			{{R from plural}}
			}}

GregorB: {{R from plural}}

2010-03-09T19:34:21Z

← Previous revision		Revision as of 19:34, 9 March 2010
Line 1:		Line 1:
	#redirect [[Randomized algorithm]]		#redirect [[Randomized algorithm]] {{R from plural}}

Sycthos: Undo revision 97799966 by 217.155.230.226 (talk)

2007-01-01T21:53:02Z

Undo revision 97799966 by 217.155.230.226 (talk)

← Previous revision		Revision as of 21:53, 1 January 2007
Line 1:		Line 1:
			#redirect [[Randomized algorithm]]
	<pre>

	===============================
	_
	/ \
	/ \
	/_ _\
	_ _____\|_\|___
	\| \| / _________ \
	\| \| \| (___ \| \| \| \|
	\| \| \___ \\| \| \| \|
	\| \|________) \| \|__\| \|
	\|___________/\|_____/
	Liquid Syko Destruction

	-------------------------------

	LSD pwns j00!! Drugz is gudz.

	-------------------------------

	Request to join LSD by
	posting a Usenet article
	entitled 'Attn: L.S.D' in the
	'alt.anonymous.messages'
	newsgroup.

	-------------------------------

	Luv LSDude, echelon77 and
	FaTmAn.

	Greetz to FFF, THC and all the
	l33t dudes out there!

	-------------------------------

	Some people hack it,
	Some others crack it,
	We ransack it!

	-------------------------------

	!BLOW.IT.UP!

	===============================

	</pre>

217.155.230.226 at 21:50, 1 January 2007

2007-01-01T21:50:51Z

← Previous revision		Revision as of 21:50, 1 January 2007
Line 1:		Line 1:
			<pre>
	#redirect [[Randomized algorithm]]

			===============================
			_
			/ \
			/ \
			/_ _\
			_ _____\|_\|___
			\| \| / _________ \
			\| \| \| (___ \| \| \| \|
			\| \| \___ \\| \| \| \|
			\| \|________) \| \|__\| \|
			\|___________/\|_____/
			Liquid Syko Destruction

			-------------------------------

			LSD pwns j00!! Drugz is gudz.

			-------------------------------

			Request to join LSD by
			posting a Usenet article
			entitled 'Attn: L.S.D' in the
			'alt.anonymous.messages'
			newsgroup.

			-------------------------------

			Luv LSDude, echelon77 and
			FaTmAn.

			Greetz to FFF, THC and all the
			l33t dudes out there!

			-------------------------------

			Some people hack it,
			Some others crack it,
			We ransack it!

			-------------------------------

			!BLOW.IT.UP!

			===============================

			</pre>

Arvindn: #redirect Randomized algorithm

2004-03-17T07:59:00Z

#redirect Randomized algorithm

← Previous revision		Revision as of 07:59, 17 March 2004
Line 1:		Line 1:
	~~'''{{msg:merge}}~~[[Randomized algorithm]]~~'''~~		#redirect [[Randomized algorithm]]

	A '''randomized algorithm''' is an [[algorithm]] equipped with a source of random [[bit\|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].

	== Example 1==
	One good example of a randomized algorithm is a ''Monte Carlo algorithm'' (i.e. one using the [[Monte Carlo Method]]). For example, suppose we have an event, E, whose probability we would like to estimate. Say you are playing [[blackjack]], you have 19 and E is the event that you win. Your algorithm uses its source of random bits to generate K random hands the dealer could have, and determines what in fraction of them you win, W. Then W/K is a good estimate for the probability that you win, as K becomes large.

	==Example 2==
	A more complex example, but one more representative of the use of randomized algorithms in [[computer science]], is one of David Karger's randomized [[minimum cut]] algorithms:

	Find-Min-Cut(undirected graph G){
	While there are more than 2 nodes in G do{
	Pick an edge (u,v) at random in G.
	Contract the edge, while preserving multi-edges.
	Remove all self-loops.
	}
	Output the remaining edges.
	}

	Here, contracting an edge (u,v) means adding a new vertex, w,
	replacing any edge (u,x) or (v,x) with (w,x), and then deleting u and v
	from G.

	Let <math>n = \|V[G]\|</math>.
	It can be shown that this algorithm outputs a minimum cut with
	probability at least <math>n^{-2}</math>, thus running it
	<math>n^{2} \log(n)</math> times and taking the smallest output cut,
	we find a minimum cut with high probability.

	==Relations to Complexity Theory==
	There are complexity classes denoting the decision problems computable by
	randomized algorithms with various properties. For example, '''RP''' is the
	class of ''randomized polynomial-time'' problems.

	Formally, a language ''L'' is in '''RP''' if and only if there exists a polynomial-time randomized algorithm ''A'' such that for all ''x'' ∈ ''L'', Pr(''A'' accepts ''x'') > 3/4, and for all ''x'' ∉ ''L'', Pr(''A'' accepts ''x'') = 0.

Jiang at 05:54, 16 March 2004

2004-03-16T05:54:53Z

← Previous revision		Revision as of 05:54, 16 March 2004
Line 1:		Line 1:
			'''{{msg:merge}}[[Randomized algorithm]]'''

	A '''randomized algorithm''' is an [[algorithm]] equipped with a source of random [[bit\|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].		A '''randomized algorithm''' is an [[algorithm]] equipped with a source of random [[bit\|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].

Timwi: fix math notation

2004-03-09T23:38:29Z

fix math notation

← Previous revision		Revision as of 23:38, 9 March 2004
Line 28:		Line 28:
	==Relations to Complexity Theory==		==Relations to Complexity Theory==
	There are complexity classes denoting the decision problems computable by		There are complexity classes denoting the decision problems computable by
	randomized algorithms with various properties. For example, RP is the		randomized algorithms with various properties. For example, '''RP''' is the
	class of ''randomized polynomial time'' problems.		class of ''randomized polynomial-time'' problems.

	Formally, a language L is in RP if and only if there exists a polynomial time		Formally, a language ''L'' is in '''RP''' if and only if there exists a polynomial-time randomized algorithm ''A'' such that for all ''x'' ∈ ''L'', Pr(''A'' accepts ''x'') > 3/4, and for all ''x'' ∉ ''L'', Pr(''A'' accepts ''x'') = 0.
	randomized algorithm A such that for all x in L, Pr(A accepts x) > 3/4 and
	for all x not in L, Pr(A accepts x) = 0.

Timwi: pre

2004-03-09T23:35:41Z

pre

← Previous revision		Revision as of 23:35, 9 March 2004
Line 7:		Line 7:
	A more complex example, but one more representative of the use of randomized algorithms in [[computer science]], is one of David Karger's randomized [[minimum cut]] algorithms:		A more complex example, but one more representative of the use of randomized algorithms in [[computer science]], is one of David Karger's randomized [[minimum cut]] algorithms:

	Find-Min-Cut(undirected graph G){		Find-Min-Cut(undirected graph G){
	While there are more than 2 nodes in G do{		While there are more than 2 nodes in G do{
	Pick an edge (u,v) at random in G.		Pick an edge (u,v) at random in G.
	Contract the edge, while preserving multi-edges.		Contract the edge, while preserving multi-edges.
	Remove all self-loops.		Remove all self-loops.
			}
		⚫	Output the remaining edges.
	}		}
⚫	Output the remaining edges.
	}

	Here, contracting an edge (u,v) means adding a new vertex, w,		Here, contracting an edge (u,v) means adding a new vertex, w,

Timwi: no header for intro section

2004-03-09T23:33:47Z

no header for intro section

← Previous revision		Revision as of 23:33, 9 March 2004
Line 1:		Line 1:
		⚫	A '''randomized algorithm''' is an [[algorithm]] equipped with a source of random [[bit\|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].
	==Overview==

⚫	A randomized algorithm is an [[algorithm]] equipped with a source of random [[bit\|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].

	== Example 1==		== Example 1==

67.165.96.9 at 22:47, 9 March 2004

2004-03-09T22:47:00Z

New page

==Overview==

A randomized algorithm is an [[algorithm]] equipped with a source of random [[bit|bits]], that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a [[random variable]] determined by the random bits, with (hopefully) good [[expected value]].

== Example 1==
One good example of a randomized algorithm is a ''Monte Carlo algorithm'' (i.e. one using the [[Monte Carlo Method]]). For example, suppose we have an event, E, whose probability we would like to estimate. Say you are playing [[blackjack]], you have 19 and E is the event that you win. Your algorithm uses its source of random bits to generate K random hands the dealer could have, and determines what in fraction of them you win, W. Then W/K is a good estimate for the probability that you win, as K becomes large.

==Example 2==
A more complex example, but one more representative of the use of randomized algorithms in [[computer science]], is one of David Karger's randomized [[minimum cut]] algorithms:

Find-Min-Cut(undirected graph G){
While there are more than 2 nodes in G do{
Pick an edge (u,v) at random in G.
Contract the edge, while preserving multi-edges.
Remove all self-loops.
}
Output the remaining edges.
}

Here, contracting an edge (u,v) means adding a new vertex, w,
replacing any edge (u,x) or (v,x) with (w,x), and then deleting u and v
from G.

Let <math>n = |V[G]|</math>.
It can be shown that this algorithm outputs a minimum cut with
probability at least <math>n^{-2}</math>, thus running it
<math>n^{2} \log(n)</math> times and taking the smallest output cut,
we find a minimum cut with high probability.

==Relations to Complexity Theory==
There are complexity classes denoting the decision problems computable by
randomized algorithms with various properties. For example, RP is the
class of ''randomized polynomial time'' problems.

Formally, a language L is in RP if and only if there exists a polynomial time
randomized algorithm A such that for all x in L, Pr(A accepts x) > 3/4 and
for all x not in L, Pr(A accepts x) = 0.