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 , we have

Proof.
Note that




as desired.

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 steps for an input of size . If after 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 ? We have freedom here to choose the function , 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 , say . We know that our Monte Carlo algorithm will output a correct answer at least when the simulation finishes in steps. If is the running time of the simulation of our Las Vegas algorithm, then the probability of having a correct answer is at least




which is good, if we pick . Obviously, we can also pick larger to gain better probability. But, as long as we pick , 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 , , and possibly other probabilistic complexity classes.

OSN 2017 Matematika Hari Kedua (Soal dan Solusi)

Solusi saya bisa diunduh di sini: osn2017h2.pdf.

OSN 2017 Matematika Hari Pertama (Soal dan Solusi)

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

 

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  terhadap teori sehingga teori tentang tidak konsisten dengan , maka ada suatu formula di teori tentang yang tidak konsisten juga dengan . Kemudian, yang saya lakukan adalah mengambil semua formula dari setiap model dari , d.k.l.

.

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

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

 

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. 🙂

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.

Transitive filtration on (Q,<)

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

Show that transitive fitration on 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 ) and the property that has as a transitive filtration.

Linearity

For all , we have .

Proof. WLOG, . Then, we show that for all , we have that if , then . If , then because , we have . If , then there exists some , such that , and thus becaue , . 

Moreover, we basically have .

Properties of irreflexive points

If , then there must be some , such that is the greatest number satisfying .

Proof. If , it means that for some , we have but . Thus, and .

I also claim no two irreflexive points can be adjacent.

Proof. Suppose that are irreflexive points w.r.t. formula and , respectively and suppose that they are adjacent in the finite list of filtration. Take any number . Clearly, . But and are adjacent in the filtration, then we must have for all such . This means that for all , particularly , we have implies . But, we have .

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 , then all the points belong to the same cluster. If there exist , then for reflexive points , means for all , implies . This means, must not be the greatest number satisfying formula for any . Because there is only finite number of singletons (due to the finiteness of , we can choose rational number such that all the numbers in are all reflexive (not a singleton). Now pick any . Clearly . We show now. Because it means for all , implies , and because is not a singleton, we then just need to check implies . Suppose but . This means that there’s a singleton for which is a contradiction. Thus belongs to a cluster which also contains at least the whole .

---

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).