From Las Vegas to Monte Carlo with Markov’s Inequality

One of the basic results in probability theory tells us that it is unlikely a random event deviates from its expected value with high probability.
Theorem 1. (Markov’s Inequality)
For any non-negative real valued random variable X, we have
{\text Pr}[X \ge \alpha] \le \frac{\mathbb{E}[X]}{\alpha}.

Proof.
Note that
\mathbb{E}[X] = \sum_{x \ge 0} x \cdotp p_X(x)
= \underbrace{\sum_{x<\alpha} x \cdotp p_X(x)}_{\ge 0} + \sum_{x \ge \alpha} x \cdotp p_X(x)
\ge \sum_{x \ge \alpha} \alpha \cdotp p_X(x)
\ge \alpha \cdotp \text{Pr}[X \ge \alpha],
as desired. \Box

There is an interesting application of this inequality in theoretical computer science. Knowing this probability bound, it allows us to control a probabilistic algorithm derived from another probabilistic algorithm.

There are at least two classes of probabilistic algorithms that are interesting when we look at in which aspect it is random:

  • a class of algorithms whose output is always correct, but its running time is random (can take very long time),
  • a class of algorithms whose running time is deterministic (for example, is a deterministic function in the length of input), but its answer is sometimes wrong.

The first class is usually called Las Vegas algorithm and the second class is usually called Monte Carlo algorithm. How are these two algorithms related?

It appears that if we can solve a problem using Las Vegas algorithm, we can also solve it using a Monte Carlo algorithm with reasonably small error probability. Let me argue why this is a useful fact. For many practical purposes, we want to have a decision right after certain amount of time; it is okay to make mistakes sometimes (as we may be able to handle it later).

To obtain a Monte Carlo algorithm, we can just simulate the Las Vegas algorithm with little modifications. Our modifications aim at fulfilling two requirements: it runs in a “fixed” time and it outputs an answer in a reasonably good probability. To fulfill the first requirement, we can just fix a threshold for the number of computational steps the Las Vegas algorithm takes, say t(x) steps for an input of size x. If after t(x) steps, our Las Vegas algorithm outputs an answer, we can just output the same answer in our Monte Carlo algorithm. This will always be a correct answer by the nature of Las Vegas algorithm. If not, we just output a made-up answer (depending on our need).

But, how should we choose t(x)? We have freedom here to choose the function t(x), but we may want to use this to fulfill the second requirement: to get a correct answer with good probability. Note that we can analyze our Las Vegas algorithm to obtain its expected running time on input x, say p(x). We know that our Monte Carlo algorithm will output a correct answer at least when the simulation finishes in t(x) steps. If X is the running time of the simulation of our Las Vegas algorithm, then the probability of having a correct answer is at least
\text{Pr}[X < t(x)] = 1- \text{Pr} [ X \ge t(x) ]
\ge 1 - \frac{ \mathbb{E}[X] }{t(x)}
= 1- \frac{p(x)}{3p(x)}
= \frac23,
which is good, if we pick t(x)=3p(x). Obviously, we can also pick larger t(x) to gain better probability. But, as long as we pick t(x)>2p(x), we can also amplify this probability by doing multiple simulations and process a final answer (in case of Boolean answer, for example, we do majority voting).

Note that we have described an abstraction of how to transform any Las Vegas algorithm to a Monte Carlo algorithm. This can be very useful if instead of getting an always-correct-answer, we know when we will get an answer and maybe do a post-processing to the answer afterwards.

Now, our curious mind would ask: Can we obtain a Las Vegas algorithm from a Monte Carlo algorithm? If yes, how? If not, why is it not allowed by nature? Are the collection of problems that can be solved using Las Vegas algorithms and the collection of problems that can be solved using Monte Carlo algorithms the same? If we talk about polytime algorithm, a mathematical-minded reader may want to read more about complexity class {\bf ZPP}, {\bf BPP}, and possibly other probabilistic complexity classes.

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

OSN 2017 Matematika Hari Kedua (Soal dan Solusi)

Solusi saya bisa diunduh di sini: osn2017h2.pdf.

Posted in Uncategorized | Leave a comment

OSN 2017 Matematika Hari Pertama (Soal dan Solusi)

Silakan unduh soal dan solusinya di sini: osn2017h1.pdf.

 

Posted in Matematika, Uncategorized | Tagged , , , , , , , | Leave a comment

