text:
CSUF Home
About CSUF
CSUF News
Titan Voices
Students Create Climate App for a Smart, Internet-Connected City
GE Digital CSU Challenge Draws Eight California State University Teams
Faculty mentors Mikhail Gofman and Kenneth "John" Faller, top photo from left, work with student Nara Dashdondog. Team members Austin Suarez, above photo from left, Jonathan Schinowsky, Jonathan Moubayed and Dashdondog collaborate on their app project for the GE Digital CSU Challenge.
A team of Cal State Fullerton computer science, computer engineering and business students is developing an app to tackle urban challenges for a smart, internet-connected city.
CSUF is one of eight California State University teams competing in this year's GE Digital CSU Challenge. The competition is designed to spark interest among engineering and computer science talent to develop projects, products, applications and solutions utilizing GE's Predix cloud-based software technology for the industrial internet.
The GE Challenge culminates with a symposium Sunday, April 29, from 9 a.m.-2:30 p.m. at San Diego Central Library. Teams will present their projects to judges from the city of San Diego and industry, and compete for $25,000 in total prize money, as well as the opportunity to intern at GE Digital.
This year's challenge focuses on San Diego, which has deployed an "internet of things" platform by placing more than 3,200 "intelligent nodes" on streetlights across the city. San Diego also has launched an open data portal to share data about city operations, public safety, street repairs, public facilities, code enforcement and business licensing.
For the competition, the CSU teams are given real-time data from sensors placed on streetlights throughout downtown San Diego, said Anand Panangadan, CSUF assistant professor of computer science and coordinator of the GE Digital CSU Challenge.
"These sensors can detect pedestrians, traffic, parking, and environmental data such as temperature and humidity," Panangadan said. "The challenge is to use this live data and other datasets to build a software application to tackle an urban challenge, and in particular, helping San Diego realize their climate action plan of eliminating half of all greenhouse gas emissions in the city and striving for all electricity used in the city to be from renewable sources by 2035."
The CSUF student team has developed a "microclimate app" to assess air quality and detect such health hazards as algae bloom and acid rain, said team member and computer science major Austin Suarez.
"We're focusing on the temperature, humidity and pressure sensors," Suarez added. "With the help of data from these sensors, the application would generate a map at a micro level that will determine areas susceptible to public health concerns. As cities are getting impacted by increases in population, it's crucial to know more about the air quality and possible health threats."
For the competition, students learn to build a software application to address a real problem using real-world datasets, Panangadan explained. "Students are encouraged to work in interdisciplinary teams and think not only about the technical aspects of their application, but also about the potential users of their application. Their software idea can have a real impact on the city of San Diego."
For the students, being in the forefront of this emerging technology gives them a competitive edge in finding jobs after graduation, Suarez added.
"Our society is changing incredibly fast — everything from smart coffee makers to self-driving cars, with millions of devices connecting to the internet every year. Building the foundation of the industrial internet is not only important now, but to how our society will continue to evolve."
In addition to Suarez, CSUF team members and their majors are: seniors Nara Dashdondog, business administration-operations and supply chain management concentration; Maygan Hooper and Jonathan Moubayed, both computer science; junior Jonathan Schinowsky, computer engineering; and computer science graduate student Shripal Mithun Rawal.
Faculty advisers for the CSUF student team are Kenneth "John" Faller, associate professor of computer engineering, and Mikhail Gofman, associate professor of computer science and director of the CSUF Center for Cybersecurity.
The other student teams are from Cal State Los Angeles, Cal State Northridge, Cal Poly San Luis Obispo, Sacramento State, San Diego State, San Francisco State and San José State.
With its "Titan Power App," the CSUF team won first place in the 2016 inaugural challenge.
GE Digital in 2017 awarded CSUF $450,000 in funding over three years to support the student design challenge. Alumnus Bill Ruh, GE Digital's chief executive officer, was instrumental in creating this opportunity for students. Ruh '83, '84 (B.S., M.S. computer science) also GE's senior vice president and chief digital officer was a Class of 2017 commencement speaker and is a recipient of the 2017 Distinguished Alumnus Award.
All News Topics A-Z Athletics
CSUF Facts Contact Media Relations Find an Expert Privacy Policy
Subscribe / Download
This site is maintained by Strategic Communications.
To report problems or comments, please contact strategiccomm@fullerton.edu.
© California State University, Fullerton. All Rights Reserved.
Learn about web accessibility Report a web accessbility problem Download Adobe Acrobat Reader Microsoft Viewers
Some page features may require javascript to run.


text:
Guhyeong of Geumgwan Gaya, also often Guhae (r. 521–532) was the tenth and final ruler of Geumgwan Gaya, a Gaya state of ancient Korea.  He was the son of King Gyeomji and Queen Suk.

Faced with an onslaught of Silla forces under King Beopheung, King Guhyeong chose to surrender freely, and brought his family and his treasures to Silla.  He was received with ceremony and his family were admitted to the second-highest rank of the Silla bone rank system, the "true bone."  The king was given the rank of Sangdaedeung, and permitted to keep his former territory as sigeup stipend land.  According to the Samguk Yusa, this occurred either 520 or 490 years after the kingdom's legendary founding by King Suro.

Family
Father: King Gyeomji (겸지왕, 鉗知王)
Mother: Lady Suk (숙부인, 淑夫人)
Wife: Lady Gyehwa (계화부인, 桂花夫人) – daughter of a suijil named Bunjil (분질).
1st son: Gim Sejong (김세종, 金世宗) – father of Gim Solji (김솔지, 金率支).
2nd son: Gim Muryeok (김무력, 金武力) – father of Gim Seohyeon (김서현, 金舒玄).
3rd son: Gim Mudeuk (김무득, 金武得) – father of Gim Changhyeon (김창현, 金昌玄).

See also
 List of Korean monarchs
 History of Korea
 Gaya confederacy
 Three Kingdoms of Korea

Notes

References

Kim Bu-sik.  Silla Bon-gi, Samguk Sagi.

Gaya rulers
6th-century monarchs in Asia

redpajama_set_name: RedPajamaWikipedia


text:
Glyvrar (IPA: , danska: Glibre) är en ort på Färöarna, belägen i Runavíks kommun på ön Eysturoy. Glyvrar hade år 2015 391 invånare.

Glyvrar är en av de flera orter på östsidan av fjorden Skálafjørður som växt ihop till en tio kilometer lång konurbation, liknande agglomeration.

I Glyvrar finns ett forntidsmuseum (Bygdasavnið Forni). Kyrkan i orten är ursprungligen från 1927 men återbyggd år 1981. Mellan 1903 och 1928 fanns det en skola för marina navigatörer. De som examinerades härifrån kunde bli kapten på fiskskepp. Den största arbetsgivaren i Glyvrar är fiskefabriken Bakkafrost.

Befolkningsutveckling

Referenser

Externa länkar

 Faroe Islands.dk - Glyvrar
 Bakkafrost (engelska)

Orter på Eysturoya sýsla


The absurd comedy series acknowledges the reach of the Fall, and offers a despairing answer.
Rick and Morty might be one of the most unexpectedly intellectual shows on television. The animated series, about the galaxy-hopping adventures of nihilistic mad scientist Rick and his grandson Morty, has a simple aesthetic—including uncomplicated character design and coloring—that nonetheless is used to create visually complicated scenes in which absurdism functions as commentary. An episode about mass mind control considers the fallibility of free will, for instance, while in another McDonald's dipping sauce becomes a metaphor for Rick's motivations. All of the strange visuals, plots, and ideas converge to create a unique portrayal of brokenness.
Most narratives involve brokenness to some extent; conflict is essential to a good story. Rick and Morty goes one step further. The brokenness in the show encompasses more than individuals or even society; it's recognized as an undeniable part of reality itself.
Take, for example, "The Ricks Must Be Crazy." In this episode, we learn that Rick has created a miniature universe in order to power his futuristic car battery. Rick instructs the microverse's population to use stepping machines to generate power for their cities, not telling them that he steals the majority of power for himself. The inhabitants gleefully comply, not knowing that Rick created them to be more or less slaves.
Although the microverse inhabitants are flawed creatures that cannot free themselves from Rick, the ultimate flaw is that their reality is structured in a way that enforces slavery. Even if all the inhabitants figured out Rick's deception, they would be unable to do anything about it. If Rick's car stops working, then he can just destroy their world and create another. Reality, not only humanity, is inherently unfair for the microverse inhabitants.
Another example is found in the episode called "Morty's Mind Blowers." Rick, unsatisfied with Morty's inability to create a level shelf, turns a section of the floor into what he calls "true level." Morty steps on the section of floor and immediately experiences unparalleled bliss. The feeling of being on a truly level surface is so overwhelming that Morty cannot go back to standing anywhere else. When Morty leaves the true level surface, he freaks out and yells, "Everything is crooked!" Rick eventually erases Morty's memory of true level in order to preserve his grandson's sanity.
People usually assume the ground they stand on is flat, possibly close to being truly level. Rick and Morty instead says, "Everything is crooked." We are just too used to the crookedness to notice. Just as Morty initially cannot comprehend the joys of standing on a truly level surface, people cannot begin to picture a perfect world due to their existence in a broken reality.
It's honest and true to acknowledge reality's brokenness.
Rick and Morty's portrayal of brokenness is not dissimilar from the biblical narrative. In the story of the Fall, God did not only curse Adam and Eve. He cursed the ground itself, implying that Adam and Eve's decision to sin had repercussions on the nonhuman world. When God removed Adam and Eve from the Garden of Eden, he was doing more than acknowledging their sinfulness. Much like Morty leaving the wonders of true level, Adam and Eve had to move from a land in perfect unity with God to one that was broken.
While Rick and Morty's portrayal of a corrupt universe surprisingly aligns with Christianity in some ways, it should be noted that the show's answer to corruption is much different. Rick and Morty rejects religion as an answer to the universe's brokenness, frequently displaying religion as inadequate at best and corrupt at worst. In one episode, Rick even humiliates Satan with relative ease through only science and intellect.
Rick and Morty's answer to brokenness can be boiled down to Rick's catchphrase for whenever Morty sees something disturbing: "Don't think about it." While most characters in Rick and Morty are too dumb to ponder the nature of reality, Rick follows his own advice through a nonstop stream of alcohol and misadventures. As long as Rick is preoccupied, he is distracted from what he views as a cold, meaningless existence.


text:
Q: Please tell me how to write sql query to seacrh smart account number input format
*

*User types first three digits of product code and account number without prefix zeros

*System automatically converts it into full account number in collection, transaction screen

Example:
Account Number: 00200600000123
User Types: 006123
002 - Branch Code
006 - Product Code
00000123 - Account Number

As the system already knows the login branch code, it adds 002 and adds zero prefix to account number

A: You can use the below to generate the smart number from the branch table using branch_code and user_input
  SELECT branch_code ||substr(:user_input,1,3)||lpad(substr(:user_input,4),9,0)
  FROM branch_table
   where branch_code=global.current_branch;

redpajama_set_name: RedPajamaStackExchange


Below is a growing body of multimedia resources. Check back to this page for more installments in the future! Also, don't forget our Resources page for further resources in text essay form. For our most in-depth materials, please see our Educational and Inspirational Spiritual Naturalist Archives accessible by members of the Society.
Click here to see our recommendations of videos produced by others on YouTube.
The Spiritual Naturalist Dialogues is a growing and ongoing series of audio posts (podcasts) that will feature conversations on topics of interest to Spiritual Naturalists. These are available to Supporting Members of the Society. Below is a sample episode! If you would like to learn more about joining the Society, please see this link.
RITUAL, with B.T. Newberg & DT Strain [20 minutes].
– Deconstructing the Christmas Gift – SNS Director, DT Strain interviewed by John Hockenberry of "The Takeaway" for Public Radio International and WNYC, with the New York Times and WGBH Boston.
– Is it possible to think too much?
– What is more important: honesty or compassion?
– How do Humanists do spirituality?
More resources are available to Society members. Find out more about membership in the Society here!


