반말재성합니다 프갤에서 여기다가물어모라고해서 복붙해왔어요






나는 저거 증명하다보니까

e >= 1 / |B| 가 나오거든?

이게 문제에서 요구하는거의 충분조건이니까 어떻게 보면 풀었다고 할 수도 있는건데

진짜 이게 성립하면 문제를 저런 식으로 안 내고 바로 e >= 1 / |B|를 증명하라고 냈을 거 같단 말이지

그래서 틀린건지 맞은건지 감이 안 와서 질문함


저런 경우에 e >= 1 / |B|가 성립함?


내가 푼 방법은

1. U의 원소 k와 l이 서로 같은 해시값을 가지는 경우의 indicator random variable을 X(k,l)이라고 표기함

2. U의 원소중에서 같은 해시값을 가지는 애들을 다 묶어서 집합을 만들고 이걸 T(1), T(2), ... , T(|B|) 로 표기함

3. UxU에 속하는 모든 순서쌍 (k,l)에 대해 X(k,l)을 다 더한 값은, ∑i=1..|B| (T(i)^2)와 같음

4. 코시 슈바르츠 부등식에 의해 ∑i=1..|B| (T(i)^2)는 (∑i=1..|B| (T(i)))^2 / |B| 보다 크거나 같음

5. (∑i=1..|B| (T(i)))^2 / |B| 는 |U|^2 / |B| 와 같음

6. 3, 4, 5번에 의해서, {UxU에 속하는 모든 순서쌍 (k,l)에 대해 X(k,l)을 다 더한 값} >= |U|^2 / |B| 이 성립함

7. 그런데 문제에서 주어진 조건과 기대값의 선형성에 의해, E({UxU에 속하는 모든 순서쌍 (k,l)에 대해 X(k,l)을 다 더한 값}) <= e * |U|^2가 성립함

8. 6, 7번에 의해, e * |U|^2 >= E({UxU에 속하는 모든 순서쌍 (k,l)에 대해 X(k,l)을 다 더한 값}) >= E(|U|^2 / |B|) = |U|^2 / |B|  임

9. 8을 정리하면 e * |U|^2 >= |U|^2 / |B|

10. 따라서 e >= 1 / |B|


위 풀이에 오류 있음..?

알고리즘 잘하는사람들아 도와줘


도와주세요