text:
->''The Frightbot told a story so scary you couldn't help but laugh.''
-->-- ''VideoGame/{{Mother 3}}''
->''He was sobbing so hard that he began to hiccup.''
-->-- '''Lorelei Mackenzie''', [[http://www.trekiverse.org/archive/2000/story/tng/PicardsIllumination Picard's Illumination]]
->''"My arm is numb. Numb arm. Numb arm, [[TropeNamer narm, NARM, NARM--]]"'' *thud*
-->-- '''Nate''', Series/SixFeetUnder
->''"[[{{Engrish}} The miracle never happen.]]"''
-->-- ''VisualNovel/PhoenixWrightAceAttorneyJusticeForAll'' (Bad Ending)
[[BigOMG Gooooooooooooooooooood.]]"''
-->--'''[[https://www.youtube.com/watch?v=lDKmSxJkOWA Hikaru Sulu]]''', Series/StarTrekVoyager (Flashback)
-->-- '''Zero''', VideoGame/MegaManX4 [[http://www.youtube.com/watch?v=LISmPmdUhYA cutscene]]
->''"[[https://www.youtube.com/watch?v=Y4cWu-0g2P8 I should have been the one to fill your dark soul with]] '''[[SkywardScream LIIIIIIIIIGHT]]'''!"''
-->-- '''Dante''', ''Franchise/DevilMayCry''
->[[AGodAmI I'M THE LIGHT BRINGER!]] ''[[https://www.youtube.com/watch?v=Wh1A03r7Nz8&t=56s I'M THE FUCKING UNIVERSE!!]]''
-->-- '''Edward Carnby''', ''Videogame/AloneInTheDark2008''
->''"Join me, Link, and I will make [[{{Mondegreen}} your face]] the grrrrrreatest in Koridai! Or else you will '''DIE.'''\\
You DARE bring LIGHT to my LAIR? '''YOU MUST DIE!!'''"''
-->-- '''Ganon''', ''[[VideoGame/TheLegendOfZeldaCDiGames Link: The Faces of Evil]]'' and ''[[WebVideo/YouTubePoop Zelda: The Wand of Gamelon]]'', respectively (and by the way, every single line from these games could probably be quoted here, but those two are arguably the Narmiest.)
->''"RUUUUUUN!!! GOOOOOOOOOOO!!! [[MemeticMutation GET TO THE CHOPAAAAAAAHHHHHH!!!]]"''
-->-- '''Dutch''' (Creator/ArnoldSchwarzenegger), Film/{{Predator}}
->''"[-........................................my boat.-]"''
-->--'''The Mariner''', {{Film/Waterworld}}
-->--'''William Forrester''', Film/FindingForrester
->''"I, Garland, will knock you all down!"''
-->-- VideoGame/FinalFantasyI
->''"Oh man! Oh God, oh man! [[MadnessMantra Oh God, oh man! Oh God oh man! Oh God oh man oh GOD]]"''
-->-- '''Ryan O'Neal''', [[http://www.youtube.com/watch?v=Y9KyBdPeKHg Tough Guys Don't Dance]]
->[[{{Engrish}} Don't walk you away]], \\
I can find \\
Don't walk you away, \\
I can smile \\
[[JapaneseRanguage All in one right]], \\
all in one yeah! \\
Start all again
-->-- The (on-screen) lyrics to the VideoGame/{{DJMAX}} song [[http://www.youtube.com/watch?v=XnAcT5nwc28&fmt=18 Fallen Angel]]
->''"That was TOO close! You were almost a JILL SANDWICH!"''
-->-- '''Barry Burton''', VideoGame/ResidentEvil
->''"[[http://www.youtube.com/watch?v=i7gIpuIVE3k Garbage day! Hahahaha!]]"''
-->-- Film/SilentNightDeadlyNightPart2
->''"[[http://www.youtube.com/watch?NR=1&v=HyophYBP_w4&feature=fvwp They're eating her! And then theyre going to eat me! OH MY GOOOOOOOOOOOOD!!!!]]"''
-->-- Film/{{Troll 2}}
->''"Then it's settled. Let's have fun tonight because it is... IT'S PARTY TIME!"''
-->--'''Minh''', Anime/BloodPlus
->''"[[IllKillYou I'll kill you]]! [[ShapedLikeItself I'll kill you to death]]!"''
-->-- '''Superboy-Prime''', ComicBook/CountdownToInfiniteCrisis
-->-- Love is Breaking My Heart by Grave Digger
->''"NOOOO! '''MY LOVE!''' Accept it! Accept it! '''ACCEPT IT!'''"''
-->-- '''Zommari Leroux''', Manga/{{Bleach}}
->''"WHAT is a MAN?!? A MISERABLE LITTLE PILE OF SECRETS! But enough talk, HAVE AT YOU!!"''
-->-- '''Dracula''', VideoGame/CastlevaniaSymphonyOfTheNight
->''"Holy cosmos, look at that thing! So, that's the dragon of the legends? My gosh! That's one whopper of a lizard!"''
-->-- [[Manga/DragonBall Vegeta]], [[http://www.youtube.com/watch?v=EdGa-2BSFiI discovering the Namekian Dragon.]]
-->-- '''Johnny''', Film/TheRoom
->"''I should not be laughing! This is a terrible situation! And yet... I find myself unable to resist... your influence!"''
-->-- '''Jorgen Von Strangle''', in The [[WesternAnimation/TheAdventuresOfJimmyNeutron Jimmy]]/[[WesternAnimation/TheFairlyOddparents Timmy]] Power Hour 2: When Nerds Collide after he blasts Jimmy and Timmy into a ditch.
->"And ah pray...OH! MAH! GOD! DO AH PRAY! I PRAY EVERYDAY SINGLE DA-AY!"
-->--'''4 Non Blondes''', "What's Up?"
->I don't think that I can ''take it!''
->Cause it took so long to ''bake it!''
->''And I'll '''never''' have that recipe again!''
->Oh '''''[[BigNo NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO!!!!!!!!!]]'''''
-->-- '''Richard Harris''', "[=MacArthur=] Park"
->"Holy mother of unintentional comedy!"
-->--'''Mike Nelson''' upon seeing Two-Face, Podcast/RiffTrax of ''Film/TheDarkKnight''
->"Yang! This is a sad scene! The audience can't be sad if they're laughing!"
-->--'''Ruby Rose''' as Yang steals the Red Riding Hood play in ''WebAnimation/RWBYChibi''
->"Wait a minute...this isn't my world...[[SayingSoundEffectsOutLoud disa]]'''''[[BigWordShout POOOOIIIINTEEEEEEED!!!!]]'''''"
->''"The sublime and the ridiculous are often so nearly related, that it is difficult to class them separately. One step above the sublime, makes the ridiculous; and one step above the ridiculous, makes the sublime again."''
-->-- '''Thomas Paine''', The Age of Reason, (1795)
->''"Misjudging whether to go big or small is, dramatically, a huge problem. The entire tightrope of dramatic effectiveness hinges on getting the balance right. The line between pathos and bathos is razor thin, and tumbling off of it can be the difference between brilliant and a disaster that will be mocked for the ages."''
-->-- '''[[http://www.eruditorumpress.com/blog/pop-between-realities-home-in-time-for-tea-71-skins/ Dr. Phil Sandifer]]''' on ''{{Series/Skins}}''
->''"There's probably a reason ''Jessie's Song'' has gotten boiled down to [[https://www.youtube.com/watch?v=bflYjF90t7c a single line of dialogue]], as it's merely a taster for ''[[Series/SavedByTheBell SBTB]]''[='=]s real excursion into drug hysteria that's yet to come, and wanders on both sides of the line between sanity and white-knuckled pearl-clutching. But when it does cross over, it's a real [[Series/MontyPythonsFlyingCircus John Cleese]] of a walk, with one leg halfway up behind its ears and the other right up its own hole."''
-->--'''Stuart Millard''', ''So Excited, So Scared''
->''"My 12-year-old son, Rob, was going through a pile of ballots, and he asked me how "[=MacArthur=] Park" goes, so I sang it, giving it my best shot, and Rob laughed so hard that when I got to the part about [[FauxSymbolism leaving the cake out in the rain]], [[WordSaladLyrics and it took so long to bake it]], and [[{{Metaphorgotten}} I'll never have that recipe again]], Rob was on the floor. He didn't BELIEVE those lyrics were real. He was SURE his wacky old humor-columnist dad [[PoesLaw was making them up.]]"''
-->--'''Creator/DaveBarry''' on the worst song ever recorded
->''"I had a stage in my life when I tried to get my friends to watch ''Doctor Who'' with me. The sad truth of the matter is that I was never going to get them to fall in love with it the way I do and so the exercise was fairly redundant...The closest I got to convincing somebody that this show really was brilliant was my friend Luke who watched the first two episodes of Ghost Light with some enthusiasm. However it all fell to pieces in part three when Light was revealed and he stepped from the lift [[FashionVictimVillain as camp as Christmas]]. Luke fell about laughing and never recovered from his mirth. To this day he still opens every text conversation, email and Facebook message with ''[==]'''[[PunyEarthlings look at these microbes ]]'''[==]'' Now the only person who has to put up with my Who obsession is Simon but he was stupid enough to marry me."''
-->--'''[[http://docohobigfinish.blogspot.co.uk/2014/01/ghost-light-written-by-marc-platt-and.html Joe Ford]]''' on ''Series/DoctorWho'', [[{{Recap/DoctorWhoS26E2GhostLight}} "Ghost Light"]]
->'''Chris:''' Remember that really good episode of WesternAnimation/JusticeLeagueUnlimited about ComicBook/BoosterGold? This is basically the opposite of that...The [[InUniverseMarketing Booster Gold infomercial]] that they ran part of in the preview last week was seriously the high point of the show.\\
'''David''': I loved all of the commercial scenes, but thats not because the show tried really hard to get the vibe of a Booster Gold informercial and reached an aspired-to level of cheesiness, its because the show is naturally at the level of [[WorldOfBuxom craft]] and [[{{Anvilicious}} subtlety]] of a Booster Gold infomercial.\\
'''Chris''': Zing!
-->--''Smallvillains'' [[http://comicsalliance.com/recap-smallville-episode-10-18-booster/ on]] {{Series/Smallville}} (Booster)
->''"Arnold rips his throat out, turns to the camera and bellows, HERE'S SUB ZERO. NOW! PLAIN ZERO!!! I honestly can't conceive of a world where there's a more badass thing to say after killing someone named Sub Zero. We are so blessed to have Film/RunningMan in our lives."''
-->--'''{{Creator/Seanbaby}}''', [[http://www.break.com/article/the-12-best-arnold-kills-out-of-all-509-2554063 The 12 Best Arnold Kills (Out of 509)]]
->''"It's the dead seriousness of this line that really makes this scene immortal. This actor sells it like he's [[ComicBook/GreenLantern Hal Jordan]] gifted with this godlike artifact of immeasurable power, something to be feared and respected. He gives it the same battle-hardened, post-orgiastic tone as the classic 'I love the smell of napalm in the morning' line from ''Film/ApocalypseNow.''"''
-->--'''[[WebVideo/TheSpoonyExperiment Noah Antwiler]]''' [[http://spoonyexperiment.com/the-wizard/ on]] ''Film/TheWizard''
->''"I personally love when [the film] tries to build up how badass Creator/StevenSeagal is by saying something to the effect of '''You could drop him in the middle of Antartica with only his skivvies and he would show up at your pool the next day with a tan and a fistful of pesos.''' That is just brilliant. This movie is simply hilarious and is funnier than most comedies out there today. You arent a movie fan until you are a Seagal connoisseur."''
-->--'''[[WebVideo/TheSpoonyExperiment Miles Antwiler]]''' [[http://moviemoses.wordpress.com/2010/01/20/on-deadly-ground-1993-steven-seagal/ on]] Film/OnDeadlyGround
->''"Moviemakers talk about 'bad laughs.' That's when the audience laughs when it's not supposed to. This is conceivably the first movie which is in its entirety a bad laugh."''
-->-- '''Creator/RogerEbert''', ''UsefulNotes/TheHindenburg'' (1975)
->''"Netflix also labels this as a comedy, but any laughter is purely unintentional."''
-->--'''{{Website/Wrestlecrap}}''' [[http://www.wrestlecrap.com/inductions/induction-the-reunion/ on]] The Reunion (2011)
->''"Of all people, Nguyen best sums up why Film/{{Birdemic}} [[SoBadItsGood works]] in the bonus features: When an audience member sarcastically asks why his film is so awesome, he responds with one word: '''Sincerity'''"''
-->--'''Andrew Kasch''', Dread Central's Birdemic: Shock and Terror DVD/Blu-Ray [[http://www.dreadcentral.com/reviews/birdemic-shock-and-terror-dvdblu-ray review]]
->"''Everyone in the theater laughed at this point. Not exactly the reaction you want for your big dramatic moment.''"
-->-- '''TheDistressedWatcher''', on Darth Vader's BigNo from ''Franchise/StarWars : Film/RevengeOfTheSith''
->''"Now, is [[RevengeOfTheSith General Grievous]] supposed to be funny? 'Cause they said he was a villain, right? Not a comedian?"''
-->-- '''[[WebVideo/RedLetterMedia Mr. Plinkett]]''', Revenge of the Sith review
->''"When faced with unspeakable horror, Cage seemingly thought to himself, 'What would [[Series/{{Friends}} Chandler Bing]] say?'"''
-->-- '''''{{Website/Cracked}}''''' on ''Film/TheWickerMan''
->''"There aren't many video games that [[https://www.youtube.com/watch?v=-5FTJxfV3pc I've actually been embarrassed]] to have people watching me play."''
-->--'''Pat R.''', [[http://www.socksmakepeoplesexy.net/index.php?a=ff10 I'm Ready For My Closeup, Mr. Sakaguchi.]]
->''"It's incidents like when Wesley Snipes gets whacked twice with a TV set and barely suffers a bruise that make up the real humor."''
-->-- [[http://www.reelviews.net/movies/d/demo_man.html James Berardinelli's review]] of ''Film/DemolitionMan''.
->"{{Spider-man}} gave Mary Jane cancer by tragically shooting her up repeatedly with his horrible radioactive Spider-Semen. ''His horrible radioactive Spider-Semen''. Thats not tragic. That shit is fucking ''hilarious''."
-->-- '''''Blog/ToplessRobot''''' [[http://www.toplessrobot.com/2008/11/the_12_dumbest_spiderman_stories_ever_besides_the.php on]] ''Comicbook/SpiderManReign''
->''"Dracula seems to have abandoned his wife, Dolores, out of grief for their dead son, leaving her to grieve for Janus at his gravestone. It's actually a kind of sad scene, at least it would be if his gravestone didn't say Rest In [[YouMakeMeSic Peaee]]."''
-->-- '''WebVideo/BennettTheSage''', in his review of [[http://thatguywiththeglasses.com/bt/the-sage/anime-abandon/33924-dracula-sovereign-of-the-damned-with-linkara Dracula Sovereign Of The Damned]]
->''"The first hour is as boring as ever, [[ItMakesSenseInContext even though they're doing the running and explaining with the less bad haircut]]. The little bit after that, snore-inducingly bad, but the last forty minutes are laugh-out-loud funny, and I guarantee you if Gerry Anderson had come up with that plot for'' Series/{{Thunderbirds}} ''or'' Series/{{Stingray}}'', he would have torn the place up. The skydiving implications of it are so staggering. In a way, I want to tell you what happens at the end because the end is so funny.''"
-->-- '''Creator/MarkKermode''' on ''Film/AngelsAndDemons''
->The comic's main villain, an old school dean who once expelled Chris for good reason, is, in the comic, an evil witch who uses a brain control ray to transform the inhabitants of [=CWCville=] into her slaves (read: mall guards). Chris explains to the audience that this ray only works on the slow-in-mind. Hilarity ensues when you realize this means that whenever Sonichu and friends fight Mary Lee's minions, [[UnfortunateImplications they are actually beating through wave after wave of the mentally handicapped.]]
-->--[[http://badwebcomicswiki.shoutwiki.com/wiki/Sonichu The Bad Webcomics Wiki]] on Webcomic/{{Sonichu}}
->Be brave like my mother. Otherwise, you disgrace her. Oh, snap, thats harsh
->Otherwise, she died for nothing. O SNAP NOW YOUVE REALLY GOT HIM
->Otherwise, the bowl will remain empty, forever. Aaaaaand youve oversold it. There was a Line of Bathos, and you crossed it. I know its a metaphorical fish, but sweetie, that fish aint comin back.
-->-- [[Creator/CleolindaJones Cleolinda Jones]] in the [[FootnoteFever commentary]] for Literature/HarryPotterAndTheHalfBloodPrince in 15 minutes.
-> You would have to have a heart of stone to watch Rory laying down his own life to save Amy (for the sixteenth or seventeenth time) without giggling, at least a little.
-->-- '''[[http://www.andrewrilstone.com Andrew Rilstone]]''' reviewing ''Series/DoctorWho, The Angels Take Manhattan'' in ''The Viewer's Tale''
->'''[[MonsterClown Zeebo:]]''' ''Give it back...''
->'''[[WebOriginal/JonTron JonTron:]]''' Oh, hey. This is getting kinda scary...
->'''Zeebo:''' ''(Circus music kicks in)'' '''''[[InopportuneVoiceCracking GIVE IT BAAAAAACK!]]'''''
->'''[[WebOriginal/JonTron JonTron:]]''' ...Aaaand they blew it!
-->-- '''WebOriginal/JonTron''' reviewing ''Series/AreYouAfraidOfTheDark''
-> In rough cut, ''Film/TheLonelyLady'' was [[SoBadItsGood one of the funniest bad movies ever made]]. Sadly, its makers previewed their film in Long Beach a week or two after I saw the rough cut, and, realizing what a total turkey they had in their hands, [[PolishTheTurd went through the movie trying desperately to cut all the laughs]]. But without the laughs, the movie was about 17 minutes long.
-->--'''[[https://books.google.com/books?id=bLpJHjGFNk8C&pg=PT231 John Wilson]]''', ''The Official [[Usefulnotes/GoldenRaspberryAward Razzie]] Movie Guide''
->''As I said previously, I really think this book suffers for its audience. There's a paradox in the subject matter; on the one hand, Lasky wants to deal with themes such as Stockholm Syndrome, cannibalism, and child soldiers, but at the same time, she has to write these themes so they're accessible to her audience... which, unfortunately, is elementary and middle school students.\\
It's really ridiculous at times. One minute, the characters will be discussing cannibalism of children and even unhatched fetuses, and yet the next minute they'll be vowing to beat the "badbutts". Really? The cannibalistic badbutts?''
-->-- [[http://aftanith.blogspot.com.au/2012/12/the-journey-guardians-of-gahoole-2-by.html A review]] of ''Literature/GuardiansOfGahoole''


text:
Bernoulli process
|This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (September 2011) (Learn how and when to remove this template message)
In probability and statistics, a Bernoulli process is a finite or infinite sequence of binary random variables, so it is a discrete-time stochastic process that takes only two values, canonically 0 and 1. The component Bernoulli variables Xi are identical and independent. Prosaically, a Bernoulli process is a repeated coin flipping, possibly with an unfair coin (but with consistent unfairness). Every variable Xi in the sequence is associated with a Bernoulli trial or experiment. They all have the same Bernoulli distribution. Much of what can be said about the Bernoulli process can also be generalized to more than two outcomes (such as the process for a six-sided die); this generalization is known as the Bernoulli scheme.
The problem of determining the process, given only a limited sample of the Bernoulli trials, may be called the problem of checking whether a coin is fair.
- 1 Definition
- 2 Formal definition
- 3 Law of large numbers, binomial distribution and central limit theorem
- 4 Dynamical system
- 5 Bernoulli sequence
- 6 Randomness extraction
- 7 References
- 8 Further reading
- 9 External links
A Bernoulli process is a finite or infinite sequence of independent random variables X1, X2, X3, ..., such that
- For each i, the value of Xi is either 0 or 1;
- For all values of i, the probability that Xi = 1 is the same number p.
In other words, a Bernoulli process is a sequence of independent identically distributed Bernoulli trials.
Independence of the trials implies that the process is memoryless. Given that the probability p is known, past outcomes provide no information about future outcomes. (If p is unknown, however, the past informs about the future indirectly, through inferences about p.)
If the process is infinite, then from any point the future trials constitute a Bernoulli process identical to the whole process, the fresh-start property.
The two possible values of each Xi are often called "success" and "failure". Thus, when expressed as a number 0 or 1, the outcome may be called the number of successes on the ith "trial".
Two other common interpretations of the values are true or false and yes or no. Under any interpretation of the two values, the individual variables Xi may be called Bernoulli trials with parameter p.
In many applications time passes between trials, as the index i increases. In effect, the trials X1, X2, ... Xi, ... happen at "points in time" 1, 2, ..., i, .... That passage of time and the associated notions of "past" and "future" are not necessary, however. Most generally, any Xi and Xj in the process are simply two from a set of random variables indexed by {1, 2, ..., n} or by {1, 2, 3, ...}, the finite and infinite cases.
Several random variables and probability distributions beside the Bernoullis may be derived from the Bernoulli process:
- The number of successes in the first n trials, which has a binomial distribution B(n, p)
- The number of trials needed to get r successes, which has a negative binomial distribution NB(r, p)
- The number of trials needed to get one success, which has a geometric distribution NB(1, p), a special case of the negative binomial distribution
The negative binomial variables may be interpreted as random waiting times.
Formal definition[edit]
The Bernoulli process can be formalized in the language of probability spaces as a random sequence of independent realisations of a random variable that can take values of heads or tails. The state space for an individual value is denoted by
Specifically, one considers the countably infinite direct product of copies of . It is common to examine either the one-sided set or the two-sided set . There is a natural topology on this space, called the product topology. The sets in this topology are finite sequences of coin flips, that is, finite-length strings of H and T, with the rest of (infinitely long) sequence taken as "don't care". These sets of finite sequences are referred to as cylinder sets in the product topology. The set of all such strings form a sigma algebra, specifically, a Borel algebra. This algebra is then commonly written as where the elements of are the finite-length sequences of coin flips (the cylinder sets).
If the chances of flipping heads or tails are given by the probabilities , then one can define a natural measure on the product space, given by (or by for the two-sided process). Given a cylinder set, that is, a specific sequence of coin flip results at times , the probability of observing this particular sequence is given by
where k is the number of times that H appears in the sequence, and n-k is the number of times that T appears in the sequence. There are several different kinds of notations for the above; a common one is to write
where each is a binary-valued random variable with in Iverson bracket notation, meaning either if or if . This probability is commonly called the Bernoulli measure.[1]
Note that the probability of any specific, infinitely long sequence of coin flips is exactly zero; this is because , for any . One[who?] says that any given infinite sequence has measure zero. Nevertheless, one can still say that some classes of infinite sequences of coin flips are far more likely than others, this is given by the asymptotic equipartition property.
To conclude the formal definition, a Bernoulli process is then given by the probability triple , as defined above.
Law of large numbers, binomial distribution and central limit theorem[edit]
Let us assume the canonical process with represented by and represented by . The law of large numbers states that, on the average of the sequence, i.e., , will approach the expected value almost certainly, that is, the events which do not satisfy this limit have zero probability. The expectation value of flipping heads, assumed to be represented by 1, is given by . In fact, one has
for any given random variable out of the infinite sequence of Bernoulli trials that compose the Bernoulli process.
One is often interested in knowing how often one will observe H in a sequence of n coin flips. This is given by simply counting: Given n successive coin flips, that is, given the set of all possible strings of length n, the number N(k,n) of such strings that contain k occurrences of H is given by the binomial coefficient
If the probability of flipping heads is given by p, then the total probability of seeing a string of length n with k heads is
This probability is known as the Binomial distribution.
Of particular interest is the question of the value of for a sufficiently long sequences of coin flips, that is, for the limit . In this case, one may make use of Stirling's approximation to the factorial, and write
Inserting this into the expression for P(k,n), one obtains the Normal distribution; this is the content of the central limit theorem, and this is the simplest example thereof.
The combination of the law of large numbers, together with the central limit theorem, leads to an interesting and perhaps surprising result: the asymptotic equipartition property. Put informally, one notes that, yes, over many coin flips, one will observe H exactly p fraction of the time, and that this corresponds exactly with the peak of the Gaussian. The asymptotic equipartition property essentially states that this peak is infinitely sharp, with infinite fall-off on either side. That is, given the set of all possible infinitely long strings of H and T occurring in the Bernoulli process, this set is partitioned into two: those strings that occur with probability 1, and those that occur with probability 0. This partitioning is known as the Kolmogorov 0-1 law.
The size of this set is interesting, also, and can be explicitly determined: the logarithm of it is exactly the entropy of the Bernoulli process. Once again, consider the set of all strings of length n. The size of this set is . Of these, only a certain subset are likely; the size of this set is for . By using Stirling's approximation, putting it into the expression for P(k,n), solving for the location and width of the peak, and finally taking one finds that
This value is the Bernoulli entropy of a Bernoulli process. Here, H stands for entropy; do not confuse it with the same symbol H standing for heads.
John von Neumann posed a curious question about the Bernoulli process: is it ever possible that a given process is isomorphic to another, in the sense of the isomorphism of dynamical systems? The question long defied analysis, but was finally and completely answered with the Ornstein isomorphism theorem. This breakthrough resulted in the understanding that the Bernoulli process is unique and universal; in a certain sense, it is the single most random process possible; nothing is 'more' random than the Bernoulli process (although one must be careful with this informal statement; certainly, systems that are mixing are, in a certain sense, 'stronger' than the Bernoulli process, which is merely ergodic but not mixing. However, such processes do not consist of independent random variables: indeed, many purely deterministic, non-random systems can be mixing).
Dynamical system[edit]
The Bernoulli process can also be understood to be a dynamical system, specifically, a measure-preserving dynamical system. This arises because there is a natural translation symmetry on the (two-sided) product space given by the shift operator
The measure is translation-invariant; that is, given any cylinder set , one has
and thus the Bernoulli measure is a Haar measure.
The shift operator should be understood to be an operator acting on the sigma algebra , so that one has
In this guise, the shift operator is known as the transfer operator or the Ruelle-Frobenius-Perron operator. It is interesting to consider the eigenfunctions of this operator, and how they differ when restricted to different subspaces of . When restricted to the standard topology of the real numbers, the eigenfunctions are curiously the Bernoulli polynomials![2][3] This coincidence of naming was presumably not known to Bernoulli.
Bernoulli sequence[edit]
The term Bernoulli sequence is often used informally to refer to a realization of a Bernoulli process. However, the term has an entirely different formal definition as given below.
Suppose a Bernoulli process formally defined as a single random variable (see preceding section). For every infinite sequence x of coin flips, there is a sequence of integers
called the Bernoulli sequence[verification needed] associated with the Bernoulli process. For example, if x represents a sequence of coin flips, then the associated Bernoulli sequence is the list of natural numbers or time-points for which the coin toss outcome is heads.
So defined, a Bernoulli sequence is also a random subset of the index set, the natural numbers .
Almost all Bernoulli sequences are ergodic sequences.[verification needed]
Randomness extraction[edit]
From any Bernoulli process one may derive a Bernoulli process with p = 1/2 by the von Neumann extractor, the earliest randomness extractor, which actually extracts uniform randomness.
Basic von Neumann extractor[edit]
Represent the observed process as a sequence of zeroes and ones, or bits, and group that input stream in non-overlapping pairs of successive bits, such as (11)(00)(10)... . Then for each pair,
- if the bits are equal, discard;
- if the bits are not equal, output the first bit.
This table summarizes the computation.
For example, an input stream of eight bits 10011011 would by grouped into pairs as (10)(01)(10)(11). Then, according to the table above, these pairs are translated into the output of the procedure: (1)(0)(1)() (=101).
In the output stream 0 and 1 are equally likely, as 10 and 01 are equally likely in the original, both having probability pq = qp. This extraction of uniform randomness does not require the input trials to be independent, only uncorrelated. More generally, it works for any exchangeable sequence of bits: all sequences that are finite rearrangements are equally likely.
The von Neumann extractor uses two input bits to produce either zero or one output bits, so the output is shorter than the input by a factor of at least 2. On average the computation discards proportion p2 + (1 − p)2 of the input pairs, or proportion p2 + q2, which is near one when p is near zero or one.
The discard of input pairs is at least proportion 1/2, the minimum which occurs where p = 1/2 for the original process. In that case the output stream is 1/4 the length of the input on average.
Iterated von Neumann extractor[edit]
|This section possibly contains inappropriate or misinterpreted citations that do not verify the text. (January 2014) (Learn how and when to remove this template message)
This decrease in efficiency, or waste of randomness present in the input stream, can be mitigated by iterating the algorithm over the input data. This way the output can be made to be "arbitrarily close to the entropy bound".[4] The algorithm works recursively, recycling ``wasted randomness" from two sources: the sequence of discard/non-discard, and the values of discarded pairs (00/11). Intuitively, it relies on the fact that, given the sequence already generated, both of those sources are still exchangeable sequences of bits, and thus eligible for another round of extraction.
More concretely, on an input sequence, the algorithm consumes the input bits in pairs, generating output together with two new sequences:
|new sequence 1
|new sequence 2
(If the length of the input is odd, the last bit is completely discarded.) Then the algorithm is applied recursively to each of the two new sequences, until the input is empty.
Example: The input stream from above, 10011011, is processed this way:
|step number
|new sequence 1
|new sequence 2
The output is therefore (101)(1)(0)()()() (=10110), so that from the eight bits of input five bits of output were generated, as opposed to three bits through the basic algorithm above.
- ^ Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN 978-1-84800-047-6.
- ^ Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992).
- ^ Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands ISBN 0-7923-5564-4
- ^ Peres, Yuval (March 1992). "Iterating Von Neumann's Procedure for Extracting Random Bits" (PDF). The Annals of Statistics. 20 (1): 590–597. doi:10.1214/aos/1176348543. Retrieved 30 May 2013.
Further reading[edit]
- Carl W. Helstrom, Probability and Stochastic Processes for Engineers, (1984) Macmillan Publishing Company, New York ISBN 0-02-353560-1.
- Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, (2002) Athena Scientific, Massachusetts ISBN 1-886529-40-X

subset: commoncrawl


text:
In a message dated 02/14/2003 9:56:13 AM Eastern Standard Time,
firstname.lastname@example.com writes:
> Even if some group slips past our numerous and costly assorted
> >government agencies in charge of security, their goal would be high
> >numbers and those are only found in major urban areas, so anybody in
> >a small town upwind of a major city has more chance of getting hit by
> >a car crossing the street than suffering from a terrorist attack. In
> >fact, even those of us living in areas that present lovely targets
> >need to simply get on with life and worry about what we need to worry
> >about, which does not include going into panic mode about terrorist
> >attacks. Remember the story about Chicken Little...
It seems to me that the extent to which we let these evil people cause us to
alter our lifestyles or live in fear and panic is the extent to which they
have already won their battle. I say this, living only about ten miles from
the controversial Indian Point nuclear power station. Auralie
To sign-off this list, send email to firstname.lastname@example.com with the
message text UNSUBSCRIBE GARDENCHAT