text:
Q: UCM dynamicview config spec : excluding all *.xml but include build.xml I am using Clearcase UCM with a dynamic view. (On linux)
In my view there many files ending in .xml. Some of there are  "build.xml"  files, others are data
files.  I want to view only "build.xml" files in my view.
Following line in config spec  excludes all the "*.xml" files.
element *.xml -none

How can I include just the "build.xml" files?

A: Just add the select rule before the non-select rule
element build.xml .../yourStream/LATEST
element build.xml yourBaseline
element *.xml -none

Note: those rules should be put at the beginning of the UCM config spec of your view, otherwise the usual UCM select rules would be applied first, and you would end up seeing all files within your component.


text:
Location: Jacksonville, FL (USA)
01/08/2020 Retail Operations Associate (Early Morning) DICK'S Sporting Goods Jacksonville, FL similar
01/08/2020 Retail Sales Associate (All positions) DICK'S Sporting Goods Jacksonville, FL similar
01/08/2020 Retail Operations Associate DICK'S Sporting Goods Jacksonville, FL similar
01/08/2020 Retail Sales Associate - Lodge DICK'S Sporting Goods Jacksonville, FL similar
01/10/2020 Retail Sales Associate (All positions) DICK'S Sporting Goods Orange Park, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Jacksonville, FL similar
01/17/2020 Block Advisors - Associate Team Leader H&R BLOCK Jacksonville, FL similar
01/11/2020 Retail Store Management The Men's Wearhouse Jacksonville, FL similar
01/08/2020 Retail Customer Service Specialist DICK'S Sporting Goods Jacksonville, FL similar
01/16/2020 Part Time Retail Inventory Associate RGIS Palatka, FL similar
01/10/2020 Part Time Retail Inventory Associate RGIS Saint Augustine, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Atlantic Beach, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Orange Park, FL similar
01/16/2020 Retail Store Management Men's Wearhouse Orange Park, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Jacksonville Beach, FL similar
01/13/2020 Retail Store Management Men's Wearhouse Jacksonville Beach, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Green Cove Springs, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Middleburg, FL similar
01/17/2020 Associate Team Leader H&R BLOCK MacClenny, FL similar
01/17/2020 Associate Team Leader H&R BLOCK Palatka, FL similar
Results 1 - 20 of 20 matches

redpajama_set_name: RedPajamaCommonCrawl


text:
Bhudson (talk | contribs)
(→Another Example:)
Kkc2suen (talk | contribs)
m (→Simulated Annealing)
2. If <math>h(y)>h(x)</math>, then e(h(y)-h(x))/T->0. Therefore r->0, we almost never accept y.

