주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대16. 정보의 양 측정하기

2018.03.30

같이 풀어볼까?

네이버밴드 구글플러스

이번 대한수학회 문제는 기존 문제와 성향이 조금 다릅니다. 새로운 분야 문제에 도전해 보세요. 출제자인 이지운 KAIST 교수님에 따르면 1번은 비교적 쉽고, 2~3번은 어렵다고 합니다. 특히 3번은 교수님도 쉬운 풀이법을 알지 못한다면서, 고등학교 수학 수준으로 해결할 수 있는지 궁금하다고 밝혔습니다. 그럼 문제 나갑니다.

 

양의 정수 \large M에 대해 수열 \large p=\left \{ p_n \right \},\, (n=1, 2, \cdots, M )을 생각합니다. 만약 \large p_1, p_2, \cdots , p_M\geq 0이고 \large p_1+p_2+ \cdots + p_M=1이면 수열 \large p 확률분포로 생각할 수 있습니다. 확률분포 \large p에 대해 평균 \large m(p) 분산 \large V(p)를 다음과 같이 정의합니다.

 

\large m(p)=\sum_{n=1}^{M} np_n, \,\,\,\,\,\,V(p)=\sum_{n=1}^{M}(n-m(p))^2p_n

 

한편, 확률분포 \large p를 통해 알 수 있는 정보의 양은 엔트로피 \large h(p)를 통해 측정할 수 있으며, 이는 다음과 같이 정의합니다.

 

\large h(p)=-\sum_{n=1}^{M}p_nlogp_n

(여기서 log는 자연로그를 의미하며, \large p_n=0인 경우 \large p_nlogp_n=0으로 생각함.)

 

 

문제 1. 주어진 \large M에 대해 엔트로피의 최댓값과 최솟값을 구하세요.

 

 

문제2. 어떤 양수 \large A_1과 \large B_1이 존재해 모든 양의 정수 \large M과 확률분포 \large p에 대해 다음이 성립함을 보이세요. (가능하다면 \large A_1과 \large B_1의 최솟값도 구하세요.)

\large e^h^(^p^)\leq A_1m(p)+B_1

 

 

문제3. 어떤 양수 \large A_2와 \large B_2가 존재해 모든 양의 정수 \large M과 확률분포 \large p에 대해 다음이 성립함을 보이세요. (가능하다면 \large A_2와 \large B_2의 최솟값도 구하세요.)

\large e^2^h^(^p^)\leq A_2V(p)+B_2

 

 

*알립니다!

소문제 (1)번이 수학장, 구머 친구에 의해 해결 됐어요! 

 

