- math
- 패스트캠퍼스 #포트폴리오 #직장인자기계발 #환급챌린지 #포트폴리오챌린지 #패스트캠퍼스후기 #초격차패키지 #오공완
- probability
- probability theory
- maths
- SUAPC
- Discrete
- cs-theory
- laplace
- argmax
- Dim
- #패스트캠퍼스 #패캠챌린지 #수강료0원챌린지 #패캠챌린지 #직장인인강 #직장인자기계발 #패캠인강후기 #패스트캠퍼스후기 #환급챌린지 #본인이선택한강의명
- Computer science
- CP
- randn
- dims
- Counting
- pytorch
- Axis
- sinchon icpc
Piico의 일상
The Probabilistic Method: An Introduction 본문
The Probabilistic Method: An Introduction
Piico 2025. 3. 19. 11:19The motivation of the probabilistic method is to show the existence of an object. The basic idea is to show that there is greater than zero probability for that object in a probability space S. There are various methods such as the argument with expectation and derandomization. We will talk about them in future sections.

In this post we explore how to make a basic argument about the existence of an object (using the concept that showing positive probability implies existence). The object we are about to existence of is the k-clique that has no monochromatic edge-coloring (i.e. its edges are not all of a single color). Recall that a complete graph Kn is a graph where all its vertices are connected to every other vertex.

Theorem 1: If \binom{n}{k}2^{-\binom{k}{2}+1}<1 then it is possible to two-color the edges of a complete graph K_n such that its subgraph K_k's edges have no monochromatic coloring.
Don't worry about this term \binom{n}{k}2^{-\binom{k}{2}+1}<1 for now, it will make sense very soon. First, let's begin with a quick warm-up:
- How many edges does K_n have?
See answers
\binom{n}{2} = \frac{n(n-1)}{2}
Here are some questions to think about to work toward the proof:
- How many possible colorings are there for the \binom{n}{2} edges?
- How many subgraphs K_k of K_n?
- Let A_i be the event that i is monochromatic. What is the \mathbb{P}[A_i]?
See answers
- 2^{\binom{n}{2}} possible colorings- \binom{n}{k}
- \mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}
End of quiz time.
Putting all these together, we have:
\mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}
By union bound:
\mathbb{P}[ \cup_{i=1}^{\binom{n}{k}}A_i] \leq \sum_{i=1}^{ \binom{n}{k}}\mathbb{P}[A_i] = \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1}
By assumption of the theorem, 1- \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1} > 0._{\,⬜}
This proof shows the existence of a non-monochromatic K_k, given a two-coloring of the edges of K_n and \binom{n}{k}2^{-\binom{k}{2}+1}<1. In the future, we will look at more sophisticated arguments using the Expectation Argument.
MU: 6.1
'수학 (Mathematics) > 이산확률 (Discrete Probability)' 카테고리의 다른 글
Pairwise Independence and Universal Hash Functions: An Introduction (1) | 2025.03.31 |
---|---|
The Probabilistic Method: Expectation Argument (0) | 2025.03.20 |
Set Theory: Probability (0) | 2023.05.18 |