3, if r is equal to 1 or close to 1, then we accept the move. If r close to 0, then that means the probability of the move is close to 0, so we almost reject.
3. if r is equal to 1 or close to 1, then we accept the move. If r close to 0, then that means the probability of the move is close to 0, so we almost reject.
Essentially, the smaller the value of T, the sharper the distribution, and the higher the probability of rejection. We start by picking T large so that there is a lower probability of rejection which is more efficient. The algorithm will then be able to explore the target distribution instead of rejecting all proposed points and just repeating the previous state. Note though that the convergence of this algorithm to an accurate estimate of the global minimum is not guaranteed. We can never be sure if we have escaped the local minimums, if it is a complex example and there are a lot of them. However, with a large enough T, and reasonable choice of 'b' in the proposal density the algorithm should work for most functions.
3.1.1 Advantages of the Inverse Transform Method
4.1 Continuous Case
13.4 Formal Definition:
13.10 Multivariate
13.11 Vector A/R Method
13.12 Common distribution
13.13 Exponential
13.14 Normal
16 Properties of Markov Chain (continued)
17 Examples of finding stationary distribution
18.3 Alternate Example
18.4 Explanation
19.2 Damping Factor "d" (http://en.wikipedia.org/wiki/PageRank)
19.3.4 Another Example:
22.1.2 b too large
22.1.3 b just right
24 Motivation: Simulated Annealing and the Travelling Salesman Problem
1. Classification: Given an input object X, we have a function which will take in this input X and identify which 'class (Y)' it belongs to (Discrete Case)
2. Regression: Same as classification but in the continuous case except y is non discrete. (Example of stock prices)
3. Clustering: Use common features of objects in same class or group to form clusters.(in this case, x is given, y is unknown)
4. Dimensionality Reduction (aka Feature extraction, Manifold learning): Used when we have a variable in high dimension space and we want to reduce the dimension.
In order to perform a simulation study, we must first:
 1. Use a computer to generate (pseudo) random numbers.
2. Use these numbers to generate values of random variable from distributions.
3. Using the concept of discrete events, we show how the random variables can be used to generate the behavior of a stochastic model over time. (Note: A stochastic model is the opposite of deterministic model, where there are several directions the process can evolve to)
4. After continually generating the behavior of the system, we can obtain estimators and other quantities of interest.
Pseudo Random Numbers are the numbers that seem random but are actually deterministic. Although the pseudo random numbers are deterministic, these numbers have a sequence of value and all of them have the appearance of being independent uniform random variables. Being deterministic, pseudo random numbers are valuable and beneficial due to the ease of generation and manipulation.
When people do the test many times, the results will be the closed express values, which make the trial look deterministic, however for each trial, the result is random. So, it looks like pseudo random numbers.
2 = 30 mod 7
The modulo operation is useful for determining if an integer divided by another integer produces a non-zero remainder. But both integers should satisfy n = mq + r, where m, r, q, and n are all integers, and r is smaller than m.
If [math]x_0=7[/math] and [math]x_n=(9x_{n-1}+5)\mod 476[/math], find [math]x_1,\cdots,x_{5}[/math].
[math]\begin{align} x_1 &{}= (9 \times 7+5) &{}\mod{200} &{}= 68 \\ x_2 &{}= 615 &{}\mod{200} &{}= 139 \\ x_3 &{}= 1256 &{}\mod{200} &{}= 304 \\ x_4 &{}= 2741 &{}\mod{200} &{}= 406 \\ x_5 &{}= 3659 &{}\mod{200} &{}= 327 \\ \end{align}[/math]
If [math]x_0=3[/math] and [math]x_n=(5x_{n-1}+7)\mod 200[/math], find [math]x_1,\cdots,x_{10}[/math].
[math]\lt math\gt Insert formula here[/math][math]\lt math\gt Insert formula here[/math]</math></math>=== Inverse Transform Method === Now that we know how to generate random numbers, we use these values to sample form distributions such as exponential. However, to easily use this method, the probability distribution consumed must have a cumulative distribution function (cdf) [math]F[/math] with a tractable (that is, easily found) inverse [math]F^{-1}[/math].
Proof of F(x) is Uniformly Distributed:
P(F(x)<u)=P(F-1(F(x))<F-1(u))=P(x<F-1(u))=F(F-1(u))=u
So F(x)~U(0,1).
>> u = rand;
>> theta  = 1;
>> lambda = 1;
>> if u < 0.5
X = theta + (1/lambda) * log(2u);
X = theta - (1/lambda) * log(2(1-u));
>>x=rand^(1/5)
>> x = 1-(1-u)^(1/3);
This command allows users to explore the effect of changes of parameters on the plot of either a CDF or PDF.
1. Draw u~U(0,1)
2. X = F-1(u)
This same technique can be used to sample from discrete distribution.
Further, the pdf [math]f(x) = \frac{1}{b-a}[/math] and 0 otherwise.
Advantages of the Inverse Transform Method
It is very easy to use and apply if we are able to find the inverse cdf [math] F^{-1}(\cdot)[/math].
It preserves monotonicity and correlation, which consequently helps in order statistics, variance reduction methods, and also generating truncated distributions.
Though this method is very easy to use and apply, it does have some major disadvantages/limitations:
Since a number of comparisons are required, the speed of this method is often very slow.
We need to find the inverse cdf [math] F^{-1}(\cdot) [/math]. In some cases the inverse function does not exist, or is difficult to find.
[Discrete Case] The same technique can be used for discrete case. We want to generate a discrete random variable x, that has probability mass function:
else if U < 0.97 then output 0
else output 1
>> u = rand;              # pick up F(x);
>> if u < 0.5             # Pr(x = -1)=0.5;
x = -1;
elseif u< 0.8          # Pr(x = 2) =0.8-0.5 =0.3
elseif u < 0.9         # Pr(x = -2)=0.9-0.8 =0.1
elseif u < 0.97        # Pr(x = 0) =0.97-0.9=0.07
else                   # Pr(x = 1) =1 - 0.97=0.03
end                    # total probability:0.5+0.2+0.2+0.07+0.03=1
size(x)
>> x = u ^ (1/2);
>> P = .3   % p from (0,1)
>> if u < (1-p)
Another method:
then if the [math]x_{i}[/math],[math]i \geq [/math], are ordered so that [math]x_{0}\lt x_{1}\lt x_{2}\lt ...[/math] and if we let F denote the distribution function of X, then [math]F(x_{k}) = \sum p_{i}[/math] and so
X will equal [math]x_{j}[/math] if [math]F(x_{j-1}) \leq U \leq F(x_{j})[/math]
Continuous Case
Example 3.8: Generating a Weibull(a,b) distribution
Let X ~ Weibull(a,b). Write an algorithm to generate X.
The PDF of X is:
[math]f(x) = ab^{-a}x^{a-1}exp((-x/b)^a)[/math] ; x > 0
The CDF of X is:
[math]F(x) = 1-exp((-x/b)^a)[/math] ; x > 0
Solve for U = F(X) for X:
[math]U = 1-exp((-x/b)^a)[/math]
<=> [math]-(X/b)^a=ln(1-U)[/math]
<=> [math](X/b)=(-ln(1-U))^{1/a}[/math]
<=> [math]X=b(-ln(1-U))^{1/a}[/math]
1. Generate U~U(0,1) <- Note: Generating U and 1-U is the same since they are still U(0,1)
2. Return [math]X=b(-ln (U) )^{1/a}[/math]
A simple example: Simulating an Exponential Random Variable: If F(x)=1-exp(-x), then F-1(u) is that value of x such that
1-exp(-x)=u
x= -log(1-u)
Hence, if U is a uniform(0,1) variable, then
F-1(u)=-log(1-U)
is exponentially distributed with mean1. Since 1-U is also uniformly distributed on (0,1) it follows that -logU is exponential with mean 1. Since cX is exponential with mean c when X is exponential with mean 1, it follows that -clogU is exponential with mean c.
this is well worth reading
(first step:draw Y~g(.))
(under any pdf, the area=1)
so a sample of g results to a sample of f.
-Acceptance-Rejection Method is not good for all cases. The limitation with this method is that sometimes many points will be rejected. One obvious cons is that it could be very hard to pick the [math]g(y)[/math] and the constant [math]c[/math] in some cases. We have to pick the SMALLEST C such that [math]cg(x) \leq f(x)[/math] else the the algorithm will not be efficient. This is because [math]f(x)/cg(x)[/math] will become smaller and probability [math]u \leq f(x)/cg(x)[/math] will go down and many points will be rejected making the algorithm inefficient.
[math]f(x)=Pr(X=x)=2Cx*(0.5)^2[/math]
3.	If [math](y=0)[/math] and [math](v\lt 1/2), output=0[/math]
If [math](y=2) [/math] and [math](v\lt 1/2), output=2 [/math]
c is the expected number of times the code runs to output 1 random variable. Remember that when [math]u \lt f(x)/(cg(x))[/math] is not satisfied, we need to go over the code again.
In other words, a [math]C[/math] is chosen to make sure [math] c \cdot g(x) \geq f(x) [/math]. However, it will not make sense if [math]C[/math] is simply chosen to be arbitrarily large. If [math]C[/math] is too large, the probability of this sample is too small. We need to choose [math]C[/math] such that [math]c \cdot g(x)[/math] fits [math]f(x)[/math] as tightly as possible.
The Acceptance-Rejection method involves finding a distribution that we know how to sample from (g(x)) and multiplying g(x) by a constant c so that [math]c \cdot g(x)[/math] is always greater than or equal to f(x). Mathematically, we want [math] c \cdot g(x) \geq f(x) [/math]. And it means c has to be greater or equal to [math]\frac{f(x)}{g(x)}[/math]. So the smallest possible c that satisfies the condition is the maximum value of [math]\frac{f(x)}{g(x)}[/math]
Where Γ (n)=(n-1)! if n is positive integer
>>x=u.^0.5;  %square root of each element of u.
Matlab Tip: Periods, ".",meaning "element-wise", are used to describe the operation you want performed on each element of a vector. In the above example, to take the square root of every element in U, the notation U.^0.5 is used. If we don't have the ".", there will be an error. Input must be a scalar and a square matrix. However if you want to take the Square root of the entire matrix U the period, "*.*" would be excluded. i.e. Let matrix B=U^0.5, then [math]B^T*B=U[/math]. For example if we have a two 1 X 3 matrices and we want to find out their product; using "." in the code will give us their product. However, if we don't use ".", it will just give us an error. For example, a =[1 2 3] b=[2 3 4] are vectors, a.*b=[2 6 12], but a*b does not work since matrix dimensions must agree.
>> ii = 1
>> while  ii < 1000   % example of generating 1000 points
y = 2 * u1 - 1;  % make y uniform over (-1,1)
if u2 <= (1 - y^2)
Simple example of Acceptance-Rejection Method: Generate a random variable having density function f(x)=20x[(1-x)^3], 0<x<1 Find c such that C>=f(x)/g(x), we use calculus to determine the maximum value of
f(x)/g(x)= 20x[(1-x)^3]
d/dx[f(x)/g(x)] = 20[(1-x)^3 - 3x(1-x^2) ] Setting this equal to 0 shows that the maximal value is attained when x=0.25, and thus f(x)/g(x) <= 20(0.25)[(0.25)^3] = 135/64 ≅c Hence, f(x)/cg(x) = (256/27)x[(1-x)^3]
Procedure: i. Generate random numbers U1 and U2 ii.If U2 <= (256/27)U1[(1-U1)^3], stop and set X=U1. Otherwise return to step i. (From textbook: Introduction to Probability, 10th Edition, Sheldon M.Ross)
Let [math] f(x) = x^3 [/math] for [math] 0\lt x\lt \sqrt{2} [/math]. Use acceptance-rejection method with the proposal distribution, [math] g(x)=x [/math] for [math] 0\lt x\lt \sqrt{2} [/math]
[math] c=max(\frac{f(x)}{g(x)}) = max(\frac{x^3}{x}) = max(x^2) = (\sqrt{2})^2 = 2 =\gt \frac{f(x)}{c \cdot g(x)} = \frac{x^2}{2} [/math]
Hence, the algorithm is:
1. Generate [math] y \sim~ U(0,1) [/math]
2. Generate [math] U \sim~ U(0,1) [/math]
3. If [math] U \leqslant \frac{y^2}{2} [/math]. Then X=y, else go to step 1.
-> Proposal distribution: g(x)=1\2R, x belongs to UNIF(-R, R)
-> We want to generate it to [math] U \sim UNIF (0,1) [/math] Let [math] Y= [R-(-R)]U+(-R)=2RU-R=R(2U-1)[/math], therefore Y follows [math]U(-R,R)[/math]
(In this example, we will see how to determine the value of c when c is a function with unknown parameters instead of a value) Let [math]f(x)=x*e^{-x}, x\gt 0 [/math]
Use [math]g(x)=a*e^{-a*x}[/math]to generate random variable
We can use the value of c to calculate the acceptance rate by '1/c'.
For instance, assume c=1.5, then we can tell that 66.7% of the points will be accepted (1/1.5=0.667). We can also call the efficiency of the method is 66.7%.
Step 1. Draw discrete uniform distribution of 1, 2, 3, 4 and 5, [math]Y \sim~ g[/math].
Step 2. Draw [math]U \sim~ U(0,1)[/math].
Step 3. If [math]U \leq \frac{f(Y)}{c \cdot g(Y)}[/math], then X = Y ;
Note: The U is independent from y in Step 2 and 3 above. The constant c is an indicator of rejection rate or efficiency of the algorithm.
Since g follows a discrete uniform distribution, the probability is the same for all variables. And since there are 5 parameters (1,2,3,4,5), g(x)=1/5=0.2.
Remember that we always want to choose [math] c/timesg [/math] to be equal to or greater than [math] f [/math], but as close as possible.
limitations: If the form of the proposal distribution g is very different from the target distribution f, then c is very large and the algorithm is not computationally effective.
For example, if c = 1.5, the acceptance rate would be [math]\frac {1}{1.5}=\frac {2}{3}[/math]. This means about 66% of points are accepted. Thus, in order to generate 1000 random values, on average, a total of 1500 iterations would be required.
[math]c=max(p_{x}/g(x))=0.6/(1/3)=1.8[/math]
Hence p(x)/cg(x) = p(x)/(1.8*1/3)= p(x)/0.6
>> while ii < 1000
j = floor((log(u1)/log(.75)) + 1;
pj = (e^3) * (3^j)/fact(j);
gj = .25 * (1 - .25)^j
if u2 < pj / (2.12 * gj)
x(ii) = j;
>> hist(x)
Neither Inverse Transformation nor Acceptance/Rejection Method can be easily applied to Gamma distribution. However, we can use additive property of Gamma distribution to generate random variables.
In other words, the Box-Muller method is a method of producing two independent standard normals from two independent uniforms.
Basic Form:
Let U1 and U2 ~ U(0,1). Assuming U1 & U2 are independent, and let:
1) [math]Z_0 = R \cos(\Theta) =\sqrt{-2 \ln U_1} \cos(2 \pi U_2)\,[/math]
2) [math]Z_1 = R \sin(\Theta) = \sqrt{-2 \ln U_1} \sin(2 \pi U_2)\,[/math]
where both Z0 and Z1~N(0,1) are independent, with corresponding polar coordinates:
[math]R^2 = -2\cdot\ln U_1\,[/math]
[math]\Theta = 2\pi U_2\,[/math]
R2 here has Chi-Squared distribution with df = 2 since it is just the square of the norm of the standard bivariate normal variable (X,Y). For the special case where df = 2, chi-squared distribution is the same as the exponential distribution. Hence, R2 is simply obtainable by generating the required exponential variate.
Source: https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform
Step 1: Generate [math]u[/math]1~[math]Unif(0,1)[/math] Step 2: Generate [math]Y[/math]1~[math]Exp(1),Y[/math]2~[math]Exp(2)[/math] Step 3: If [math]Y2 \geq(Y-1)^2/2[/math],set [math]V=Y1[/math],otherwise,go to step 1 Step 4: If [math]u1 \leq 1/2[/math],then [math]X=-V[/math]
More intuitively, because x is an odd function (f(x)+f(-x)=0). Taking integral of x will give [math]x^2/2 [/math] which is an even function (f(x)=f(-x)). If support is from negative infinity to infinity, then the integral will return 0.
The special case of the normal distribution is standard normal distribution, which the variance is 1 and the mean is zero. If X is a general normal deviate, then Z = (X − μ)/σ will have a standard normal distribution.
while (i <= n)
The inverse method is universal in the sense that we can potentially sample from any distribution where we can find the inverse of the cumulative distribution function. However, this is not always the case as some functions do not have an inverse while others may be difficult to find. As such, there exist different procedures such as Acceptance-Rejection which is outlined in a further lecture.
1. The preceding can be written algorithmically as Generate a random number U. If U<p0 set X=x0 and stop. If U<p0+p1 set X=x1 and stop....
2. If the xi, i>=0, are ordered so that x0<x1<x2<... and if we let F denote the CDF of X, X will equal xj if Fxj-1<=U<Fxj
1. generate u ~ Unif[0, 1)
2. Set x = U1/n
For example, when n = 20,
u = 0.6 => x = u1/20 = 0.974
Observe from above that the values of X for n = 20 are close to 1, this is because we can view Xn as the maximum of n independent random variables X, X~Unif(0,1) and is much likely to be close to 1 as n increases. This is because when n is large the exponent tends towards 0. This observation is the motivation for method 2 below.
1) Generate U, V ~ [math]U(0,1)[/math]
2) If u < p1, v=[math]F_{X_{1}}(x)[/math]-1
3) Else if u < p1+p2, v=[math]F_{X_{2}}(x)[/math]-1
4) ....
else if [math]u\lt \frac{2}{3}, x = v\lt sup\gt \frac{1}{2}\lt /sup\gt [/math]
else [math]x = v\lt sup\gt \frac{1}{3}\lt /sup\gt [/math]
if <math>u<\frac{1}{3}</math>
elseif <math>u<\frac{2}{3}</math>
Pro: This method allows us to sample an unknown distribution from a easy distribution. Con: This method may have to reject many points, which is inefficient.
Suppose we want to sample from f(x), we can write f(x)=[math]\int _{0}^{f(x)}du[/math]. Thus, f(x) can be thought as the marginal distribution of (X, U) ∼ U{(x, u):0 <u<f(x)}.
Theorem: Simulating X ∼ f(x)is equivalent to simulating (X, U) ∼ U{(x, u):0 <u<f(x)}.
The beta distribution maximized at 0.5 with value [math](1/4)^n[/math]. So, [math]c=b*(1/4)^n[/math] Algorithm: 1.Draw [math]U_1[/math] from [math]U(0, 1)[/math].[math] U_2[/math] from [math]U(0, 1)\lt math\gt 2.If \lt math\gt U_2\lt =b*(U_1)^n*(1-(U_1))^n/b*(1/4)^n=(4*(U_1)*(1-(U_1)))^n[/math]
In this lecture, we will discuss algorithms to generate 3 well-known distributions: Binomial, Geometric, and Poisson. For each of these distributions, we will first state its general understanding, probability mass function, expectation, and variance. Then, we will derive one or more algorithms to sample from each of these distributions, and implement the algorithms utilizing Matlab.
The Bernoulli distribution is a special case of the binomial distribution, where n = 1. X ~ Bin(1, p) has the same meaning as X ~ Ber(p), where p is the probability if the event success, otherwise the probability is 1-p (we usually define a variate q, q= 1-p). Bin(n, p), is the distribution of the sum of n independent Bernoulli trials - Bernoulli(p), each with the same probability p, where 0<p<1.
p p(1-p) [math]\begin{cases} 1-p & \text{for }k=0 \\ p & \text{for }k=1 \end{cases}[/math] [math]\begin{cases} 0 & \text{for }k\lt 0 \\ 1-p & \text{for }0\leq k\lt 1 \\ 1 & \text{for }k\geq 1 \end{cases} [/math] [math]1-p+pe^t\,[/math]
p = 0.1;            # define the prob. p
The binomial distribution is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p. (Definition is copied from:http://en.wikipedia.org/wiki/Binomial_distribution) Let X~Bin(n,p), then:
[math] np [/math] [math] np(1-p) [/math] (nCx) px(1-p)(n-x), x=0,1,...n
[math]\sum_{i=0}^{x}{n\choose i}p^i(1-p)^{n-i}[/math] (1-p+pet)n
Generate n uniform random number [math]U_1,...,U_n[/math] and let X be the number of [math]U_i[/math] that are less than or equal to p. The logic behind this algorithm is that the Binomial Distribution is simply a summation of n Bernoulli trials, each with probability of success p. Thus, we can say equivalently that sampling from a Bin (n, p) distribution is the same as sampling from n Bernoulli trials. In the example below, we are sampling 1000 realizations from 20 Bernoulli random variables. By summing up the rows of the 20 by 1000 matrix that is produced, we are summing up the 20 Bernoulli outcomes to produce one binomial sampling. We have 1000 rows, which means we have realizations from 1000 binomial random variables when this sum is done (the output of the sum is a 1 by 1000 sized vector).
MATLAB tips: to get the pdf f(x), we can use code binornd(N,P). N represents the number of trials and P is the probability of success. a=[2 3 4],if set a<3, will produce a=[1 0 0]. If you set "a == 3", it will produce [0 1 0]. If a=[2 6 9 10], if set a<4, will produce a=[1 0 0 0], because only the first element (2) is less than 4, meanwhile the rest are greater. So we can use this to get the number which is less than p.
>>rand(20,1000)   # if we want to generate 20 times; retry the trail 20 times.
remark: a=[2 3 4],if set a<3, will produce a=[1 0 0]. If you set "a == 3", it will produce [0 1 0].
Geometric distribution is a discrete distribution. There are two types of geometric distributions. 1. Generate the probability distribution of X Bernoulli fail trials (probability 1-p), until the first success (probability p). X belongs in the set {1, 2, 3, ...}. 2. Generate probability distribution of Y = X - 1 failures (probability 1-p) before the first success (probability p). Y belongs in the set {0, 1, 2, 3, ...}.
If the success event showed at the second time and failed at the first time, which x=2, then f(x)=p(1-p).
If the success event showed at the third time and failed at the first and second time, which x=3, then f(x)= p(1-p)(k-1). etc.
If the success event showed at the x time and all failed before time x, which x=x, then f(x)= p(1-p)(k-1)
n P(1-P)(n-1)(number of x-1 failures)
Memorylessness properties : P(X>m+n|X>=m)=P(X>n)
If Y~Exp([math]\lambda[/math]) then X=floor(Y)+1 is geometric.
P(X>x) = P( floor(Y) + 1 > X) = P(floor (Y) > x- 1) = P(Y>= x) = e(-[math]\lambda[/math] * x)
Now, let [math]Y=e^{\lambda}[/math] => x=floor(Y) +1
2) Set X= floor(Y)+1, to generate X
Definition: In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since the last event. The Poisson distribution can also be used for the number of events in other specified intervals such as distance, area or volume. (from Wikipedia) In short, the Poisson distribution measures the number of occurrences at a particular time interval, given the rate of occurrences per unit time.
If customers independently come to bank over time, all of the following exponential distributions with rate [math]\lambda[/math] per unit of time, then X(t) = # of customer in [0,t] ~ Poi[math](\lambda t)[/math]
The beta distribution is a continuous probability distribution. There are two positive shape parameters (i.e. greater than zero) in this distribution, defined as α and β. X falls within the interval [0,1]. The parameter α is used as exponents of the random variable. The parameter β is used to control the shape of the this distribution. We use the beta distribution to build the model of the behavior of random variables, which are limited to intervals of finite length. For example, we can use the beta distribution to analyze the time allocation of sunshine data and variability of soil properties.
and [math]f(x;\alpha,\beta)= 0 [/math] otherwise Note: [math]\Gamma(\alpha)=(\alpha-1)! [/math] if [math]\alpha[/math] is a positive integer. However, several other authors, including W. Feller choose to exclude the ends x = 0 and x = 1, (such that the two ends are not actually part of the density function) and consider instead 0 < x < 1. Another notation for beta-distributed random variables is X~Be([math]\alpha, \beta[/math]).
Vanriance
[math]\frac{\alpha}{\alpha + \beta}[/math] [math]\frac{\alpha\beta}{(\alpha+\beta)^2 (\alpha + \beta + 1)}[/math]
The variance of the beta distribution decreases monotonically if [math] \alpha = \beta [/math] and as [math] \alpha = \beta [/math] increases, the variance decreases. The mode of a Beta distributed random variable X with α, β > 1 is [math]\frac{\alpha-1}{\alpha + \beta-2}[/math].
>>Y1 = sum(-log(rand(10,1000)))             #Gamma(10,1), sum 10 exponential for each of the 1000 samples
>>Y2 = sum(-log(rand(5,1000)))              #Gamma(5,1), sum 5 exponential for each of the 1000 samples
>>disttool                                   #Check the beta plot. We can change beta here.
If [math]x_1, x_2 \cdots, x_d[/math]'s are independent, then
2) Ui ~ U(0,1) (we want to translate this to U(a,b))
(open->file->function)
function x = urectangle (d,n,a,b)    #urectangle: function name; d:dimension; n:number of sample
%keyboard                       #(or writen only as "keyboard")makes the function stop at this step so you can evaluate the variables
>>scatter(x(1,:),x(2,:))           #another way to scatter points
MATLAB code for using Acceptance-Rejection Method to sample from a d-dimensional unit ball.
u = rand(d,n);      #U1~U(0,1),...,Ud~U(0,1)
z = 1 - 2*u;        #x1=1-2U1
R = sum(z.^2);      #R=sum of (xi)^2, i=1,...,d
R(ii) determines whether the generated random coordinates fall within the unit ball. In 2-D we have a random x and
y, thus if x^2+y^2 <=1 then it falls within the unit ball and we increase our count by 1.
>>[x]=Unitball(2,10000);      %the larger the amount like "10000" , the better the value we will get
>>c=7839/10000                 %efficiency of the acceptance, Efficiency = points accepted / total points
>>4*.7839
3.1356              %area of the circle
>>pi
ans =       3.1416
In statistics, efficiency is a term used in the comparison of various statistical procedures and, in particular, it refers to a measure of the optimality of an estimator, of an experimental design or of a hypothesis testing procedure. Essentially, a more efficient estimator, experiment or test needs fewer samples than a less efficient one to achieve a given performance.
Good luck on the midterm
In other words, stochastic process is non-deterministic. This means that there is some indeterminacy in the final state, even if the initial condition is known.
1. Poisson Process - This is a continuous time counting process that satisfies a couple of properties that are listed in the next section. The Poisson process is understood to be a good model for independent events such as incoming phone calls, number of traffic accidents, and goals during a game of hockey or soccer. It is also an example of a birth-death process.
2. Markov Process - This is a stochastic process that satisfies the Markov property which can be understood as the memory-less property. The property states that the jump to a future state only depends on the current state of the process, and not of the process's history. This model is used to model random walks exhibited by particles, the health state of a life insurance policyholder, decision making by a memory-less mouse in a maze, etc.
Stochastic process always has a state space and the index is set to limit the range. For instances, in a stock market, the set of all non-negative numbers is the state space, while [math]x_t[/math] are individual stock prices.
We can easily simulate a stochastic process by simulating a sequence of random variables. For instance, to simulate the first t time units of a renewal process having inter arrival distribution F we can simulate indepenf=dent random variables X1,X2,... having distribution F, stopping at
N=min{n:X1+...+Xn>t}
The Xi, i>=1, represent the inter arrival times of the renewal precess and so the preceding simulation yields N-1 events by time t -- the events occurring at times X1,X1+X2,....,X1+...+Xn-1. (From textbook, Introdution to probability, 10th Edition, Sheldon M.Ross)
How to generate a multivariate normal with build in function "randn": (example)
>> hist(sum(X(1:2,:)))      %first 2 columns
>>hist(sum(X(1:20,:))) -> approaches to normal
>>u=exprnd(200,1000)
>>hist(sum(u(1:200,:)))    %the graph is exponential
>>hist(sum(u(1,:)))
>>hist(u(1,:))             %each u is uniform
Theorem: Central Limit Theorem Let [math]X_1, ..., X_n[/math] be iid random variables such that [math]E(X_i)=\mu[/math] and [math] Var(X_i)=\sigma^2[/math], and [math] \bar{X} = n^{-1} \left ( \sum_{i=1}^n x_i \right ) [/math].
Then [math] \ \frac{\sqrt{n}(\bar{X} - \mu)}{\sigma} \xrightarrow{d}\ N(0,1)[/math]
The number of arrivals N(t) in a time interval of length t follows Poisson distribution with mean [math]\lambda*t[/math],i.e.
[math]P(N(t)=n) = \frac{e^{-\lambda t} (\lambda t)^n}{n!}[/math]
In probability theory, a Poisson process is a stochastic process which counts the number of events[note 1] and the time that these events occur in a given time interval. The time between each pair of consecutive events has an exponential distribution with parameter λ and each of these inter-arrival times is assumed to be independent of other inter-arrival times. The process is named after the French mathematician Siméon-Denis Poisson and is a good model of radioactive decay,[1] telephone calls[2] and requests for a particular document on a web server,[3] among many other phenomena. By wikipedia
(b) Homogeneity or Uniformity: The number of arrival in each interval I(a,b] is Poisson distribution with rate [math]\lambda (b-a)[/math]
(c) Individuality: for a sufficiently short time period of length h, the probability of 2 or more events occurring in the interval is close to 0
where I denotes the an interval.
In other words, the inter-arrival times are independent and follows Exponential distribution with mean λ.
when we use the inverse-transfer method, we can assume the poisson process to be exp distribution, and get the h function from the inverse method, and sometimes we assume h is very small.
3) Tn - Tn-1 =[math] -\frac {1}{\lambda} [/math] log (Un) (Declare an arrival)(repeat this process many times until Tn >T)
4) if Tn >T stop; else n = n + 1, go to step 2 (go back to step 2 and generate another random)
while T(ii)<=TT       % we want Tn>T
plot(T)
Formal Definition:
The process [math] \{x_n: n \in T\} [/math] is a markov chain if:
The possible values of Xi form a countable set S called the state space of the chain. Markov chains are often described by a directed graph, where the edges are labeled by the probabilities of going from one state to the other states.
Definition: A Markov transition matrix is a square matrix describing the probabilities of moving from one state to another in a dynamic system. In each row are the probabilities of moving from the state represented by that row, to the other states. Thus the rows of a Markov transition matrix each add to one.
A Transition Matrix is used to describe the transitions of a Markov chain. Each of its entries is a non-negative real number representing a probability.
we have the following property (Markov property):
Example of Double-Stochastic Matrix:
Consider the following probability transition matrix.
[math] P= \left [ \begin{matrix} 0 & p & q \\ q & 0 & p \\ p & q & 0 \end{matrix} \right] [/math] Where q=1-p
Each row sums to 1 and each column also sums to 1. Thus, this kind of probability transition matrix is called a Double-Stochastic Matrix.
For all stochastic matrices, each row always sums to 1, but columns do not.
The transition matrix in this case would be:
[math] P=\left [ \begin{matrix} 0.9 & 0.1 & 0 \\ 0 & 1 & 0 \\ 0.3 & 0.7 & 0 \\ \end{matrix}\right] [/math]. Notice the "1" entry at [math] P_{2,2} [/math], even though the image doesn't show that. This is because there is no way of getting out of state 2, hence the probability of staying in state 2 is 1 (cant get out).
cg(x)>=f(x) [math]c=max\left[\frac{f(x)}{g(x)}\right][/math]
-Accept if the point is inside G
Sample uniformly from W
1/λ: The mean of the exponentials and the scale parameter
1. U1, U2, ... Un ~ U(0,1) , independent n uniform distribution
generate uniform directly
use inverse method to generate
this requires attention
[math]1-y=(e^(-\lambda))^x=e^(-\lambda*x)[/math] since [math]1-p=e^-\lambda[/math]
[math]F^(-1)(x)=-1/(\lambda)*log(1-x)[/math]
In probability theory and statistics, the Poisson distribution (pronounced [pwasɔ̃]), named after French mathematician Siméon Denis Poisson, is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since the last event.[1] The Poisson distribution can also be used for the number of events in other specified intervals such as distance, area or volume.
The number of event happened today and the number of event happened tomorrow ,etc and then make it a sequence. This is called Poisson process.
This distribution models the number of times and event occurs in a given time period X~Poi[math](\lambda)[/math]
if [math]u1 \geq e^{-\lambda}[/math], count 1, n=1;
if [math]u1*u2 \geq e^{-\lambda}[/math], count 1, n=2;
if [math]u1*u2*u3 \geq e^{-\lambda}[/math], n=2.
1) x = 0, F = [math]P(X=0) = e^{-\lambda} = p[/math]
4) Else [math]p = \frac{p*\lambda}{x+1} [/math]
Definition: The n-step transition matrix is the matrix [math]P_n[/math] whose elements are the probability of moving from state [math]i[/math] to state [math]j[/math] in [math]n[/math] steps.
[math]P_n (i,j)=Pr(X_{m+n}=j|X_m=i)[/math] is the n-step transition probability.
The probability of [math]X_{n+1}[/math] being in state j given that Xn is in state, i is called the one-step transition probability and is denoted by [math]P_{i,j}(n,n+1)[/math]. That is
[math]P_{i,j}(n,n+1) = Pr(X_{n+1}=j|X_n=i)[/math]