Salah mendefinisikan himpunan

Beberapa hari yang lalu saya (akhirnya pernah) mengerjakan soal matematika dengan mendefinisikan kelas/koleksi yang saya pikir merupakan himpunan, namun ternyata bukan. (Ini seakan-akan sebuah pencapaian tersendiri sebagai orang yang belajar logika hahaha). Awalnya saya bingung asisten dosennya menulis komentar bahwa yang saya definisikan itu bukan himpunan, kemudian saya berpikir mengapa itu bukan himpunan. Setelah berdiskusi dengan teman saya, Anna dan Marvin, saat makan siang, baru benar-benar yakin kalau yang saya definisikan bukan himpunan.

Salah satu intuisi paling mudah sesuatu itu bukan himpunan adalah bahwa ia merupakan koleksi yang “terlalu besar” untuk menjadi sebuah himpunan. Misalnya koleksi semua himpunan bukanlah sebuah himpunan. Koleksi semua kardinal atau ordinal juga bukan sebuah himpunan.

Nah, soal yang saya kerjakan ini adalah soal PR Teori Model. Saya membuktikan bahwa jika ada suatu model B  terhadap teori T sehingga teori tentang B tidak konsisten dengan A, maka ada suatu formula \varphi_B di teori tentang B yang tidak konsisten juga dengan A. Kemudian, yang saya lakukan adalah mengambil semua formula \varphi_B dari setiap model B dari T, d.k.l.

S=\{\varphi_B: B \vDash T\}.

Dari konstruksi S ini, S bukanlah sebuah himpunan jika T punya model dengan kardinalitas tak hingga. Mengapa? Karena menurut Teorema Skolem-Loewenheim versi upward maupun downward, jika T memiliki suatu model tak hingga, maka untuk sembarang kardinal tak hingga \kappa, maka T akan memiliki model dengan kardinalitas \kappa. Ini berarti, S memuat model dengan hampir semua kardinal. Ini mengindikasikan konstruksi S ini bukan merupakan himpunan.

Terus kenapa kalau S bukan himpunan? Ya, intinya kita belum tentu boleh mengaplikasikan operasi-operasi yang valid untuk himpunan kepada S, seperti tidak bisa mengambil subhimpunan dari S dengan properti tertentu. It is black magic!

 

Posted in Uncategorized | Leave a comment

Karya tahun 2008 (omg)

Tahun 2008 mungkin dikenal dengan masa-masa kealayan. Orang-orang baru mulai mengenal Facebook (dan meninggalkan Friendster).

Bagi saya, tahun 2008 (dan mungkin 2007) adalah masa di mana (selain juga mejadi alay), saya juga mulai menekuni bidang matematika! Saya agak freak waktu itu karena belajar matematika sampai larut malam hampir setiap hari. Well, rumah saya agak jauh ya dari pusat ibu kota Pekanbaru jadi jalan-jalan juga malas dan jarang 😛

Saya ingat dulu suka bikin kompilasi soal-soal olimpiade. Nah, ternyata masih beredar di internet! Berikut adalah tautannya:

https://matematikaict.files.wordpress.com/2009/05/soal-latihan-olimpiade-matematika-100-soal.pdf

OMG. Nostalgia abis!

Meskipun hal ini merupakan hal yang bisa ditertawakan, menurut saya menerjemahkan soal-soal olimpiade dari bahasa asing ke bahasa Indonesia saja sudah sangat berguna. Saya ingat beberapa orang sempat menyapa saya karena mereka menggunakan kompilasi soal-soal di atas untuk latihan. Saya yang sombong sudah lupa dan terus memasang muka terkejut “Oh yaa?” Sekarang sih jadi ingat lagi.

(Padahal sekarang sedang mengerjakan laporan proyek yang deadlinenya 3 jam lagi. Post ini hanya pelarian saja… ckck).

Oh ya, kalau diperhatikan ada hal yang lucu. Nama saya di berkas kompilasi tersebut bukan Raja Oktovin P. D. tetapi Raja Octovin P. D yang menurut saya lucu. Pertama, saya dulu memang suka memaksakan nama saya Octovin, pake c. Karena menurut saya lebih English. LOL. Tapi akhirnya saya menerima kenyataan setelah memastikan di akte kelahiran saya, kalau nama saya pakai huruf k. (Beneran saya periksa dulu). Kemudian, saya merasa agak bodoh tidak menaruh titik di belakang huruf D.