댓글 79

  • 수학장 2018.03.30 16:46:28

    1번 최솟값 : 0

    p_n이 1 미만일 때는 -log p_n이 양수가 되기 때문에 모두 0이고 하나만 1일 때 최솟값이 나옵니다

    좋아요0 댓글수2
    • David 2018.03.31 02:40:41

      죄송하지만 모두 0이고 하나만 1일 때 최솟값이 왜 -1이 되나요? 0아닌가요?

      좋아요0
    • 수학장 2018.03.31 07:16:31

      아 ㅋㅋㅋㅋ 제 실수네요 실수로 log 1을 1이라고 계산했네요

      좋아요0
  • 수학장 2018.03.30 21:17:15

    1번 문제 최댓값입니다. 일단, 이 명제부터 증명하겠습니다. a^a\times a^a\leq (a+b)^{a+b}\times (a-b)^{a-b}이걸 증명하면 됩니다. 제가 여러 가지 경우 넣어봤는데 대충 성립합니다. 어쩄든 이걸 증명하면, 최댓값은 -\log\frac{1}{M}=\log M이 됩니다. 왜냐하면, -\sum_{n=1}^{M}p_n\log p_n을 정리하면 -\log (p_1^{p_1}p_2^{p_2}...p_M^{p_M})이게 최대가 되려면 p_1^{p_1}p_2^{p_2}...p_M^{p_M}이 최소가 되야 하는데, 위의 저 정리를 증명하면 p_1,p_2,p_3,.....,p_M=\frac{1}{M}일 때 최소가 되고, 그러면(\frac{1}{M}^{\frac{1}{M}})^M=\frac{1}{M}^{\frac{1}{M}\times M}=\frac{1}{M}이 됩니다.

     

    결론 :  a^a\times a^a\leq (a+b)^{a+b}\times (a-b)^{a-b}이걸 먼저 증명하자.(구머님이 증명해주심)

    이게 설명을 잘 못해서 여러 분들이 오해를 하시는 것 같은데 최댓값은 \log\frac{1}{M}이 아니라 \log M입니다.(2018.4.15)

    좋아요0 댓글수8
    • 수학장 2018.03.31 18:36:47

      음...... 잘 안 풀리네요. 접근부터가 잘못된 걸까요?

      좋아요0
    • Mathdragon 2018.03.31 23:22:54

      a^a\times a^a\leq (a+b)^{a+b}\times (a-b)^{a-b}

      a+b=\alpha, a-b=\beta라 하자.

      \frac{\alpha +\beta }{2}^{(\alpha +\beta) }\leq \alpha ^{\alpha }\times \beta ^{\beta }

      (\alpha +\beta )log{\frac{\alpha +\beta }{2}}\leq \alpha log{\alpha }+\beta log{\beta }

      이렇게 생각해 봅시다.

      좋아요0
    • 구머 2018.04.01 01:31:13

      오랜만입니다. a>b의 가정 하에 증명하였습니다.

      좋아요0
    • 구머 2018.04.01 01:32:27

      비슷한 방식으로 최솟값을 구하려면 하나에 값을 몰아주면 되겠네요.

      좋아요0
    • 수학장 2018.04.01 10:35:52

      최솟값은 맨 위에서 0이라고 구했습니다. 제 생각 증명해주셔서 감사합니다.

      좋아요0
    • 여백 패르마 2018.04.04 20:08:10

      그런데 3번째 줄에서 4번째 줄로 가는 것이 이해가 잘 않되는데, 제 지식이 적은 탓(저는 오래 살지 않았습니다.) 인가요...

      좋아요0
    • 구머 2018.04.04 22:54:38

      (1+1/x)^x가 증가함수이기 때문입니다.

      좋아요0
    • 김우현 기자 2018.04.17 09:33:22

      주정훈 멘토에게 여쭤본 결과, 수학장 친구와 구머 친구의 풀이 모두 정답입니다!laugh

      좋아요0
  • 여백 패르마 2018.04.01 17:00:33

    그런데  수열 a_k가 있을 때     \sum_{k=1}^{n}n^2 a_k하고 (\sum_{k=1}^{n}n a_k)^2를 n과 a_k에 대한 식으로 못나타내나요?

    좋아요0 댓글수3
    • 여백 패르마 2018.04.01 17:18:30

      그러면 조금마나 3번이 풀릴 수 있습니다.

      e^{h(p)}=\frac{1}{e}\prod_{n=1}^{M}{p_n^{p_n}}입니다. 수학장님의 의견대로 \prod_{n=1}^{M}{p_n^{p_n}}의 최댓값은 \frac{1}{M}입니다. 즉, e^{2h(p)}의 최댓값은 \frac{1}{e^{2}M^{2}}입니다. 

      즉, 3번은 언제나 \frac{1}{e^{2}M^{2}}\leq A_2((\sum_{n=1}^{M}n^2p_n)-((\sum_{n=1}^{M}np_n)^2))+B_2이라는 것을 증명해야 합니다.

      2번도 비슷하게 풀 수 있을 듯합니다.

      좋아요0
    • 여백 패르마 2018.04.01 17:20:56

      V(p)=\sum_{n=1}^{M}n^2p_n-(\sum_{n=1}^{M}np_n)^2입니다.

      좋아요0
    • 수학장 2018.04.01 17:50:25

      e^{h(p)}=\frac{1}{\prod_{n=1}^{M}p_{n}^{p_n}}아닌가요?

      좋아요0
  • 수학장 2018.04.01 17:48:34

    2번 문제 식의 좌변에 있는 e^{h(p)}의 값을 구했습니다. 일단, e^{h(p)}=k라고 합시다. 양변에 로그를 취해 주면\log k=h(p)=-\log p_{1}^{p_{1}} p_{2}^{p_{2}}........p_{M}^{p_{M}}(물론 이떄 밑은 e입니다.)

    즉, \log k=-\log p_{1}^{p_{1}} p_{2}^{p_{2}}........p_{M}^{p_{M}}우리가 알고 싶은 건 k값이므로 양변에 로그를 없애주면k=\frac{1}{p_{1}^{p_{1}}p_{2}^{p_{2}}....p_{M}^{p_{M}}}이 됩니다.

     

    좋아요0 댓글수0
  • 여백 패르마 2018.04.01 21:32:42

    제가 전에 쓴것을 바탕으로 가겠습니다.

    \frac{1}{\prod p_n^{p_n}}\leq A_2V(p)+B_2       (V(p)=\sum_{n=1}^{M}n^2p_n-(\sum_{n=1}^{M}np_n)^2)이라는 것을 증명해야 합니다.

    p_a\rightarrow p_a+\varepsilon 이고, 그래서 p_b\rightarrow p_b-\varepsilon이 됩니다. 그러면,  (V(p)=\sum_{n=1}^{M}n^2p_n-)인 분산의 차이는 (a^2-b^2)\varepsilon -(a-b)\varepsilon =(a-b)(a+b-1)\varepsilon입니다.

    또, \prod p_n^{p_n}의 차이는 아무리 적어도p_a^{\varepsilon }-p_b^{\varepsilon }+\varepsilon ^{p_a}+\varepsilon ^{p_b}입니다.

    즉, 약 \varepsilon ^{p_a}+\varepsilon ^{p_b}가 차이 입니다. \varepsilon에서는 너무 작아서 지수는 상관없습니다.

    즉, \frac{1}{2\varepsilon}\leq A_2(a-b)(a+b-1)\varepsilon +B_2을 증명해야 하고, 즉, A_2=\frac{1}{\varepsilon ^2}이면 성립하기 때문에 증명 끝.

    좋아요0 댓글수3
    • 여백 패르마 2018.04.01 21:33:07

      3번입니다 참고로

      좋아요0
    • 수학장 2018.04.01 23:48:45

      \varepsilon은 무한소를 뜻하는 것 아닌가요? 그러면 \frac{1}{\varepsilon^2 }은 무한대가 되니까 A_2를 이거라고 할 수는 없지 않나요?

      좋아요0
    • 여백 패르마 2018.04.03 22:11:11

      \frac{1}{\varepsilon ^2}은 어떤 매우 큰 수이지 무한은 아닙니다.

      좋아요0
  • 수학장 2018.04.02 22:02:14

    여러분 p를 이렇게 나눠봅시다.

    1. p_M이 0인 경우   2. 0이 아닌 경우

    만약 1번 경우라면, M에서 1을 빼고 p_M을 없앱니다. 그래도 h(p)과 m(p), V(p)의 값은 차이가 없습니다.

    그래서 맨 끝의 수가 0이 아닌 수가 될 때까지 맨 끝의 수를 없앱니다.

    저번에 말했다시피 e^{h(p)}=\frac{1}{p_{1}^{p_1}p_{2}^{p_{3}}...p_M^{P_M}}입니다. 이p_{1}^{p_1}p_{2}^{p_{3}}...p_M^{P_M}의 최솟값이 \frac{1}{M}이므로 e^{h(p)}의 최댓값은 M입니다.

    즉, m(p)에 차수가 1 이상인 M이 들어가기만 한다면,(즉 상수가 아니라면) A_1B_1이 존재합니다. 그런데, 우리가 아까 p 맨 끝의 0들을 모두 제거했기 때문에 m(p)는 상수가 나올 수가 없습니다.

    최솟값은 좀 더 해봐야 알 것 같은데, 이 정도로 증명을 끝낼 수 있을까요? 맨 마지막 문장이 좀 애매하긴 한 것 같지만.... 반증이나 오류 발견하면 알려주세요.

    좋아요0 댓글수2
    • 여백 패르마 2018.04.03 15:34:11

      \frac{1}{M}은 최댓값인데..

      좋아요0
    • 수학장 2018.04.03 16:24:16

      1/M이 최솟값입니다

      h(p)의 최댓값은 log M이고요

      좋아요0
  • Mathdragon 2018.04.03 20:53:31

    우선, 수학장님이 구하신 e^{h(p)}의 값은

    =\frac{1}{p_{1}^{p_{1}}p_{2}^{p_{2}}....p_{M}^{p_{M}}}

    가 맞습니다.

    또한, e^{h(p)}의 값은 p_{1}=p_{2}=\cdots =p_{M}=\frac{1}{M}일 때 M으로 최댓값을 가집니다.

    이때의 m(p)의 값은 \sum_{n=1}^{M}np_{n}이므로

    \sum_{n=1}^{M}np_{n}=\frac{1}{M}\sum_{n=1}^{M}n=\frac{1}{M}\times \frac{M(M-1)}{2}=\frac{M-1}{2}

    \therefore M\leq\frac{A_{1}(M-1)}{2}+B_{1}

    (1-\frac{A_{1}}{2})M\leq B_{1}-\frac{A_1}{2}

    M\leq \frac{B_{1}-\frac{A_{1}}{2}}{1-\frac{A_{1}}{2}}

    이렇게 생각할 수도 있을까요?

    좋아요0 댓글수2
    • 수학장 2018.04.03 22:14:18

       

      \sum_{n=1}^{M}np_{n}=\frac{1}{M}\sum_{n=1}^{M}n=\frac{1}{M}\times \frac{M(M-1)}{2}=\frac{M-1}{2}이 부분 잘 이해가 안 가는데요.

      p_n=\frac {1}{M}이라고 한 건가요? 모든 경우에서 증명해야 될 것 같습니다

      좋아요0
    • 여백 패르마 2018.04.03 22:32:23

      최솟값으로 한것 같습니다.

       

      좋아요0
  • 여백 패르마 2018.04.03 22:31:23

    e^{2h(p)}\leq A_2V(p)+B_2이라는 것을 증명해야 합니다.

    e^{2h(p)}의 최댓값은 1/M으로 수학장님 말대로 입니다. 그리고 분산의 성질로 V(p)=\sum_{n=1}^{M}n^2p_n-(\sum_{n=1}^{M}np_n)^2가 있습니다.

    Mathdragon 님의 의견과 같이 \sum_{n=1}^{M}np_n=\frac{1}{M}\sum_{n=1}^{M}n으로 할 수 있습니다. 즉, 분산 V(p)=\frac{1}{M}\sum_{n=1}^{M}n^2-(\frac{1}{M}\sum_{n=1}^{M}n)^2이라고 할 수 있습니다.

    \sum_{n=1}^{M}n^2=\frac{n(n+1)(2n+1)}{6}이고, \sum_{n=1}^{M}n=\frac{n(n+1)}{2}입니다.

    그래서 정리하면 M^2\leq A_2(\frac{(M+1)(2M+1)}{6}-\frac{M^2-2M+1}{4M^2})+B_2이라는 것을 증명해야 합니다.

    그리고, A_2=6이고, B_2=\frac{3}{2}이기면 됩니다.

    Q.E.D

     

    좋아요0 댓글수2
    • 수학장 2018.04.03 23:04:24

      \frac {1}{M^2}이 아니라 M^2이요.......

      마지막 결론에는 제대로 썼네요. 처음 부분 수정하면 됩니다.

      좋아요0
    • 여백 패르마 2018.04.04 18:29:55

      아 다시 보면 특별한 경우만 증명한 것같습니다.

      좋아요0
  • 여백 패르마 2018.04.04 19:47:40

    \varepsilon를 이용한 풀이를 조금 수정하겠습니다. 그리고 \varepsilon은 매우 작은 수로 0.000000001 또는 0.000000000000000000001이 될 수 있습니다. 그런데 0은 아니기 때문에 \frac{1}{\varepsilon^2}은 무한대가 아닙니다.

    먼저, p는 짝으로 \varepsilon만큼 바뀝니다.  p_a\rightarrow p_a+\varepsilonp_b\rightarrow p_b-\varepsilon이라고 합시다. 그러면 분산의 차이는 전의 댓글에 말했듯이 (a^2-b^2)\varepsilon -(a-b)\varepsilon=(a-b)(a+b-1)\varepsilon입니다. 그리고, e^{2h(p)}=\frac{1}{(\prod p_n^{p_n})^2}입니다. 그것의 차이는 적어도 \frac{1}{((p_b-p_a)\varepsilon -\varepsilon^2)^2}입니다. 즉, \frac{1}{((p_b-p_a)\varepsilon -\varepsilon^2)^2}\leq A_2((a-b)(a+b-1)\varepsilon )이라는 것을 증명해야 합니다.                     \varepsilon으로 묶으면 \frac{1}{\varepsilon^{2}((p_b-p_a)-\varepsilon)^2}\leq A_2((a-b)(a+b-1)\varepsilon )이라는 식이 나옵니다. 아무리 차가 커도  p_b-p_a\leq 1이기 때문에 \frac{1}{\varepsilon ^2(1 -\varepsilon)^2}\leq A_2((a-b)(a+b)\varepsilon )이라는 식을 증명해야 합니다. 그리고 B_2항이 없는 이유는 차이에는 상수항이 사라지기 때문입니다. 전개해보면 \varepsilon ^2(1-\varepsilon )^2=(\varepsilon (1-\varepsilon ))^2 =(\varepsilon -\varepsilon ^2)^2 =\varepsilon ^2-2\varepsilon ^3+\varepsilon^4입니다.

    즉, 1\leq (\varepsilon ^2-2\varepsilon ^3+\varepsilon ^4)A_2(a-b)(a+b-1)\varepsilon이여야 합니다. 이제 A_2의 값을 정해봅시다. 그 값은 매우 크지만 상수입니다. 바로 \frac{1}{(\varepsilon ^3-2\varepsilon ^4+\varepsilon ^5)} 입니다. 그러면 1\leq (a-b)(a+b-1)이라는 식이 나오게 됩니다. 그 식의 참은 당연합니다. B_2의 값은 큰 문제가 없습니다. 아무 양수 입니다.

    그리고, p_a+\varepsilon \rightarrow p_a, p_b-\varepsilon \rightarrow p_b으로 바꾸면 반복되어서 결국 모든 p에 대해 참입니다.

    즉, 증명 끝.

    Q.E.D

     

     

    좋아요0 댓글수7
    • 구머 2018.04.04 20:31:14

      e^2h(p)의 차를 정확하게 계산해 보시길 바랍니다

      좋아요0
    • 여백 패르마 2018.04.04 20:54:45

      그러는 방법이 있나요??

      좋아요0
    • 여백 패르마 2018.04.04 21:09:49

      저는 그것의 차이를 진짜보다 적게 하였습니다. 그래야 전체의 차이가 커지기 때문입니다. (분수이기 때문입니다.)

      좋아요0
    • 구머 2018.04.04 21:15:10

      차이가 진짜보다 커야 부등식에 의미가 있는거 아닌가요?

      좋아요0
    • 여백 패르마 2018.04.04 21:21:46

      그래서 차이를 진짜보다 크게 하였습니다.

      좋아요0
    • 구머 2018.04.04 21:31:21

      아 그러네요 ㅋㅋ

      좋아요0
    • 수학장 2018.04.04 23:24:51

      "그리고, p_a+\varepsilon \rightarrow p_a, p_b-\varepsilon \rightarrow p_b으로 바꾸면 반복되어서 결국 모든 p에 대해 참입니다."

      이 부분이 조금 걸리네요. 저번에도 말했듯이, \varepsilon은 무한소가 될 수 밖에 없습니다. \varepsilon이 0이 아니라고는 하시지만, 무한소는 0에 무한히 가까운, 이것보다 작은 양수가 존재하지 않는 양수라고 할 수 있습니다. 만약 \varepsilon이 무한소가 아니라면, \varepsilon보다 작은 양수가 항상 존재하게 되고, 그러면 모든 p에 대해 증명이 불가능합니다.

      결국, \varepsilon이 무한소일 수 밖에 없다는 건데, \lim_{\varepsilon \rightarrow 0} \frac{1}{\varepsilon ^2}=\infty입니다. 귀납적으로 증명하는 것보다는, 귀류법이나 직접 증명이 필요할 것 같습니다.

      좋아요0
  • 여백 패르마 2018.04.06 16:07:11

    3을 풀으려면 e^{2h(p)}이 무한대로 가는 경우는 없다고 증명해야 합니다.  그 이유는 무한이 아니기 한다면 A_2,B_2가 큰 수여라도 문제가 참이기 때문입니다.

    e^{2h(p)}을 간단히 한다면 \frac{1}{(\prod p_n^{p_n})^2}이 됩니다.  이것이 무한대가 되는 경우는 없습니다. 단, p에 0이 포함되어서 \prod p_n^{p_n}가 '정하기 불가' 상황이 될때를 제외한다면 말이죠. (0^0은 결정 불가입니다. 논쟁이 일고 있는 부분이지요.) 이때는 문제로 다시 돌아가야 하며, 엔트로피의 정의로 돌아가야 합니다. 문제에서 p_n=0이면 p_n log p_n은 0이라고 가정했습니다. 즉, 모든 0들은 p_n log p_n이 0이고, 즉 엔트로피 h(p)는 유한하게 되고, 즉 e^{2h(p)}가 유한하게 됩니다. 그 뜻은 e^{2h(p)}는 언제나 무한이 도지 않고, 증명 끝.

    Q.E.D

    좋아요0 댓글수3
    • 구머 2018.04.06 16:15:17

      M이 무한으로 수렴하면 e^2h(p)도 무한으로 수렴하게 됩니다.

      좋아요0
    • 여백 패르마 2018.04.07 15:26:19

      그러면 분산은 계산 불가인 무한대-무한대가 됩니다. 

      좋아요0
    • 구머 2018.04.07 15:38:58

      V(p)의 원래 식을 보면 무한-무한 꼴이 나오지 않게 할수 있고,(정확히 계산은 안해봤지만 상식으로 분산이 꼭 무한으로 수렴하지 않는 경우도 많던걸로 기억합니다)

      그럼 e2h(p)/v(p)가 무한으로 수렴하니까 a2가 무한으로 수렴해야 해서 모순이죠.

      좋아요0
  • 여백 패르마 2018.04.10 16:10:16

    좋아요0 댓글수14
    • 여백 패르마 2018.04.10 16:12:08

      3번 풀이이고, 순서는..거꾸로입니다.

      좋아요0
    • 구머 2018.04.10 16:56:28

      M->무한일 때 p1=1, 나머지는 0일때 V(p),M(p)를 구해보면 무한-무한 꼴이 되지 않습니다.

      전댓글에도 언급했던것 같은데..

      좋아요0
    • 여백 패르마 2018.04.11 14:09:59

      A2가 무한이 될수 있습니다. 

      좋아요0
    • 구머 2018.04.11 16:30:47

      그리고 패르마님 답을 얻기 전에 일부 값들을 미리 대입해봐서 식이 성립하는지 확인하는 작업이 필요하신 것 같습니다.

      좋아요0
    • 구머 2018.04.11 16:32:24

      그리고 무한이 되는 경우도 있지만 안되는 경우또한 존재하고, (위 예시처럼) 따라서 m이 무한으로 수렴하지 않는다는 논리를 사용할 수 없습니다.

      좋아요0
    • vorn보른 2018.04.11 16:45:31

      그동안 패르마님 풀이를 꽤 많이 봤었는데, 패르마님은 아직 무한에 대한 정확한 개념이 부족한 것 같습니다..이 문제는 딱히 무한을 써서 푸는 문제가 아닌것 같으니 같이 다른 방법을 생각해봐요.

      좋아요0
    • 여백 패르마 2018.04.11 16:48:32

      아 최솟값 0은 실수입니다...

      좋아요0
    • 여백 패르마 2018.04.11 19:16:37

      M이 무한대로 가도 양의 정수가 된다면 A2도 무한대로 갈 수 있습니다. 즉, 성립합니다.

      좋아요0
    • vorn보른 2018.04.11 20:06:43

      문제에서 A2가 어떤 양수라 하지 않았나요? 무한이 되면 안될것 같아요.(애초에 그런식으로 풀리면 문제의 의미가..)

      좋아요0
    • 여백 패르마 2018.04.12 07:10:21

      M도 양수라고 했습니다. 그래서 M도 무한으로 가면 않됩니다.

      좋아요0
    • vorn보른 2018.04.12 07:21:24

      하지만 A2가 정해져 있다면 그 A2를 넘어서는 M은 무한이 아니라도 잡을 수 있습니다. 다른 논리가 필요할 것 같습니다.

      좋아요0
    • 여백 패르마 2018.04.12 08:34:26

      ...A2는 정해지는 것이 아닙니다 그리고 엔트로피의 최댔값은 M이 무한 으로 가면 0 이 됩니다. 그 이유는 \frac{1}{M}이 0 이 되기때문입니다.

      좋아요0
    • vorn보른 2018.04.12 13:32:24

      ?엔트로피 최댓값은 1/m이 아닌데.. 최댓값은 -log(1/m)=log m아닌가요?

      좋아요0
    • 구머 2018.04.12 16:46:54

      패르마님 지금 전혀 문제를 잘못 이해하신것 같은데 A2 B2는 고정된 값입니다..M이 어떻게 되든 방정식이 성립하는 A2를 찾는 게 문제 2 3번입니다.

      좋아요0
  • 여백 패르마 2018.04.12 16:13:32

    문제 2,3 번을 풀기 위해서는 엔트로피인 h(p)가 유한하다는 것을 증명해야 합니다. 귀류법을 씁시다. 즉, h(p)가 무한할 수 없다는 것을 증명합시다.

    #1. p에 0이 있지 않은 경우 (M\rightarrow \infty이진 않습니다.) 

    이 경우에는 엔트로피는 유한합니다.  그 이유는 n< 1일때 n^n은 1보다 작고, 1보다 작은 수들을 계속 곱하면 1보다 작으며, 1보다 작은 수에 log를 붙이면 그 값은 음수가 되고, 절대로 -\infty가 되지 않기 때문입니다. 

    #2. p에 0이 있는 경우 (M\rightarrow \infty이진 않습니다.)

    이경우에는 수학적 귀납법을 씁시다. 먼저, M이 2이면 당연히 성립합니다. 또, M-1과 그 전때 일때 언제나 성립한다고 합시다. 그리고 M이면서 p에 0이 있다고 합시다. 그러면 무네에 의해서 p안의 0항은 없는 듯 만듯이 됩니다. 그 이유는 p_nlog(p_n)이 p_n이 0이면 0이라고 문제에서 말했기 때문입니다. 즉, p에서 있는 0은 빼도 괜찮습니다. 즉, 전의 것들은 언제나 성립하기 때문에 #2도 성립합니다. 

    또, M\rightarrow \infty은 엔트로피가 계산불가입니다.( 최댓값이 log 0이여서..)

    Q.E.D

    좋아요0 댓글수5
    • 구머 2018.04.12 16:29:48

      문제에서 plogp=0, 즉 logp^p=0이라고 가정한다는 것은 p^p=e^0=1이라고 계산하라는 것과 같습니다.

       

      //윗분 댓 확인

      좋아요0
    • 여백 패르마 2018.04.13 15:07:03

      그래도 유한하지 않나요?? 그리고우리가 문제의 식을 만족하는 수를 찾으라는 것입니다. 유리가 정해서 고정된 값으로 먼들기 때뮨입니다. 

      좋아요0
    • 구머 2018.04.13 20:37:59

      뭐가 유한한가요? 그리고 문제의 식을 만족하라는 건 뭔 수를 의미하나요? 구체적으로 주어를 생략하지 말고 말해주세요.

      좋아요0
    • 구머 2018.04.14 14:32:22

      그리고 각경우마다 그 경우를 만족하는 A2 B2을 찾는게 아니라 모든 경우를 만족시키는 A2 B2를 찾는 거에요.. 애초에 문제가 패르마님이 생각한 그런 문제면 아무나 다 풀수 있을 건데 내질 않겠죠.

      좋아요0
    • 여백 패르마 2018.04.14 22:02:54

      아... 그렇군뇨

      좋아요0
  • 여백 패르마 2018.04.14 13:19:10

    그런데 A2과 B2의 최솟값은 뭔가요?? 그 둘의 합이 최소인가요, 아니면 그 둘중 하나가 가장 작은 것인가요??

    좋아요0 댓글수2
    • 구머 2018.04.14 13:31:35

      A2, B2가 각각 어떤 수보다 크기만 하면 모든 M과 p들에 대해 등식이 성립하는데,  그 어떤 수를 구하란 거죠

      좋아요0
    • 여백 패르마 2018.04.14 21:54:56

      아...

      좋아요0
  • 여백 패르마 2018.04.14 22:02:23

    e^{2h(p)}의 최댓값은 \frac{1}{M^2}입니다. 그리고 \frac{1}{M^2}의 최댓값은 M이 1일때, 즉, 1입니다.  그 뜻은 모든 M에 관해서, 그리고 p에 관해서 1\leq A_2V(p)+B_2을 만족하는 A_2와 B_2가 존재한다는 것을 증명해야 합니다.  그리고,  V(p)=\sum_{n=1}^{M}n^2p_n-(\sum_{n=1}^{M}np_n)^2입니다.  이 분산의 최솟값은 0입니다. p_1=1이고 다른 p_n=0일때이지요. 그 이유는 1을 재외한 모든 n에 대해 n^2> n이기 때문에 그러면 V(p)=\sum_{n=1}^{M}n^2p_n가 최소가 되고 (\sum_{n=1}^{M}np_n)^2,즉 (\sum_{n=1}^{M}np_n)가 최대가 되지 않기 때문입니다. 즉, n^2=n인 1=n를 택하고 그래서 분산의 최솟값이 0입니다. (다른풀이:(확실하지는 않음.) 분산은 언제나 \mathbb{N}_0입니다. 즉, \mathbb{N}_0의 최솟값인 0이 분산의 최솟값입니다. 단, \mathbb{N}_0=\mathbb{N}+0입니다. ) 그렇기 때문에 1\leq B_2+0\times A_2이라는 식이 나오고, 즉 1\leq B_2입니다. 그 뜻은 A_2는 어떤 양수이고, 1\leq B_2이기만 하면 성립한다는 것을 알 수 있습니다. 그렇기 때문에 3번의 반절은 성립합니다. 

    또, 최솟값은 B_2는 1, 그리고 A_2는 0이라는 것을 알 수 있습니다. 

    좋아요0 댓글수2
    • 깜냥 2018.04.14 22:24:52

      패르마님 지금 뭔가 착각하신 것 같은데 e^{2h(p)}의 최댓값은 \frac{1}{M^{2}}이 아니라 M^{2}입니다. h(p)의 최댓값이 logM이거든요.

      위에 수학장님 댓글에도 써 있습니다. 다시 한 번 문제를 잘 읽어보세요.

      좋아요0
    • 여백 패르마 2018.04.15 12:10:42

      왜 계속 실수만 하지?ㅠㅠ

      좋아요0
  • 여백 패르마 2018.04.15 14:26:04

    안 맞는 것일지도 모르지만, 귀납법적 증명을 하겠습니다.  시작은 전의 댓글과 같습니다.  확률분포는 짝으로 \varepsilon만큼 바귄다는 것과 p_a\rightarrow p_a+\varepsilon   p_b\rightarrow p_b-\varepsilon으로 부터 시작합니다.  그때 필요한것은 이항정리입니다. 그것의 증명은 다음과 같습니다: \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}라는 등식을 먼저 증명해야 합니다. 그것의 증명은 다음과 같습니다. \binom{n}{k}=\frac{n!}{(n-k)!k!}이고, \binom{n-1}{k-1}=\frac{(n-1)!}{(n-k)!(k-1)!}이며,  \binom{n-1}{k}=\frac{(n-1)!}{(n-k-1)!k!}이다. 우변=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}=(\frac{1}{n-k}+\frac{1}{k})\times \frac{(n-1)!}{(k-1)!(n-k-1)!}=\frac{(n-1)!}{(k-1)!(n-k-1)!}\times \frac{n}{k(n-k)}=\binom{n}{k} 

    이제 이항정리를 증명합시다. (x+y)^{n+1}=(x+y)(x+y)^{n}=(x+y)\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}=x\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}+y\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}=\sum_{k=0}^{n}\binom{n}{k}x^{n+1-k}y^{k}+\sum_{k=1}^{n+1}\binom{n}{k-1}x^{n+1-k}y^k+y^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}x^{n+1-k}y^{k}입니다. (p_a+\varepsilon)^{p_a+\varepsilon}(p_b-\varepsilon )^{p_b-\varepsilon }=(p_a+\varepsilon )^{p_a}(p_b-\varepsilon )^{p_b}p_a^{\varepsilon }p_b^{\varepsilon }입니다. \lim_{\varepsilon \rightarrow 0}p_{a,b}^{\varepsilon }=1이기때문에 =(p_a+\varepsilon )^{p_a}(p_b-\varepsilon )^{p_b}이라고 할 수 있습니다. 이항정리로 하면 (p_a^{p_a}p_b^{p_b}을 뺏습니다.) (\binom{p_a}{1}\varepsilon p_a^{p_a-1}+...+\varepsilon ^{p_a})(\binom{p_b}{1}\varepsilon p_b^{p_b-1}+...+\varepsilon ^{p_b})입니다.즉, e^{2h(p)}의 차이는  \frac{(\binom{p_a}{1}\varepsilon p_a^{p_a-1}+...+\varepsilon ^{p_a})(\binom{p_b}{1}\varepsilon p_b^{p_b-1}+...+\varepsilon ^{p_b})}{p_a^{p_a}p_b^{p_b}(p_a+\varepsilon )^{p_a+\varepsilon }(p_b-\varepsilon) ^{p_b-\varepsilon }}입니다. 분산은 V(p)=\sum_{n=1}^{M}n^2p_n-(\sum_{n=1}^{M}np_n)^2입니다. 즉, 분산의 차이는 a^2\varepsilon -b^2\varepsilon +a^2\varepsilon ^2-b^2\varepsilon ^2입니다. 

    \frac{(\binom{p_a}{1}\varepsilon p_a^{p_a-1}+...+\varepsilon ^{p_a})(\binom{p_b}{1}\varepsilon p_b^{p_b-1}+...+\varepsilon ^{p_b})}{p_a^{p_a}p_b^{p_b}(p_a+\varepsilon )^{p_a+\varepsilon }(p_b-\varepsilon) ^{p_b-\varepsilon }}\leq A_2(a^2\varepsilon -b^2\varepsilon +a^2\varepsilon ^2-b^2\varepsilon ^2)이라는 것을 증명해야 합니다. \varepsilon이 양변으로 지위집니다. 이제 \lim_{\varepsilon \rightarrow 0}를 취하면 됩니다. 그러면 \frac{1}{p_a^{2p_a-1}p_b^{2p_b-1}}\leq A_2(a^2-b^2)이 나옵니다. p_a,p_b이 최댓값은 \frac{1}{2}이기 때문에 대입하면 1\leq A_2(a^2-b^2)이 나옵니다. (a^2-b^2)의 최솟값은 a=2,b=1으로, 3입니다. 즉, A_2의 최솟값은 \frac{1}{3}이 나옵니다. 그래서 3번의 반절이 증명됬습니다.

    Q.E.D

    좋아요0 댓글수0
  • 여백 패르마 2018.04.15 22:14:53

    좋아요0 댓글수3
    • 여백 패르마 2018.04.15 22:15:37

      맨 마지막에 있는 부등식을 생각해야 합니다. 

      좋아요0
    • 여백 패르마 2018.04.15 22:18:48

      전 풀이에 매우 작은 오류가 있어서 수정했습니다. 아이디어와 거의 다 식은 비슷합니다.

      좋아요0
    • 여백 패르마 2018.04.17 15:29:29

      아 진짜...... crying오류가 있다...

      부등식이 않풀려.....

      좋아요0
  • 곽민정 2018.04.17 21:54:54

    ll,,l,

    좋아요0 댓글수1
    • 여백 패르마 2018.04.18 18:36:00

      그것이 뭔 뜻이지요??...

      좋아요0
  • 여백 패르마 2018.04.18 14:58:35

    좋아요0 댓글수2
    • 여백 패르마 2018.04.22 14:21:19

      3번 풀이입니다...

      좋아요0
    • 여백 패르마 2018.04.25 16:11:06

      비슷한 방법으로 2번을 풀 수 있다고 생각합니다.

      \frac{1}{p_a^{p_a}\cdot p_b^{p_b}}-\frac{1}{(p_a+\varepsilon )^{p_a}\cdot (p_b-\varepsilon )^{p_b}}=\frac{\varepsilon \cdot ((p_a^{p_a-1}\cdot p_b^{p_b}+p_a^{p_a}\cdot p_b^{p_b-1})+\varepsilon \cdot (\chi ))}{p_a^{p_a}\cdot p_b^{p_b}\cdot (p_a+\varepsilon )^{p_a}\cdot (p_a-\varepsilon )^{p_b}}(\chi=\varepsilon로 묶일 수 있는 것)을 이용합니다.

      좋아요0