Two-step transition probability:
The probability of moving from state a to state a:
Therefore, [math]P_n = P_1^n [/math]

It is true because of the Markov property or the memoryless property of Markov chains, where the probabilities of going forward to the next state
We can see how [math]P_n = P^n[/math] from the following:
Consider a two-state Markov chain {[math]X_t; t = 0, 1, 2,...[/math]} with states {1,2} and transition probability matrix
c)[math] P(X_2=1|X_0=1)= P_2(1,1) = 5/12 [/math] (Start from state 1 and then get back to it in 3 steps) (1 ->1->1 = (1/2)*(1/2) or 1->2->1 = (1/2)*(1/3))
Consider a 3-state Markov chain {[math]X_t; t = 0, 1, 2,...[/math] with states {1,2,3} and transition probability matrix
[math] P= \left [\begin{matrix} 1/4 & 1/2 & 1/4 \\ 1/3 & 1/3 & 1/3 \\ 1/7 & 2/7 & 4/7 \end{matrix} \right] [/math]
Given [math] X_0=1 [/math]. Compute the following:
a)[math] P(X_2=1, X_1=3 | X_0 = 2) = P(X_2=1|X_1=3)*P(X_1=3|X_0=2)= 2/7 * 1/4 = 1/14 [/math]
b)[math]P(X_2=3|X_0=1) = P(X_2=3|X_1=1)*P(X_1=1|X_0=1)+P(X_2=3|X_1=2)*P(X_1=2|X_0=1)+P(X_2=3|X_1=3)*P(X_1=3|X_0=1)=(1/4)* (1/7)+(1/3)*(2/7)+(1/7)*(4/7)=125/588 [/math]
[math]\underline{\mu_t}~=(\mu_t(1), \mu_t(2),...\mu_t(n))[/math] where [math]\mu_t(1)[/math] is the probability of being on state 1 at time t.
and in general, [math]\mu_t(i)[/math] shows the probability of being on state i at time t.
Given the marginal distribustion at time n-1, we can compute the distribution at time n:
[math]\mu_n~ = \mu_{n-1}~P[/math]
After repeating the algorithm starting at time 0, we can have the following relationship:
Stationary distribution may refer to:
-The limiting distribution in a Markov chain.
-The marginal distribution of a stationary process or stationary time series.
-The set of joint probability distributions of a stationary process or stationary time series.
[math]\pi[/math] is stationary distribution of the transition matrix P if [math]\pi \cdot [/math] P = [math]\pi[/math] which means [math]\pi[/math] is an eigenvector of P with eigenvalue 1.
where [math]\pi[/math] is a probability vector [math]\pi[/math]=([math]\pi[/math]i | [math]i \in X[/math]) such that, all the entries are nonnegative and sum to 1.
In other words, if X0 is drawn from [math]\pi[/math]. Generally, Xn is drawn from the same distribution as [math]\pi[/math] for every n≥0.
Example: consider the following transition matrix
[math] P= \left [ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] [/math]
so how to compute it: use [math]\pi = \pi * P[/math] Intuitively, the chain spends half of the time in each of the states, so [math]\pi[/math] = (1/2,1/2)
1. As n gets bigger and bigger, [math]\mu_n[/math] will possibly stop changing, so the quantity [math]\pi[/math] i can also be interpreted as the limiting probability that the chain is in the state [math]j[/math]
>> mu=[.9 .1]                       %initial distribution
>> mu*p                        % marginal distribution at time 1, enter mu=mu*P, repeat multiple times until the value of the vector mu remains unchanged
An alternate Method of Computing the Stationary Distribution
[math]\mu~=\mu/\Sigma(\mu)[/math]
A Markov Chain consists of a countable (possibly finite) set S (called the state space) together with a countable family of random variables X0,X1,X2,X3,... with values in S such that:
[math]P(X_{t+1}=s \vert X_t=s_t,X_{t-1}=s_{t-1},...,X_0=s_0)=P(X_{t+1}=s \vert X_t=s_t)[/math]
and we refer to this fundamental equation as the Markov property. Note the sufficient property here is that the closest future state is independent of the past states. It is not necessary to be dependent on the current state. Here are some more properties of Markov Chain:
Properties of Markov Chain (continued)
4. Ergodicity
If state i is aperiodic and positive recurrent, state i is said to be ergodic. In other words, state i is ergodic if it has a period of 1 and has finite mean recurrence time. Consequently, an irreducible Markov Chain is said to be ergodic if all states in the chain are ergodic.
In statistics, the term describes a random process for which the time average of one sequence of events is the same as the ensemble average. source: wikipedia An extra note here is that if a finite state irreducible Markov chain has an aperiodic state, then it is ergodic. If there is a finite number N such that any state can be reached from any other state in exactly N steps, a model is said to have the ergodic property. For example, if we have a fully connected transition matrix where all transitions have a non-zero probability, this condition is fulfilled with N=1. A model with more than one state and just one out-going transition per state cannot be ergodic. We will have more examples to follow later on.
5. Steady-state analysis and limiting distributions
Definition: If a Markov Chain is time-homogeneous, then the vector [math]\boldsymbol{\pi}[/math]is called a stationary distribution if [math]\forall j \in S[/math] it satisfies:
1)[math]0\leq\pi_j\leq1[/math]
2)[math]\sum_{j \in S}\pi_j = 1[/math]
3)[math]\pi_j = \sum_{i \in S} \pi_i p_{ij}[/math]
If all states of an irreducible chain are positive recurrent, it has a stationary distribution. In this case, [math]\boldsymbol{\pi}[/math] is unique. It is also related to the expected return time:
[math]\pi_j = \frac{C}{M_j}\,, [/math]
where C is the normalizing constant.
If the chain is both irreducible and aperiodic, then for any i and j,
[math]\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{C}{M_j} [/math]
Final result:
[math]\boldsymbol{\pi}[/math] is called the equilibrium distribution of the chain if the chain converges to the stationary distribution regardless of where it begins.
Source: https://en.wikipedia.org/wiki/Markov_chain
Examples of finding stationary distribution
We will have examples for this later.
Solve the system of linear equations to find the Stationary Distribution
[math]\pi_{0}~ + \pi_{1} + \pi_{2} = 1 [/math]
Solving the 4 equations,
[math]\pi_{0}=\frac {1}{3}[/math], [math]\pi_{1}~=\frac {4}{9}[/math], and [math]\pi_{2}~=\frac {2}{9}[/math]
Therefore [math]\pi=(\frac{1}{3},\frac{4}{9}, \frac{2}{9})[/math]
Similarly, this can be achieved by calculating
[math]P^{30}=\left[ {\begin{array}{ccc} \frac{1}{3} & \frac{4}{9} & \frac{2}{9} \\[6pt] \frac{1}{3} & \frac{4}{9} & \frac{2}{9} \\[6pt] \frac{1}{3} & \frac{4}{9} & \frac{2}{9} \end{array} } \right][/math]
Which produces the same result as solving the systems of equations.
Alternatively, the system of equations can also be solved using matrix simplification. Namely, when the system of equations is more complicated and doesn't simplify easily. Continuing from the above example, we would have [-2/3 1/4 1/2 | 0] [1/3 -1/4 0 | 0] [1/3 0 -1/2 | 0] [1 1 1 | 1]
Simplifying this matrix (from math 136), we can easily obtain the results for [math]\pi_0[/math], [math]\pi_1[/math], and [math]\pi_2[/math].
[math]\pi[/math] can be considered as an eigenvector of P with eigenvalue = 1.
But the vector u here needs to be a column vector. So we need to transform [math]\pi[/math] into a column vector.
[math]\pi[/math]T= PT[math]\pi[/math]T
Then [math]\pi[/math]T is an eigenvector of PT with eigenvalue = 1.
[math]\lim_{n\to \infty} P^n= \left[ {\begin{array}{ccc} \pi \\ \vdots \\ \pi \\ \end{array} } \right][/math]
If the Limiting Distribution [math]\pi[/math] exists, it must be equal to the Stationary Distribution. Of course, the Stationary Distribution is unique in this case.
In general, there are chains with Stationary distributions that don't converge, which means that they have Stationary Distributions but do not converge in distribution to any one of them, this is especially true for periodic chains. Convergence here means that the limit of [math] X_(t+1) |X_t = i [/math] for any i in the state space converges in distribution to the stationary distribution.
Let [math] P = U * \Sigma * U^{-1} [/math] be the eigenvalue decomposition of [math] P [/math], where [math]\Sigma = diag(\lambda_1,\ldots,\lambda_n) ; 1=|\lambda_1|; |\lambda_i| \gt |\lambda_j|, \forall i \lt j [/math]
Suppose [math] x^T = \sum a_i u_i [/math] where [math] a_i \in \mathcal{R} [/math] and [math] u_i [/math] are eigenvectors of [math] P [/math] for [math] i = 1\ldots n [/math]
>> P=[1/3, 1/3, 1/3; 1/4, 3/4, 0; 1/2, 0, 1/2]       % We input a matrix P.This is the same matrix as last class'.
the example of code and an example of Stationary Distribution, then all the pi probability in the matrix are the same.
>> P^100                                             % The Stationary Distribution is [0.3333 0.4444 0.2222]  since values remain unchanged.
>> a=-vec(:,1)      % The eigenvectors can be mutiplied by (-1) since probability can not be negative and λV=AV  can be written as λ(-V)=A(-V)
This example shows the distinction between having a Stationary Distribution and having a Limiting Distribution(convergence).Note: [math]\pi=(1/3,1/3,1/3)[/math] is the stationary distribution as [math]\pi=\pi*p[/math]. However, upon repeatedly multiplying P by itself (repeating the step [math]P^n[/math] as n goes to infinite) one will note that the results become a cycle (of period 3) of the same sequence of matrices. The chain has a Stationary Distribution but does not converge to it. Thus, there is no Limiting Distribution.
Limiting Distribution of the chain refers the transition matrix that reaches the stationary state. If the lim(n-> infinite)P^n -> c, where c is a constant, then, we say this Markov chain is convergent; otherwise, it's not convergent.
The above two examples are designed to solve for the stationary distribution of the matrix P. Meanwhile, they also give us the Limiting Distribution of the matrices as we have mentioned earlier that the Stationary Distribution is equivalent to the Limiting Distribution.
A Markov chain is called an ergodic chain if it is possible to go from every state to every state (not necessarily in one move). For instance, note that we can claim a Markov chain is ergodic if it is possible to somehow start at any state i and end at any state j in the matrix. We could have a chain with states 0, 1, 2, 3, 4 where it is not possible to go from state 0 to state 4 in just one step. However, it may be possible to go from 0 to 1, 1 to 2, then from 2 to 3, and finally from 3 to 4 .Therefore, we can claim that it is possible to go from 0 to 4 and this would satisfy a requirement of an ergodic chain. The example below will further explain this concept.
In this case, state a can go to state a, b, or c; state b can go to state a, b, or c; and state c can go to state a, b, or c. Henceit is possible to go from every state to every state. (Although state b cannot directly go into c in one move, it must go to a, and then to c.).
Recall that a Markov chain is irreducible if all the states communicate with each other.
The following chain is not an ergodic chain.
Note that this is true because it is not possible to get to every state from any state. So you cannot get to states C or D from states A or B, and vice versa.
The matrix looks like this:
Obviously, you cannot get from A or B to C or D.
Note1: Ergodic Markov Chain is irreducible, aperiodic and positive recurrent, meaning all states have to be positive recurrent.
Note2: positive recurrent if the expected amount of time between recurrences is finite.Or, E(Ti) < [math]infinite[/math].
Note3: If the limiting distribution exists for a markov chain does not always imply that the chain is ergodic.
Consider the markov chain of [math]\left[\begin{matrix}0 & 1 \\ 1 & 0\end{matrix}\right][/math], the Stationary Distribution( If the Markov chain is a time-homogeneous Markov chain, so that the process is described by a single, time-independent matrix , then the vector is called a stationary distribution (or invariant measure) if it satisfies)
is obtained by solving [math]\pi P = \pi[/math],
getting [math]\pi=[0.5, 0.5][/math], but from the assignment we know that it does not converge, ie. there is no limiting distribution, because the Markov chain is not aperiodic and cycle repeats [math]P^2=\left[\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right][/math] and [math]P^3=\left[\begin{matrix}0 & 1 \\ 1 & 0\end{matrix}\right][/math]
>> eye(3)                      %returns 3x3 identity matrix
>> L=(eye(3)-P)               %return the Laplace transform
Markov chain -an irreducible chain if it is possible to go from every state to every state (not necessary in one more).
An Ergodic Markov chain has a unique stationary distribution [math]\pi[/math]. The limiting distribution exists and it is equal to [math]\pi[/math].
Note to all students, the first half of today's lecture will cover the midterm's solution; however, please do not post the solution on the Wikicoursenote.
Let [math]\displaystyle P[/math] be the transition probability matrix of a Markov chain. [math] P_{ij}[/math] means the probability from in to j. If there exists a distribution vector [math]\displaystyle \underline{\pi} = [\pi_1 \pi_2 ... \pi_n][/math] such that [math]\pi_i \cdot P_{ij}=P_{ji} \cdot \pi_j, \; \forall i,j[/math], then the Markov chain is said to have detailed balance. The principle of detailed balance, formulated for kinetic systems, are decomposed into elementary processes (collisions, or steps, or elementary reactions): Each elementary process should be equilibrated by its reverse process at equilibrium, that is to say that detailed balance holds if and only if the Markov Chain is reversible.
A detailed balanced Markov chain must have [math]\displaystyle \underline{\pi}[/math] given above as a stationary distribution, that is [math]\displaystyle \underline{\pi} = \underline{\pi} P[/math], where [math]\displaystyle \underline{\pi}[/math] is a 1 by n matrix and [math]\displaystyle P[/math] is a n by n matrix.
[math]\; [\pi P]_j = \sum_i \pi_i P_{ij} =\sum_i P_{ji}\pi_j =\pi_j\sum_i P_{ji} =\pi_j  ,\forall j[/math]
Note: Since [math]\pi_j[/math] is a sum of column j and we can do this proof for every element in matrix P; in general, we can prove [math]\pi=\pi P[/math] . Hence [math]\pi[/math] is always a stationary distribution of [math]P(X_n+1=j|X_n=i)[/math], for every n.
Keep in mind that the detailed balance is a sufficient but not required condition for a distribution to be stationary. i.e. A distribution satisfying the detailed balance is stationary, but a stationary distribution does not necessarily satisfy the detailed balance.Also note that in the stationary distribution [math]\pi=\pi P[/math], in the proof the [math] \sum_i P_(ji) = 1 [/math] as we are summing across a row, so [math]\pi P=\pi[/math].
PageRank is a link-analysis algorithm developed by Larry Page and Sergey Brin at Stanford University in 1996. Two years later they founded Google, using PageRank as their basis for measuring a website's importance, relevance and popularity.
PageRank is a probability distribution used to represent the likelihood that a person randomly clicking on links will arrive at any particular page.
Many social media sites use this (such as Facebook and Twitter).
This is what made Google the search engine of choice over Yahoo, Bing, etc.- What made Google's search engine a huge success is not its search function, but rather the algorithm it used to rank the pages. (Eg. If we come up with 100 million search results, how do you list them by relevance and importance so the users can easily find what they are looking for. Most users will not go past the first 3 or so search pages to find what they are looking for. It is this ability to rank pages that allows Google to remain more popular than Yahoo, Bink, AskJeeves, etc.)
1. A web page is important if it has many other pages linked to it
3. If a webpage has many outgoing links then its links have less value (eg: if a page links to everyone, like 411, it is not as important as pages that have incoming links)
Page 3 is the most important since it has the most links pointing to it (3 links), therefore more weight should be placed on its outgoing links.
Page 4 comes after page 3 since it has the second most links (2) pointing to it
Page 2 comes after page 4 since it has the third most links (1) pointing to it
Cj = The number of outgoing links of page [math]j[/math]: [math]C_j=\sum_i L_{ij}[/math] suppose we have N pages, then p is a N by 1 vector contains rank of the pages (i.e. sum of entries in column j)
- [math]P_i[/math] counts the number of incoming links of page [math]i[/math]
[math]P_i=\sum_j L_{ij}[/math] For a row i, if there is a 1 in the third column, it means page three points to page i.
Alternate Example
File:pagerank.jpg
In this case, Page 5 does not have any pointers to or from the cluster of pages on its left. When we build the algorithm to conduct page rank in the next lecture, we will ensure that Page 5 is not ignored in the ranking system.
Obviously the rank is Page 3, Page 4, Page 2, Page 1, Page 5. Without an additional term ([math]d[/math]), poor old Page 5 would not come up on the search. However, we will make sure that it does. Yay!
A PageRank results from a mathematical algorithm based on the webgraph, created by all World Wide Web pages as nodes and hyperlinks as edges, taking into consideration authority hubs such as cnn.com or usa.gov. The rank value indicates the importance of a particular page. A hyperlink to a page counts as a vote of support. (This would be represented in our diagram as an arrow pointing towards the page. Hence in our example, Page 3 is the most important, since it has the most votes of support). The PageRank of a page is defined recursively and depends on the number and PageRank metric of all pages that link to it ("incoming links").
A page that is linked to by many pages with high PageRank receives a high rank itself. If there are no links to a web page, then there is no support for that page (In our example, this would be Page 1 and Page 5). (source:http://en.wikipedia.org/wiki/PageRank#Description)
Notice: Page and Brin confused a formula in above paper.
Page Rank checker - This is a free service to check Google™ page rank instantly via online PR checker or by adding a PageRank checking button to the
web pages (http://www.prchecker.info/check_page_rank.php)
[math]L_{ij}[/math] = 1 (if j has a link to i) & 0 (otherwise)
P is a Nx1 vector that contains the rank of all N pages.
For page i, the rank is [math]P_i[/math]
[math]L= \left[ {\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} } \right][/math]
then C = [2 1 1]
The rank of page i is
1) Proportional to the importance of each page that linked to it and
2) Inversely proportional to the total number of links coming from each of those pages.
If given all other Pj, we can easily calculate Pi. However, we don't know any of them, thus we need to solve N unknowns with the N equations that we have.
We do not want a page with rank 0 to occur (to give new websites an opportunity to be clicked), so we use d (damping factor)
The reason why we are multiplying by the d term in front of the [math]\sum_j \frac {L_{ij}P_j}{c_j}[/math] is to get rid of the problem with extreme cases where term one or two is dominant over the others.
1) Sum of Lij is the total number of incoming links.
[math]c_j[/math] is the number of outgoing links, the less outgoing links a page has, the more important the page is.
Then P = (1-d) e + dLD-1P
The relative value of page rank is valuable, but the absolute value is meaningless.
P is a vector of rank which could contain any arbitrary numbers. We only care about whether one web is more important than others(Pi[math]\gt =[/math] Pj for any j)
We assume that rank of all N pages sums to N. The sum of rank of all N pages can be any number, as long as the ranks have certain proportions.
[math]P=AP, where A=[(1-d)~\frac{ee^T}{N}+dLD^{-1}][/math]
P is the stationary distribution of A and it is a row vector
A is a transitional probability matrix (N[math]*[/math]N)
The following variables are necessary to calculate page rank:
[math]N[/math]: the number of pages
[math]L[/math]: an [math]N[/math] by [math]N[/math] matrix (Binary Matrix - every entry is 1 or 0)
[math]D^{-1}[/math]: an [math]N[/math] by [math]N[/math] diagonal matrix
[math]P[/math]: an [math]N[/math] by 1 row vector
[math]d[/math]: a constant between 0 and 1 (In the origional algorithm, d =0.8 )
Given that
[math]L= \left[ {\begin{matrix} L11 & L12 \\ L21 & L22 \end{matrix} } \right][/math]
[math]D^{-1}= \left[ {\begin{matrix} 1/C1 & 0 \\ 0 & 1/C2 \end{matrix} } \right][/math]
[math]P= \left[ {\begin{matrix} P1 \\ P2 \end{matrix} } \right][/math]
L D-1 P = [math] \left[ {\begin{matrix} L11/C1 & L12/C2\\ L21/C1 & L22/C2 \end{matrix} } \right] \left [ \begin{matrix} P1 \\ P2 \end{matrix} \right] [/math]=[math]\left [ \begin{matrix} L11*P1/C1+L12*P2/C2 \\ L21*P1/C1+L22*P2/C2 \end{matrix} \right] [/math]