Oke, sudah cukup procrastinating-nya. Melihat pekerjaan saya yang tak seberapa ini membuat saya ingin memproduksi lebih banyak karya lagi. Gak tau apakah akan dipakai orang atau tidak. Saya ga peduli. 🙂

Posted in Uncategorized | 1 Comment

Yes, Douwe Bob, just yes

I am in love.

 

Thanks again for Eurovision for letting person from far-away country to know more singers like Mr. Douwe Bob. Since now I am living in Amsterdam, it’ll be easier for me to meet my idol. See you soon, Douwe Bob.

Posted in Uncategorized | Leave a comment

Transitive filtration on (Q,<)

This a bonus question for HW 2 Basic Modal Logic course 2016/2017.

Show that transitive fitration on (\mathbb{Q},<) is a finite list of clusters, maybe interspersed by some irreflexive singletons, no two of which may be adjacent.

What I did is to consider it in four steps.

Finiteness and transitivity

This follows from filtration property (upon finite \Sigma) and the property that R has as a transitive filtration.

Linearity

For all a \ne b, we have Rab \vee Rba.

Proof. WLOG, a<b. Then, we show that for all \diamond \phi \in \Sigma, we have that if b \Vdash \phi \vee \diamond \phi, then a \Vdash \diamond \phi. If b \Vdash \phi, then because a<b, we have a \Vdash \diamond \phi. If b \Vdash \diamond \phi, then there exists some c>b, such that c \Vdash \phi, and thus becaue a<b<c, a \Vdash \diamond \phi\blacksquare

Moreover, we basically have < \subseteq R.

Properties of irreflexive points

If \neg Raa, then there must be some \diamond \phi \in \Sigma, such that a is the greatest number satisfying \phi.

Proof. If \neg Raa, it means that for some \diamond \phi \in \Sigma, we have a \Vdash \phi \vee \diamond \phi but a \nVdash \diamond \phi. Thus, a \Vdash \phi and a \nVdash \diamond \phi. \blacksquare

I also claim no two irreflexive points can be adjacent.

Proof. Suppose that a<b are irreflexive points w.r.t. formula \alpha and \beta, respectively and suppose that they are adjacent in the finite list of filtration. Take any number c \in (a,b) \cap \mathbb{Q}. Clearly, Rac. But a and b are adjacent in the filtration, then we must have Rbc for all such c. This means that for all \diamond \phi \in \Sigma, particularly \diamond \beta, we have c \vDash \beta \vee \diamond \beta implies b \vDash \diamond \beta. But, we have b \nvDash \diamond \beta. \blacksquare

Properties of non-simple cluster

Now, we prove that for any reflexive point, it belongs to a non-simple cluster.

Proof. If there is no \diamond \phi \in \Sigma, then all the points belong to the same cluster. If there exist \diamond \phi, then for reflexive points a, Raa means for all \diamond \phi \in \Sigma, a \vDash \phi \vee \diamond \phi implies a \vDash \Diamond \phi. This means, a must not be the greatest number satisfying formula \phi for any \diamond \phi \in \Sigma. Because there is only finite number of singletons (due to the finiteness of \Sigma, we can choose rational number a_1 >a such that all the numbers in (a,a_1) \cap \mathbb{Q} are all reflexive (not a singleton). Now pick any x \in (a,a_1) \cap \mathbb{Q}. Clearly Rax. We show Rxa now. Because it means for all \diamond \phi \in \Sigma, a \vDash \diamond \phi implies x \vDash \diamond \phi, and because a is not a singleton, we then just need to check a \vDash \diamond \phi implies x \vDash \diamond \phi. Suppose a \vDash \diamond \phi but x \nvDash \diamond \phi. This means that there’s a singleton for \phi \in (a,x) which is a contradiction. Thus a belongs to a cluster which also contains at least the whole (a,a_1) \cap \mathbb{Q}.


Because every point in filtration is either reflexive or irreflexive, these properties show that the result of filtration is a finite list of clusters, may be interspersed by some irreflexive singletons, no two of which are adjacent.


This is approximately what I wrote in my homework. I have not got any feedback yet at the time I am writing this. I hope it got almost full marks (like 8 or more).

Posted in Uncategorized | Tagged , , , , , , , , , , | Leave a comment