Notice that all entries in AT are non-negative and each row sums to 1.
Hence AT satisfies the definition of a transition probability matrix.
We can consider AT to be the matrix describing all possible movements following links on the internet, and PT as the probability of being on any given webpage if we have been on the internet long enough.
Damping Factor "d" (http://en.wikipedia.org/wiki/PageRank)
The PageRank assumes that an imaginary user who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue is a damping factor, "d". It is generally assumed that "d" is set around a value of 0.85.
(1-d) is the likelihood of a web surfer jumping to a page chosen at random throughout the entire web.
A web page with no outbound links is known as a "sink" page. If a web surfer lands on a sink page, they are randomly transferred to another page and continue surfing. Thus, it is assumed that a page with no outbound links is linked to all other pages in the web.
Additionally, the higher the damping factor, the larger is the effect of an additional inbound link for the PageRank of the page that receives the link, and the more evenly distributes PageRank over the other pages of a site.
also page ranking system are used in data base management system vastly
[math]c= \left[ {\begin{matrix} 1 & 1 & 1 \end{matrix} } \right][/math]
[math]D= \left[ {\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} } \right][/math]
A=(1-d)*ones(N)/N+d*L*pinv(D)        #pinv: Moore-Penrose inverse (pseudoinverse) of symbolic matrix
We use the pinv(D) function [pseudo-inverse] instead of the inv(D) function because in the case of a non-invertible matrix,
it would not crash the program.
[vec val]=eigs(A)                    #eigen-decomposition
a=-vec(:,1)                          #find the eigenvector equals to 1
a=a/sum(a)                           #normalize a
Changing the value of d, does not change the ranking order of the pages.
c = [1 1 1] since there are 3 pages, each page is one way recurrent to each other and there is only one outgoing for each page.
Hence, D is a 3x3 standard diagonal matrix.
>> a=a/sum(a)  ;;standardize a
Page 2 is the most important page, because it has 2 incomings.
Page 3 is more important than page 1 because page 3 has the incoming result from page 2.
This example is similar to the first example, but here, page 3 can go back to page 2.
Hence, the matrix of the outgoing matrix, the third column of the D matrix is 2 in the third row. And we use the code to calculate the p=Ap.
In this example the second page has 2 incomings (from the first and third page). So, page 2 is the most important. Since the number of incoming for page 1 and 3 both come from page 2, they are equally important.
Consider: 1 <-> 2 -> 3
[math]L= \left[ {\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} } \right][/math] [math]c= \left[ {\begin{matrix} 1 & 2 & 0 \end{matrix} } \right][/math] [math]D= \left[ {\begin{matrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{matrix} } \right][/math]
1 <-> 2 -> 3 <-> 4
>> L= [0 1 0 0;1 0 0 0;0 1 0 1;0 0 1 0];
The ranking of each page is as follows: Page 3, Page 4, Page 2 and Page 1.
Page 3 has the highest ranking,since it has the most incoming links.
All of the other pages only have one incoming link, but Page 4 becomes the second highest ranked since Page 3 (highest ranked page) links to Page 4.
Page 2 is ranked next, because it links to Page 3. It has 2 outgoing links; page with the same number of incoming links can be ranked closest to the highest ranked page.
If the page with the highest ranking P1 has an incoming link to page P2, then P2 is ranked second, and so on.
For the matrix above:
page 4 has 3 incomings;
page 5 has 1 incomings from page 4;
page 2 has 1 incoming;
page 1 has 2 incoming;.
The rank is then: page 4 , page 5, page 2 and page 1 and page 3.
where c=[2 1 1 3 1].
Markov Chain Monte Carlo (MCMC) methods are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the desired distribution. The quality of the sample improves as a function of the number of steps. (http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo)
Idea: generate a Markov chain whose stationary dist is the same as target dist.
This is because [math]\pi[/math] is the proportion of time the process spends in state i, and [math]p{ij}[/math] is the probability the process transition out of state i into state j. Therefore, [math]\pi_i*p_{ij}[/math] is the proportion of time it takes for the process to enter state j. Therefore, [math]\pi_j[/math] is the sum of this probability over overall states i.
X can take m possible different values from [math]{1,2,3,\cdots,m}[/math]
- We want to generate [math]\{X_t: t=0, 1, \cdots, m\}[/math] according to [math]\pi[/math]
2. [math]r_{ji} = a(i,j) [/math] [math]\pi_i q_{ij} [/math] ≤ 1, then we get: [math]a(j,i)[/math] ≤ [math]1/(\pi_j q_{ji})[/math]
[math]P(Y=j) = q_{ij} [/math]. [math]\frac{\pi_j q_{ji}}{\pi_i q_{ij}}[/math] is a positive ratio.
go back to the first step
recall for the acceptance probability [math]r_{ij}[/math]
[math]r_{ij}=min(\frac {{\pi_j}q_{ji}}{{\pi_i}q_{ij}},1)[/math]
when [math]\frac {{\pi_j}q_{ji}}{{\pi_i}q_{ij}} \lt 1[/math], we have [math]r_{ij}=\frac {{\pi_j}q_{ji}}{{\pi_i}q_{ij}}[/math], and [math]r\lt sub\gt ji\lt /sub\gt =1 [/math]
when [math]\frac {{\pi_j}q_{ji}}{{\pi_i}q_{ij}} \geq 1[/math], we have [math]r_{ji}=\frac {{\pi_i}q_{ij}}{{\pi_j}q_{ji}}[/math], and [math] r\lt sub\gt ij\lt /sub\gt =1 [/math]
For the sake of simplicity using a discrete uniform distribution is the simplest.
3. [math] r_{ij} = \min \{\frac{\pi_j q_{ji}}{\pi_i q_{ij}}, 1\} = \min \{\frac{\pi_j 1/6}{\pi_i 1/6}, 1\} = \pi_j/\pi_i [/math]
Note: current state i is Xt, the candidate state j is Y.
Note: since qij = qji for all i and j, that is, the proposal distribution is symmetric, we have [math] r_{ij} = \min \{\frac{\pi_j}{\pi_i }, 1\} [/math]
hist(x,6)
In place of [math]\pi[/math] use [math]f(x)[/math] In place of [math]q\lt sub\gt i,j\lt /sub\gt [/math] use [math]q(y|x)[/math]
In place of [math]r\lt sub\gt i,j\lt /sub\gt [/math] use [math]r(x,y)[/math]
Definition: Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult. The purpose of the Metropolis-Hastings algorithm is to generate a collection of states according to a desired distribution [math]P(x)[/math]. [math]P(x)[/math] is chosen to be the stationary distribution of a Markov process, [math]\pi(x)[/math]. (http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm)
There are several differences between the discrete and continuous case of the Markov Chain:
We choose q(y|x) so that it is simple to sample from. Usually, we choose a normal distribution.
i.e. [math]q(y|x)=q(x|y)[/math] [math]q(y|x)=\frac{1}{\sqrt{2\pi}b}\,e^{- \frac{\scriptscriptstyle 1}{\scriptscriptstyle 2b^2} (y-x)^2}[/math] [math]q(x|y)=\frac{1}{\sqrt{2\pi}b}\,e^{- \frac{\scriptscriptstyle 1}{\scriptscriptstyle 2b^2} (x-y)^2}[/math] [math]\Rightarrow (y-x)^2=(x-y)^2[/math] so [math]~q(y \mid x)=q(x \mid y)[/math]
The value y is accepted if u<=[math]min\{\frac{f(y)}{f(x)},1\}[/math], so it is accepted with the probability [math]min\{\frac{f(y)}{f(x)},1\}[/math]. Thus, if [math]f(y)\gt f(x)[/math], then y is always accepted. The higher that value of the pdf is in the vicinity of a point [math]y_1[/math] , the more likely it is that a random variable will take on values around [math]y_1[/math]. As a result it makes sense that we would want a high probability of acceptance for points generated near [math]y_1[/math].
Note: if the proposal comes from a region with low density, we may or may not accept; however, we accept for sure if the proposal comes from a region with high density.
also notice that Metropolis Hastings is just a special case of Metropolis algorithm [math] \begin{align} f(x;\alpha,\beta)& = \frac{1}{\mathrm{B}(\alpha,\beta)}\, x^{\alpha-1}(1-x)^{\beta-1}\end{align} [/math]
xx=x(501:end)
Several extensions have been proposed in the literature to speed up the convergence and reduce the so called "burn-in" period.
1) Initialize the chain with xi and set i=0
2)Y~q(y|xi) where our proposal function would be uniform [0,1] since it matches our original ones support. =>Y~Unif[0,1]
4)Xi+1=Y with prob r(x,y), Xi+1=Xi, otherwise
5)i=i+1, go to 2
Xt= state of chain at step t
[math]Y[/math]~[math]q(y|x)[/math]
[math]\,r=min[\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,,1][/math]
[math]U[/math]~[math]Uniform(0,1)[/math]
xt+1 = y
xt+1 = xt
By the memoryless property of Markov Chain, the current state will only be affected by the previous state. Thus, time t will not affect the choice of state.
In this example, q(y|x)=N(x, b^2)
Demonstrated as follows, the choice of b will be significant in determining the quality of the Metropolis algorithm. This parameter affects the probability of accepting the candidate states, and the algorithm will not perform well if the probability is too large or too small.
hist(x(5000:end,100)
plot(x(5000:end)
Then we are setting up our proposal distribution [math]q(y\mid{x})[/math] to be much narrower than the target [math]\displaystyle f(x)[/math] so the chain will not have a chance to explore the sample state space and visit a lot of the states of the target [math]\displaystyle f(x)[/math]. For example, if we are generating samples from the combination of two normal distributions, it is highly likely the histogram of [math]\displaystyle X[/math] will only be able to show the distribution of one of the normal distributions.
with b =0.02, the chain takes small steps so the chain doesn't explore enough of the sample space. Thus, we want b large enough so that it explores both distributions, but small enough so that it is still efficient
As CLT said, when b is very large the graph looks like a normal distribution(b=20). However, when b is very small it looks like a fluctuate graph. (b= 0.2)
b too large
Then the fraction [math]\frac{f(y)}{f(x)}[/math] would be very small [math]\Rightarrow[/math] [math]r=min{\{\frac{f(y)}{f(x)},1}\}[/math] is very small as well. It is highly unlike that [math]\displaystyle u\lt r[/math], the probability of rejecting [math]\displaystyle Y[/math] is high so the chain is likely to get stuck in the same state for a long time [math]\rightarrow[/math] chain may not coverge to the right distribution.It is easy to observe by looking at the histogram of [math]\displaystyle X[/math], the shape will not resemble the shape of the target [math]\displaystyle f(x)[/math] Most likely we reject y and the chain will get stuck.
with b = 20, jumps are very unlikely to be accepted
if b is too large then the normal distribution can not cover the fluctuate graph, so it is hard to accept.
b just right
Well chosen b will help avoid the issues mentioned above and we can say that the chain is "mixing well".
chose a right b (mixing well), is more likely to accept the chain.
with b = 2, the chain is mixing well.
[math] \frac{f(y)}{f(x)}[/math] and consequently r is very small and very unlikely that u < r, so the current value will be repeated.
ie. y is rejected as [math]\frac{f(y)}{f(x)}[/math] and xt+1 = xt; as a result, we get a lot of the same points from the output.
also we want to notice that if we choose b to be too small we could never reach where we want to go in a multi distribution graph
Recall detailed balance for discrete case if [math]\pi_i*P_ij=\pi_j*Pji[/math] then [math]\pi=\pi*P[/math]
Recall: Each row of P must add up to 1
Continuous case: If [math]\displaystyle f(x)P(y|x)=f(y)P(x|y)[/math], then [math]\displaystyle f(x)[/math] is a stationary distribution.
Because [math]\int^{}_y f(y)P(x|y)dy=\int^{}_y f(x)P(y|x)dy=f(x) \cancel{\int^{}_y P(y|x)dy}=f(x)*1 = f(x)[/math]
Convergence of MH
We generate y from q(y|x) and accept with probability
without loss of generality, assume [math]\,\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,\lt 1[/math]
then r(x,y) i.e. probability of accepting y given that the current state is x will be
[math]\,r(x,y)=min[\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,,1]=\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,[/math]
Now suppose that the current state is y and we are generating x. The probability of accepting x, given that the current state is y is [math]\,r(y,x)=min[\frac{f(x)}{f(y)}\,\frac{q(y|x)}{q(x|y)}\,,1]=1[/math]
Based on our original assumption [math]\frac{f(y)}{f(x)}[/math][math]\frac{q(x|y)}{q(y|x)}\gt 1[/math] , then r(y,x)=1
In Metropolis-Hastings, the probability of jumping to y, given that the current state is x (denoted by P[y|x]) depends on (1) the probability of generating y, and (2) the probability of accepting y.
[math]\,P(y|x)=q(y|x)×r(x,y)=\frac{q(y|x)f(y|x)}{f(x|y)}\,\frac{q(x|y)}{q(y|x)}\,=\frac{f(y|x)q(x|y)}{f(x|y)}\,[/math]
The probability of jumping to x, given that the current state is y.
[math]\,P(x|y)=q(x|y)×r(y,x)=q(x|y)[/math]
Detailed balance for the chain requires [math]\,f(x)P(y|x)=f(y)P(x|y)[/math].
L.H.S
[math]f(x)\frac{f(y)q(x|y)}{f(x)}\,=f(y)q(x|y)[/math]
R.H.S
[math]\,f(y)P(x|y)=f(y)q(x|y)[/math]
L.H.S = R.H.S
Thus, detailed balance holds. Therefore f(x) is the stationary distribution of the chain generated by Metropolis-Hastings.
If [math]\,\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,\gt 1[/math]
[math]\,r(x,y)=min[\frac{f(y)}{f(x)}\,\frac{q(x|y)}{q(y|x)}\,,1]=1[/math]
[math]\,r(y,x)=min[\frac{f(x)}{f(y)}\,\frac{q(y|x)}{q(x|y)}\,,1]=\frac{f(x)}{f(y)}\,\frac{q(y|x)}{q(x|y)}\,[/math]
[math]\,P(y|x)=q(y|x)×r(x,y)=q(y|x)[/math]
[math]\,P(x|y)=q(x|y)×r(y,x)=\frac{f(x)q(y|x)}{f(y)}\,[/math]
LHS=RHSusing the same rationale as the previous case
Suppose we have two normal distribution [math]N(2, \sigma^2)[/math] and [math]N(10, \sigma^2)[/math], and we want
[math] f(x) = \begin{cases} N(2, \sigma^2), & \text{if } j = 0 \\ N(10, \sigma^2), & \text{if } j = 1 \end{cases}[/math]
where P(j = 0) = 0.5 and P(j = 1) = 0.5
Mixture of Gaussians
We want to sample [math]f(x)=0.5*exp-\frac{(x-\mu1)^2}{\sigma1^2} = 0.5*exp-\frac{(x-\mu2)^2}{\sigma2^2}[/math]
We can use MH where, [math]\,r(x,y)=min[\frac{e^{-(y-2)^2}+e^{-(y-10)^2}}{e^{-(x-2)^2}+e^{-(x-10)^2}}\,,1][/math] using the normal distribution of to show the r(x,y).
b=2;%b=20, b=200
for i=2:100000
r=min((exp(-(y-2)^2)+exp(-(y-10)^2))/(exp(-(x(i-1)-2)^2)+exp(-(x(i-1)-10)^2),1);
hist(x(5000:end), 100)
As it clear from this plot that the matlab code above generated (simulated) mixture of Gaussian, one around mean of 2 and other around mean of 10.
However, keep in mind that inappropriate b (either too small or too large) may not simulate it properly
For b = 0.02 (too small)
For b = 200 (too large)
These both does not seem like the gaussian distribution centered around mean 2 and 10. Either b is too large or too small, the graph would not look like the original graph.
In general, the mixture of Normal distributions can have any mixture of weights as long as they are between 0 and 1, and the sum of the weights equals 1. For the mixture of Normal distributions, it is important to be careful with the selection of b.
1) If b is too small, it will easily get stuck in one of the two parts of the Normal distribution, as it can't choose a number in the other half as a candidate
2) If b is too large, it will get stuck on a single number for larger periods of time, as we saw before.
To simulate a multivariate distribution, we can use the above algorithm and modify the code so that the scalars x and y are vectors.
ezplot
>>ezplot(x^2)
>>ezsurf('exp(-(x1^2*x2^2+x1^2+x2^2-8*x1-8*x2)/2)')
Matlab Tips:
Function "ezplot" is used to "easily" plot a curve [math]\displaystyle y=f(x)[/math]. By default the domain is set to [math]-2 \pi\leq x \leq 2\pi[/math]
Resource:http://www.mathworks.com/help/matlab/ref/ezplot.html
Function "ezsurf" is used to "easily" plot a surface [math]\displaystyle z=f(x,y)[/math]. By default the domain is set to [math]-2\pi\leq x\leq 2\pi, -2\pi\leq y\leq 2\pi[/math]
Resource:http://www.mathworks.com/help/matlab/ref/ezsurf.html
Function "syms" is a shortcut used to create symbolic variables.
Resource:http://www.mathworks.com/help/symbolic/syms.html
we are interested in the probability of moving to y from x in the Markov Chain generated by MH algorithm denoted by p(y|x) p(y|x) depends on two probabilities. 1) probabilities of generating y 2)probabilities of accepting y
Mixture distribution of two random variables:
In general if X is a mixture distribution of random variables Y and Z, then
1) f(x) = p*fy(x) + (1-p)*fz(x)
3) S(x) = 1-F(x) = p*Sy(x) + (1-p)*Sz(x)
4) E(Xk) = p*E(Yk) + (1-p)*E(Zk)
this lecture has many main points. please remember all of them ! please notice the highlights sentence
Simulated Annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). This notion of slow cooling is implemented in the Simulated Annealing algorithm as a slow decrease in the probability of accepting worse solutions as it explores the solution space. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the optimal solution.
Bold text is very important here!!!!!!!
The method was independently described by Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi in 1983 and by Vlado Černý in 1985. http://en.wikipedia.org/wiki/Simulated_annealing
In short, Simulated Annealing is a popular algorithm in simulating for optimization. This Simulated Annealing is an application of the Metropolis algorithm. This algorithm aims to find a global minimum or a global maximum.
[math]e^{-\frac{h(x)}{T}}[/math]
Note that exponential function is monotonic - meaning that it is only ever increasing/decreasing.
For a given (arbitrary) constant T>0, min h(x) is equivalent to max [math]e^{-\frac{h(x)}{T}}[/math]
We want to find min h(x).
T is an arbitrary positive number. A small T will narrow the function and large T will widen the function.
Note that choosing the value of T will not affect the points of the min/max.
Why? [math] e^{-x} [/math] is a decreasing function of x. Therefore the minimum value of this function occurs at the largest value of x.
f ∝ e-h(x)/T
Note that exponential function is monotonic. If T is small, then sampling from f is in fact a sample of points close to the mode of [math]e^{\frac{-h(x)}{T}}[/math] which are the min of h(x). Based on this intuition, simulated annealing has the process:
1. Set T to a large number
2. Initialize the chain. Set [math]X_t[/math]
3. [math]y[/math] ~ [math]q(y|x)[/math] (q should be symmetric)
4. [math]r = min{\frac{f(y)}{f(x)}}[/math]
5. [math]U[/math]~[math] U(0,1)[/math]
6. If U < r: [math]x_{t+1}=y[/math]
else: [math]x_{t+1}=x_t[/math]
7. Decrease T. Go back to 3.
[math] r = \min ( \frac{f(y)}{f(x)} ,1 )[/math]
[math] = \min (\frac{e^{\frac{-h(y)}{T}}}{e^\frac{-h(x)}{T}} ,1)[/math]
[math] = \min (e^{\frac{-h(y)}{T}-\frac{-h(x)}{T}} ,1)[/math]
[math] = \min (e^{\frac{h(x)-h(y)}{T}},1)[/math]
[math]r=min\left[\frac{f(y)}{f(x)},1\right]=min\left[\frac{e^{\frac{-h(y)}{T}}}{e^{\frac{-h(x)}{T}}},1\right]=min\left[e^{\frac{h(x)-h(y)}{T}},1\right][/math]
Suppose T is large,
1. If [math]h(y)\lt h(x)[/math], then [math]e^{\frac {h(x)-h(y)}{T}}[/math]>1. Therefore r=1 and we will always accept y (a good move)
2. If [math]h(y)\gt h(x)[/math], then [math]e^{\frac {h(x)-h(y)}{T}}[/math]<1. Therefore r<1 and we will accept with probability r (this will help to escape from local minima).
Suppose T is small (T->0)
1. If [math]h(y)\lt h(x)[/math], then e(h(y)-h(x))/T->infinity. Therefore r=1, we always accept y. Since h(y) takes on a lower value, moving towards h(y) is considered a good move and we always accept such a good move.
2. If [math]h(y)\gt h(x)[/math], then e(h(y)-h(x))/T->0. Therefore r->0, we almost never accept y.
3. if r is equal to 1 or close to 1, then we accept the move. If r close to 0, then that means the probability of the move is close to 0, so we almost reject. Essentially, the smaller the value of T, the sharper the distribution, and the higher the probability of rejection. We start by picking T large so that there is a lower probability of rejection which is more efficient. The algorithm will then be able to explore the target distribution instead of rejecting all proposed points and just repeating the previous state. Note though that the convergence of this algorithm to an accurate estimate of the global minimum is not guaranteed. We can never be sure if we have escaped the local minimums, if it is a complex example and there are a lot of them. However, with a large enough T, and reasonable choice of 'b' in the proposal density the algorithm should work for most functions.
Also, the main reason to choose T to be large enough at first is mainly because we have no idea what the possibilities of xt can be.With that in mind,if we initialize a value of x which is away from the mean too much,we may never have the chance to ever get any closer to meanbecause the probability to move towards the wrong direction will be way too high due to the mechanism of the algorithm.
min([math]\frac {e^{-\frac {h(y)}{T}}}{e^{-\frac {h(x)}{T}}}[/math],1)=min([math]e^{\frac {h(x)-h(y)}{T}}[/math],1)
Note: The variable T is known in practice as the "Temperature", thus the higher T is, the more variability there is in terms of the expansion and contraction of materials. The term "Annealing" follows from here, as annealing is the process of heating materials and allowing them to cool slowly - in our case, starting the algorithm with a high T, and then lowering it.
6) [math]U\lt r =\gt X_{t}+1=y, else, X_{t}+1=x_{t}[/math]
Ezplot((x-3)^2)
Ezplot((x-3)^2,[-6,12])
Ezplot(exp(-((x-3)^2)), [-6, 12])
x(1)=rand;
y=b*rand+x(ii);
when T is large it is helpful for generate the function.
example for H(x)=(x-3)^2
Another Example: [math]h(x)=((x-2)^2-4)((x-4)^2-8)[/math]
The Travelling Salesman Problem asks: given n numbers of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
The idea of using Simulated Annealing algorithm is: let Y (let Y be all possible combinations of route in terms of cities index) be generated by permutation of all cities. Let the target or objective distribution (f(x)) be the distance of the route given Y. Then use the Simulated Annealing algorithm to find the minimum value of f(x).


text:
10:44 pm EST, January 26, 2016
'Marvel's Most Wanted' recruits Delroy Lindo for 'S.H.I.E.L.D.' spinoff
By Michal Schick | 10:44 pm EST, January 26, 2016
Delroy Lindo joins Agents of S.H.I.E.L.D. spinoff Marvel's Most Wanted as an established figure in comic book history.
Lindo will play Dominic Fortune, a character who debuted in the 1970s and was originally established as an adventurer from the early 20th century. Tellingly, Fortune played in 2010's Hawkeye & Mockingbird comic, and also appears in an issue of last year's run of comics inspired by Agents of S.H.I.E.L.D.
The role of Dominic Fortune is the first new face to be cast in Most Wanted, which will star Adrianne Palicki and Nick Blood as Bobbi Morse and Lance Hunter. It remains to be seen whether or not Delroy Lindo's role will be that of a villain or ally, but Jeph Loeb's comments on the casting suggest that it might be complicated.
"Dominic Fortune carries with him a cunning and charm but also a dangerous edge that only Delroy could bring to life," Loeb says. "We're thrilled to have him join the show."
Related: Agents of S.H.I.E.L.D. showrunners "very excited" for Marvel's Most Wanted
Recognized for his work on stage and screen, Delroy Lindo has appeared in many films, including Cymbeline and The Cider House Rules. He has recently been seen on television in ABC's Blood and Oil, and NBC's Believe.
Marvel's Most Wanted is helmed by Agents of S.H.I.E.L.D. writers and producers Jeff Bell and Paul Zbyszewski. ABC President Paul Lee recently commented that the pilot episode will be filmed in the upcoming months, and that he has high hopes for the spinoff series.
"We love the script," he says. "We think it's going to be great."
Source: Marvel


By design, a two-stroke diesel is power-dense, with a power stroke every revolution, and inherently cleaner than a gasoline two-stroke. A major drawback is a narrow powerband. And "clean" is... Two-cycle engines are often used to power small machines such as lawn mowers and string trimmers. Keeping a two-cycle engine running smoothly and efficiently requires regular maintenance, a proper fuel mixture and a carburetor that is adjusted correctly.
Cleaning 2 stroke fuel tanks My dilemma: I have a translucent plastic fuel tank for a 2stroke engine that has been standing with mixed fuel in it for some time.... We found the Tecumseh engine information on a label (Photo 2). But other brands may stamp the numbers into the engine block, valve cover or engine shield. But other brands may stamp the numbers into the engine block, valve cover or engine shield.
3/04/2013 · The extreme thermal cycle is a stress releiving process and can actually be good for the pipe. Just don't quench it with water while it's hot - that can harden the metal and promote fracturing even though low carbon steel (1018, 1020) can't really be hardened but so much. how to clean cat pee from hardwood floor Sustainable Energy The Two-Stroke Engine, Reconsidered Once thought too polluting, the two-stroke engine makes a comeback in advance of stricter fuel efficiency standards.
Therefore, your unlikely to see a significant change in engine performance or noise with the use of 2-stroke in diesel. When and how to use the 2 Stroke in Diesel: However, if you have a 2005-2012 Denso Common Rail equipped system, your vehicle will most likely notice significant changes.
3/04/2013 · The extreme thermal cycle is a stress releiving process and can actually be good for the pipe. Just don't quench it with water while it's hot - that can harden the metal and promote fracturing even though low carbon steel (1018, 1020) can't really be hardened but so much.