블록 설계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 존슨 결합 도식 속의 블록 설계
- 2.2. 일반적 결합 도식 속의 블록 설계
3. 성질
4. 연산
- 4.1. 유도 블록 설계
- 4.2. 결합 행렬
5. 종류
6. 예시
7. 역사
8. 응용
참조

1. 개요

블록 설계는 유한 집합 X의 원(점)과 k개의 원으로 구성된 X의 부분 집합(블록)으로 정의되며, 특정 조건을 만족하는 2-디자인을 형성한다. 이 디자인은 점의 개수 v, 블록의 개수 b, 각 점을 포함하는 블록의 개수 r, 하나의 블록에 포함된 점의 개수 k, 두 점을 함께 포함하는 블록의 개수 λ를 파라미터로 갖는다. 블록 설계는 균형 불완전 블록 설계(BIBD), 대칭 2-디자인(SBIBD), 가분 2-디자인, 일반 균형 디자인(t-디자인) 및 부분 균형 디자인(PBIBD) 등 다양한 종류로 분류되며, 실험 계획법, 오류 정정 부호, 소프트웨어 테스팅 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

집합족 - 가측 공간
가측 공간은 집합과 그의 멱집합의 부분 시그마 대수로 이루어진 순서쌍으로, 시그마 대수는 여집합과 가산 합집합에 대해 닫혀 있는 성질을 가지며, 가측 공간과 가측 함수는 구체적 범주를 이룬다.
집합족 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
조합론 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
조합론 - 계승 (수학)
계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다.
실험 설계 - 무작위 대조 시험
실험 설계 - 실험군과 대조군
실험군과 대조군은 임상 연구에서 새로운 방법이나 약물의 효과를 평가하기 위해 사용되는 두 그룹으로, 대조군은 비교 기준이 되며, 실험군은 새로운 치료법을 받는 그룹이다.

블록 설계
개요
분야	조합론
하위 분야	설계 이론
관련 항목	조합 설계 실험 설계 유한 기하학 코딩 이론 암호학
정의
블록 설계란	유한 집합의 원소들을 블록이라 불리는 부분집합으로 구성하여 특정 조건을 만족하도록 하는 구조
블록	설계에서 사용되는 부분집합
빈도	원소가 블록에 나타나는 횟수 (정확한 정의 필요)
종류
균형 불완전 블록 설계 (BIBD)	모든 블록의 크기가 동일하고, 각 원소 쌍이 동일한 수의 블록에 나타나는 블록 설계
부분 기하	BIBD의 특수한 경우로, 추가적인 기하학적 구조를 가짐
3-설계	각 3개의 원소 집합이 동일한 수의 블록에 나타나는 블록 설계
하다마르 설계	하다마르 행렬에서 유도되는 블록 설계
전단사 블록 설계	블록 간의 전단사 사상이 존재하는 블록 설계
응용
통계적 실험 설계	다양한 처리 효과를 비교하기 위한 실험 설계에 사용
암호학	암호 시스템의 구성 요소로 사용
코딩 이론	오류 정정 코드 설계에 사용
관련 연구
설계 이론	블록 설계 및 관련 조합 구조를 연구하는 분야
조합론적 행렬	블록 설계의 표현 및 분석에 사용되는 행렬

2. 정의

세 자연수 $t,k,n$ 에 대하여, ''' $(t,k,n)$ -블록 설계''' $(X,\mathcal B)$ 는 다음 조건을 만족하는 조합론적 구조이다.

크기가 $n$ 인 유한 집합 $X$ 가 주어져 있고, 그 원소를 '''점'''(point^영어)이라고 한다.
$X$ 의 부분집합 중 크기가 $k$ 인 것들의 집합족 $\mathcal B\subseteq\operatorname{Pow}_k(X)$ 가 주어져 있고, 그 원소를 '''블록'''(block^영어)이라고 한다. ( $\operatorname{Pow}_k(X)$ 는 $X$ 의 부분 집합들 가운데 크기가 $k$ 인 것들로 구성된, 멱집합의 부분 집합이다.)
$t$ 개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값 $\lambda_t>0$ 이어야 한다.

두

(t,k,n)

-블록 설계

(X,\mathcal B)

,

(X',\mathcal B')

가 주어졌을 때, 다음을 만족하는 전단사 함수

:

\iota\colon X\to X'

가 존재하면,

(X,\mathcal B)

와

(X',\mathcal B')

는 서로 '''동형'''이라고 한다.

:

\{\iota(B)\}_{B\in\mathcal B}=\mathcal B'

\lambda_t=1

인

(t,k,n)

-블록 설계는 '''

(t,k,n)

-슈타이너 계'''(Steiner系, Steiner system|스타이너 시스템^영어)라고 하며, 보통

\operatorname S(t,k,n)

로 표기한다.

통계학에서 블록 설계는 블록이 요소의 여러 복사본을 포함할 수 있는 ''비이진'' 블록 설계로 확장될 수 있다. 각 요소가 동일한 총 횟수로 발생하는 설계를 ''등반복''이라고 하며, 설계가 이진이 아닌 경우에만 ''정규'' 설계를 의미한다.

유한 집합 ''X''와 양의 정수 ''k'', ''r'', λ가 주어졌을 때, ''X''의 원을 '''점'''이라 하고, ''k''개의 원으로 구성된 ''X''의 부분 집합을 '''블록'''이라고 한다. 이때 튜플 (''X'', ''B'') (''B''는 블록의 집합)가 다음 조건을 만족하면, '''2-디자인''' 또는 간단히 '''디자인'''이라고 한다.

임의의 서로 다른 두 점 ''x'', ''y''에 대해, ''x''와 ''y''를 함께 포함하는 ''B''의 원은 정확히 λ개이다. (이 조건으로 첫번째 조건은 자동 만족)
임의의 점 ''x''에 대해, ''x''를 포함하는 ''B''의 원은 정확히 ''r''개이다.

디자인의 파라미터는 점의 개수 ''v'', 블록의 개수 ''b'', 어떤 점을 포함하는 블록의 개수 ''r'', 하나의 블록에 포함된 점의 개수 ''k'', 서로 다른 두 점을 포함하는 블록의 개수 ''λ''이다.

파라미터	의미
v	점의 개수 (X의 원소 개수)
b	블록의 개수 (B의 원소 개수)
r	어떤 점을 포함하는 블록의 개수
k	하나의 블록에 포함된 점의 개수
λ	서로 다른 두 점을 포함하는 블록의 개수

파라미터 ''v'', ''b'', ''r'', ''k'', λ를 갖는 디자인은 (''v'', ''k'', λ)-디자인 또는 (''v'', ''b'', ''r'', ''k'', λ)-디자인 등으로 표기된다. 파라미터들은 모두 독립적인 것은 아니며, ''v'', ''k'', λ를 주면 ''b'', ''r''이 결정된다.

2. 1. 존슨 결합 도식 속의 블록 설계

세 자연수 t, k, n에 대하여, (t, k, n)-블록 설계는 다음 조건을 만족시키는 조합론적 구조이다. λ_t = 1인 (t, k, n)-블록 설계를 (t, k, n)-슈타이너 계(Steiner system)라고 한다.

2. 2. 일반적 결합 도식 속의 블록 설계

결합 도식

(X,\{D_i\in\operatorname{Mat}(|X|,|X|;\mathbb Z)\}_{i\in I})

이 주어졌다고 하자. 그렇다면, 그 복소수 계수 보스-메스너 대수

:

\mathcal A=\operatorname{Span}_{\mathbb C}\{D_i\}_{i\in I}\subseteq\operatorname{Mat}(|X|,|X|;\mathbb C)

는 반단순 대수이며, 따라서 그 최소 멱등원들의 집합

:

(E_a)_{a\in A}

:

E_aE_b=\delta_{ab}E_a

:

\sum_{a\in A}E_a=1_{\mathcal A}

를 정의할 수 있다. 특히,

:

E_0=\frac1

\mathsf J_

는 항상 최소 멱등원이다. (

\mathsf J_

는 모든 성분이 1인

|X|\times|X|

정사각 행렬이다.)

이제, 계수

:

E_a=\sum_{i=0}^

Q_{ai}D_i

들을 정의할 수 있다.

X

의 부분 집합(즉,

X

속의 블록 부호)

C\subseteq X

가 주어졌을 때, 내부 분포

:

\alpha_i=\frac

및 쌍대 내부 분포

:

\beta_a=\sum_{i\in I}Q_{ai}\alpha_i

를 정의할 수 있다.

만약 어떤 부분 집합

E\subseteq A

가 주어졌을 때, 만약

X

의 부분 집합

C\subseteq X

가 다음 조건을 만족시킬 경우, '''

E

-블록 설계'''(E-block design^영어)라고 한다.^[43]

:임의의

a\not\in E

에 대하여,

\beta_a=0

만약

X

가 존슨 결합 대수일 때, 이는 첫째 정의로 귀결된다.

3. 성질

임의의 (t, k, n)-블록 설계 (X, ${\mathcal B}$)가 주어졌을 때, 다음이 성립한다.

0 ≤ i ≤ t 인 i에 대하여, i개의 점들을 모두 포함하는 블록의 개수는 정확히

::

\lambda_i=\frac{\lambda_t\binom {n-i}{t-i}}{\binom{k-i}{t-i}}\qquad(i\in\{0,1,\dotsc,t\})

이다.

특히, i=0일 경우, 블록의 수는 $\textstyle\lambda_0 = \lambda_t \binom nt / \binom kt$ 이다.

이에 따라, 모든 (t, k, n)-블록 설계는 임의의 0 ≤ t' ≤ t에 대하여 (t', k, n)-블록 설계이다.

'''피셔 부등식'''(Fisher’s inequality^영어)에 따르면,^[52] 임의의 (2, k, n)-블록 설계 (X, ${\mathcal B}$)에 대하여, 다음이 성립한다.

:

|X| \ge \lambda_0

:

k \ge \lambda_1

(Xλ₁=kλ₀이므로, 두 조건은 사실 동치이다.) 이 부등식을 포화시키는 블록 설계, 즉 점의 수가 블록의 수와 같은 2-블록 설계를 '''정사각 블록 설계'''(square block matrix^영어) 또는 '''대칭 블록 설계'''(symmetric block design^영어)라고 한다.

보다 일반적으로, 임의의 (t, k, n)-블록 설계 (X,${\mathcal B}$)에 대하여, 다음이 성립한다.^[44]

:

\lambda_0 \ge \binom n{\lfloor t/2\rfloor}

'''브룩-라이저-차울라 정리'''(Bruck–Ryser–Chowla theorem^영어)에 따르면,^[45]^[46] 임의의 (t, k, n)-블록 설계 (X,${\mathcal B}$)에 대하여, 만약 |X| = λ₀라면,

만약 |X|가 짝수라면, k - λ₂는 제곱수이다.
만약 |X|가 홀수라면, x² = (k - λ₂)y² + (-1)^(|X|-1)/2λ₂z²를 만족시키는 정수 (x, y, z) ≠ (0, 0, 0)가 존재한다.

4. 연산

블록 설계의 연산에는 유도 블록 설계와 결합 행렬이 있다.

'''유도 블록 설계'''는 임의의 $(t,k,n)$ -블록 설계 $(X,\mathcal B)$ 및 점 $x\in X$ 가 주어졌을 때, $X'=X\setminus\{x\}$ 와 $\mathcal B'=\{B\setminus\{x\}\colon x\in B\in\mathcal B\}$ 는 $(t-1,k-1,n-1)$ -블록 설계를 이루는 것을 말한다. 이를 $(X,\mathcal B)$ 의 유도 블록 설계라고 하며, 서로 다른 점에서 취한 유도 블록 설계는 서로 동형이 아닐 수 있다.

$(t,k,n)$ -블록 설계 $(X,\mathcal B)$ 에서, $X=\{x_1,\dotsc,x_n\}$ 와 $\mathcal B=\{B_1,\dotsc,B_{\lambda_0}\}$ 위에 각각 임의로 전순서를 부여하면, '''결합 행렬'''은 다음과 같은 $n\times\lambda_0$ 행렬이다.

: $M\in\operatorname{Mat}(n,\lambda_0;\mathbb F_2)$

: $M_{ij}=\begin{cases}1 & x_i\in B_j \\ 0 & x_i \not\in B_j\end{cases}$

정사각 블록 설계의 경우 결합 행렬은 정사각 행렬이다.

4. 1. 유도 블록 설계

임의의

(t,k,n)

-블록 설계

(X,\mathcal B)

및 점

x\in X

가 주어졌을 때, 다음과 같이 정의되는

X'

와

\mathcal B'

는

(t-1,k-1,n-1)

-블록 설계를 이룬다.

:

X'=X\setminus\{x\}

:

\mathcal B'=\{B\setminus\{x\}\colon x\in B\in\mathcal B\}

이때,

\lambda'_{t-1}=\lambda_t

이다. 이를

(X,\mathcal B)

의 '''유도 블록 설계'''( derived block design^영어 )라고 한다. 서로 다른 점에서 취한 유도 블록 설계는 서로 동형이 아닐 수 있다.

슈타이너 계의 유도 블록 설계는 항상 슈타이너 계이다.

t-(''v'',''k'',''λ'') 디자인 '''D''' = (''X'', ''B'')에서 ''p''를 ''X''의 점이라고 할 때, ''유도 디자인'' ''D''_''p''는 점 집합 ''X'' − {''p''}를 가지며, 블록 집합은 ''p''를 포함하는 '''D'''의 모든 블록에서 ''p''를 제거한 블록으로 구성된다. 이는 (''t'' − 1)-(''v'' − 1, ''k'' − 1, ''λ'') 디자인이다. 서로 다른 점에 대한 유도 디자인은 동형이 아닐 수 있다.

4. 2. 결합 행렬

(t,k,n)

-블록 설계

(X,\mathcal B)

에서,

X=\{x_1,\dotsc,x_n\}

와

\mathcal B=\{B_1,\dotsc,B_{\lambda_0}\}

위에 각각 임의로 전순서를 부여할 수 있다. 그렇다면,

(X,\mathcal B)

의 '''결합 행렬'''(incidence matrix^영어)은 다음과 같은

n\times\lambda_0

행렬이다.

:

M\in\operatorname{Mat}(n,\lambda_0;\mathbb F_2)

:

M_{ij}=\begin{cases}1 & x_i\in B_j \\ 0 & x_i \not\in B_j\end{cases}

정사각 블록 설계의 경우 결합 행렬은 정사각 행렬이다.

표준화된 형태의 크기가 4''a''인 아다마르 행렬이 주어지면, 첫 번째 행과 첫 번째 열을 제거하고 모든 −1을 0으로 변환한다. 결과적인 0–1 행렬 '''M'''은 '''아다마르 2-설계'''라고 하는 대칭 2-(4''a'' − 1, 2''a'' − 1, ''a'' − 1)의 사건 행렬이다.^[20] 이 설계는

4a-1

개의 블록/점을 포함하며, 각 블록은

2a-1

개의 점/블록을 포함하거나 포함된다. 점들의 각 쌍은 정확히

a-1

개의 블록에 포함된다.

5. 종류

블록 설계는 여러 종류로 나뉜다.

균형 불완전 블록 설계 (BIBD): 모든 쌍의 점들이 동일한 수의 블록에 포함되는 설계이다.
대칭 2-디자인 (SBIBD): 점과 블록의 수가 같은 2-설계이다. 피셔의 부등식에 의해, 이는 동일한 점의 수를 가진 모든 2-설계 중에서 가장 적은 수의 블록을 가진다.
가분 2-디자인: 블록을 ''평행 클래스''라는 집합으로 분할할 수 있는 BIBD이며, 각 평행 클래스는 BIBD의 점 집합의 분할을 이룬다.
일반 균형 디자인 (t-디자인): 모든 t개의 점들의 집합이 동일한 수의 블록에 포함되는 설계이다.
부분 균형 디자인 (PBIBD): 점들 간의 관계를 나타내는 결합 도식을 이용하여 정의된다.

5. 1. 균형 불완전 블록 설계 (BIBD)

균형 불완전 블록 설계(BIBD) 또는 2-디자인은 모든 쌍의 점들이 동일한 수(λ)의 블록에 포함되는 설계이다.

유한 집합 ''X''(원소는 ''점''이라고 부름)와 정수 ''k'', ''r'', ''λ'' ≥ 1이 주어졌을 때, 2-설계는 ''X''의 ''k''-원소 부분 집합(블록)의 모임 ''B''로 정의된다. 이때, ''X''의 모든 점 ''x''는 ''r''개의 블록에 포함되고, ''X''의 서로 다른 두 점 ''x''와 ''y''는 ''λ''개의 블록에 포함된다.

여기서 ''v''(''X''의 원소 수, 점의 수), ''b''(블록 수), ''k'', ''r'', ''λ''는 설계의 매개변수이다. 이러한 설계는 (''v'', ''k'', ''λ'')-설계 또는 (''v'', ''b'', ''r'', ''k'', ''λ'')-설계로 불린다. 매개변수들은 서로 독립적이지 않으며, 다음 두 기본 방정식을 만족해야 한다.

:

bk = vr,

:

\lambda(v-1) = r(k-1),

이 방정식들을 통해 ''v'', ''k'', ''λ''가 주어지면 ''b''와 ''r''을 계산할 수 있다. 하지만, ''v'', ''k'', ''λ''의 모든 조합이 가능한 것은 아니다. 예를 들어, (43,7,1)-설계는 존재하지 않는다.^[4]

2-설계의 ''차수''는 ''n'' = ''r'' − ''λ''로 정의된다. 2-설계의 '''보수'''는 각 블록을 점 집합 ''X''에서 그 여집합으로 대체하여 얻으며, 또 다른 2-설계가 된다.

로널드 피셔의 이름을 딴 피셔의 부등식에 따르면, 모든 2-설계에서 ''b'' ≥ ''v''이다.

파라미터	설명
v	점의 개수 (X의 원소 수)
b	블록의 개수 (B의 원소 수)
r	특정 점을 포함하는 블록의 개수
k	하나의 블록에 포함된 점의 개수
λ	서로 다른 두 점을 동시에 포함하는 블록의 개수

5. 2. 대칭 2-디자인 (SBIBD)

피셔 부등식에서 등식이 성립하는 경우, 즉 점과 블록의 수가 같은 2-설계를 '''대칭 설계'''라고 한다.^[9] 대칭 설계는 동일한 점의 수를 가진 모든 2-설계 중에서 가장 적은 수의 블록을 가진다.

대칭 설계에서는 ''r'' = ''k''와 ''b'' = ''v''가 성립하며, 일반적으로 임의의 2-설계에서는 성립하지 않지만, 대칭 설계에서는 서로 다른 두 개의 블록이 정확히 ''λ''개의 점에서 만난다.^[10] 라이저의 정리는 역을 제공한다. ''X''가 ''v''-원소 집합이고, ''B''가 ''k''-원소 부분 집합("블록")의 ''v''-원소 집합이며, 서로 다른 두 개의 블록이 정확히 λ개의 점을 공유한다면, (''X, B'')는 대칭 블록 설계이다.^[11]

대칭 설계의 매개변수는 다음을 만족한다.

:λ(''v''-1) = ''k''(''k''-1).

이는 ''v''에 대한 강한 제약을 가하므로 점의 수는 임의적이지 않다. 브루크-라이저-초울라 정리는 이러한 매개변수를 사용하여 대칭 설계의 존재에 대한 필요 조건(충분 조건은 아님)을 제공한다.

다음은 대칭 2-설계의 중요한 예시이다.

크기 ''m''인 아다마르 행렬은 ±1을 원소로 갖는 ''m'' × ''m'' 행렬 '''H'''로, '''HH'''^⊤ = m'''I'''_m을 만족한다. 여기서 '''H'''^⊤는 '''H'''의 전치 행렬이고 '''I'''_''m''은 ''m'' × ''m'' 단위 행렬이다. 아다마르 행렬은 첫 번째 행과 첫 번째 열의 모든 항목이 +1인 형태로 ''표준화 형태''로 만들 수 있다(즉, 동등한 아다마르 행렬로 변환될 수 있다). 크기 ''m'' > 2인 경우, ''m''은 4의 배수여야 한다.

표준화된 형태의 크기가 4''a''인 아다마르 행렬이 주어지면, 첫 번째 행과 첫 번째 열을 제거하고 모든 −1을 0으로 변환한다. 결과적인 0–1 행렬 '''M'''은 '''아다마르 2-설계'''라고 하는 대칭 2-(4''a'' − 1, 2''a'' − 1, ''a'' − 1) 사건 행렬이다.^[20] 이 설계는 4''a''-1개의 블록/점을 포함하며, 각 블록은 2''a''-1개의 점/블록을 포함하거나 포함된다. 점들의 각 쌍은 정확히 ''a''-1개의 블록에 포함된다.

이 구성은 가역적이며, 이러한 매개변수를 가진 대칭 2-설계의 사건 행렬은 크기가 4''a''인 아다마르 행렬을 형성하는 데 사용될 수 있다.

5. 3. 가분 2-디자인

'''가분 2-설계'''는 블록을 ''평행 클래스''라는 집합으로 분할할 수 있는 BIBD이며, 각 평행 클래스는 BIBD의 점 집합의 분할을 이룬다. 이러한 평행 클래스들의 집합을 설계의 ''분해''라고 한다.^[21]

2-(''v'',''k'',λ) 가분 설계에서 ''c''개의 평행 클래스가 존재하면, ''b'' ≥ ''v'' + ''c'' − 1 이다.^[21]

따라서, 대칭 설계는 하나 이상의 평행 클래스를 갖는 비자명 분해를 가질 수 없다.^[22]

가분 2-설계의 대표적인 예시는 유한 아핀 평면이다. 15명의 여학생 문제에 대한 해는 2-(15,3,1) 설계의 분해이다.^[23]

5. 4. 일반 균형 디자인 (t-디자인)

t-design|t-디자인^영어은 모든 t개의 점들의 집합이 동일한 수(λ)의 블록에 포함되는 설계이다.

세 자연수

t,k,n\in\mathbb N

가 주어졌을 때, '''

(t,k,n)

-블록 설계'''

(X,\mathcal B)

는 다음과 같은 데이터로 구성된다.

크기 $n$ 의 유한 집합 $X$ . 그 원소는 '''점'''이라고 한다.
$X$ 의, 크기 $k$ 의 부분 집합들의 족 $\mathcal B\subseteq\operatorname{Pow}_k(X)$ . 그 원소를 '''블록'''이라고 한다.

이는 다음 조건을 만족시켜야 한다.

$t$ 개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값 $\lambda_t>0$ 이다.

\lambda_t=1

인

(t,k,n)

-블록 설계는 '''

(t,k,n)

-슈타이너 계'''라고 하며,

\operatorname S(t,k,n)

로 표기된다.

2 이상의 정수 ''t''에 대해, '''''t''-디자인'''은 다음 조건을 만족하는 설계이다.

임의의 서로 다른 ''t''개의 점에 대해, 그 ''t''개의 점을 모두 포함하는 블록은 정확히 λ개이다.

''t''-(''v'', ''k'', 1)-디자인은 슈타이너 시스템이라고 하며, ''S''(''t'', ''k'', ''v'')로 표기된다.

임의의 양의 정수 ''t''에 대해, ''t''-디자인 ''B''는 ''X''의 ''k''-원소 부분 집합들의 집합으로, ''블록''이라고 불린다. ''X''의 모든 점 ''x''는 정확히 ''r''개의 블록에 나타나고, 모든 ''t''-원소 부분 집합 ''T''는 정확히 λ개의 블록에 나타난다. ''v''(''X''의 원소의 수), ''b''(블록의 수), ''k'', ''r'', λ, ''t''는 디자인의 ''매개변수''이다.

디자인의 매개변수는 다음과 같다.

파라미터	설명
v	점의 개수
b	블록의 개수
r	어떤 점을 포함하는 블록의 개수
k	하나의 블록에 포함된 점의 개수
λ	서로 다른 t개의 점을 포함하는 블록의 개수

5. 5. 부분 균형 디자인 (PBIBD)

부분 균형 불완전 블록 설계(PBIBD)는 점들 간의 관계를 나타내는 결합 도식을 이용하여 정의된다.^[42]^[43]

''n''개의 연관 클래스를 갖는 '''부분 균형 불완전 블록 설계'''(PBIBD(''n''))는 크기가 ''k''인 ''b''개의 블록을 갖고, 각 원소가 ''r''개의 블록에 나타나는 ''v''-집합 X를 기반으로 하는 블록 설계이다. 이때 ''X''에 정의된 ''n''개의 클래스를 갖는 결합 도식이 있어서, 원소 ''x''와 ''y''가 ''i''번째 연관 원소(1 ≤ ''i'' ≤ ''n'')이면 정확히 λ_i개의 블록에 함께 존재한다.

PBIBD(''n'')은 결합 도식을 결정하지만, 그 역은 성립하지 않는다.^[30]
예시집합 ''X'' = {1,2,3,4,5,6}에 대한 3개의 연관 클래스를 갖는 연관 체계 ''A''(3)은 다음과 같다. (''i'',''j'') 항목은 요소 ''i''와 ''j''가 R_s 관계에 있는 경우 ''s''이다.

	1	2	3	4	5	6
1	0	1	1	2	3	3
2	1	0	1	3	2	3
3	1	1	0	3	3	2
4	2	3	3	0	1	1
5	3	2	3	1	0	1
6	3	3	2	1	1	0

''A''(3)을 기반으로 하는 PBIBD(3)의 블록은 다음과 같다.

124	134	235	456
125	136	236	456

이 PBIBD(3)의 매개변수는 ''v'' = 6, ''b'' = 8, ''k'' = 3, ''r'' = 4 이고, λ₁ = λ₂ = 2, λ₃ = 1 이다. 또한 연관 체계의 경우 ''n''₀ = ''n''₂ = 1 이고 ''n''₁ = ''n''₃ = 2 이다.^[31]

PBIBD(''m'')의 매개변수는 다음 조건을 만족한다:^[32]

# $vr = bk$

# $\sum_{i=1}^m n_i = v-1$

# $\sum_{i=1}^m n_i \lambda_i = r(k-1)$

# $\sum_{u=0}^m p_{ju}^h = n_j$

# $n_i p_{jh}^i = n_j p_{ih}^j$

PBIBD(1)은 BIBD이며, λ₁ = λ₂인 PBIBD(2)는 BIBD이다.^[33]

PBIBD(2)는 가장 간단하고 유용하기 때문에 가장 많이 연구되었다. PBIBD(2)는 6가지 유형으로 나뉜다:^[36]

# 그룹 가분

# 삼각

# 라틴 방격형 유형

# 순환

# 부분 기하학 유형

# 기타

6. 예시

파노 평면 (유한체 F|'''F'''₂^영어 위의 사영 평면)은 (2,3,7)-슈타이너 계를 이룬다.

점의 수: 7개 ( $n=7$ )
블록 내 점의 수: 3개 ( $k=3$ )
블록의 수: 7개 ( $\lambda_0=7$ )
한 점을 포함하는 블록의 수: 3개 ( $\lambda_1=3$ )
서로 다른 두 점을 포함하는 블록의 수: 1개 ( $\lambda_2=1$ )^[8]

이진 골레 부호는 759개의 옥타드(값이 1인 성분이 8개인 벡터)를 가지며, 각 옥타드를

\{1,2,\dotsc,24\}

의 크기 8의 부분 집합으로 여겨 (5,8,24)-슈타이너 계를 이룬다. 이를 '''비트 설계'''(Witt設計, Witt design^영어)라고 한다.

아다마르 행렬 (

4m\times 4m

, 첫 열과 행은 모두 1)에서 첫 열과 행을 제거하고, -1을 0으로 치환하면 아다마르 설계 (

\lambda_2=m-1

인

(2,2m,4m-1)

-블록 설계)를 얻는다.^[20]

임의의 유한 집합

X

와 양의 정수

1\le k\le|X|

에 대하여,

(X,\operatorname{Pow}_k(X))

는

\textstyle (k, k, |X|)

-블록 설계를 이룬다.

7. 역사

1844년에 영국의 보험계리인 웨슬리 스토커 바커 울하우스(Wesley Stoker Barker Woolhouse^영어, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》(Lady’s and Gentleman’s Diary^영어)에서 블록 설계에 대한 퍼즐을 제시하였다.^[47] 이는 현대적 용어로는

(q,p,n)

-슈타이너 계를 다루는 것이다.

1847년에 영국의 잉글랜드 성공회 사제 토머스 페닝턴 커크먼(Thomas Penyngton Kirkman^영어, 1806~1895)이 이 문제를 해결하였다.^[48] 그러나 이들의 논문은 크게 관심을 불러일으키지 못했다.

1853년에 야코프 슈타이너가 울하우스와 커크먼과 독자적으로 블록 설계에 대한 논문을 출판하였다.^[49] 이후 그의 이름을 따

\lambda_t=1

인

t

-블록 설계는 “슈타이너 계”로 불리게 되었다.

1940년에 로널드 피셔가 피셔 부등식을 증명하였다.^[52]

8. 응용

블록 설계는 실험계획법에서 시작되었으며, 특히 분산 분석 기법을 적용할 때 유용하다. 이러한 설계는 생물학적 응용 분야에서 기원했지만, 소프트웨어 테스팅과 같이 체계적인 비교가 필요한 다양한 분야에서 사용된다.^[37] 블록 설계의 접속 행렬은 오류 정정 부호로 사용되는 블록 부호의 소스를 제공하며, 접속 행렬의 행은 펄스 위치 변조의 기호로도 사용된다.^[37]

예를 들어, 피부암 연구자들이 세 가지 다른 자외선 차단제를 테스트하는 경우, 한 피험자의 손등에 두 가지 다른 자외선 차단제를 바르고 UV 방사선 조사 후 피부 자극을 기록할 수 있다. 이 경우 처리 횟수는 3(자외선 차단제)이고 블록 크기는 2(사람당 손)이다.

R의 [https://cran.r-project.org/package=agricolae R-패키지 agricolae]의 ''design.bib'' 함수를 사용하여 BIBD를 생성할 수 있으며, 그 결과는 다음 표와 같다.

플롯	블록	처리
101	1	3
102	1	2
201	2	1
202	2	3
301	3	2
302	3	1

위 표에서 볼 수 있듯이, 균형 불완전 블록 설계를 얻기 위해 3개의 블록, 즉 3명의 피험자가 필요하다. 각 블록은 {2, 3}, {1, 3}, {1, 2}와 같이 구성된다.

해당 사건 행렬은 다음 표와 같다.

처리	블록 A	블록 B	블록 C
1	0	1	1
2	1	0	1
3	1	1	0

각 처리는 2개의 블록에서 발생하므로 r = 2이고, 각 처리 쌍은 하나의 블록에서만 동시에 나타나므로 λ = 1이다.

이 예시와 같이 테스트할 자외선 차단제가 3개이지만 각 사람에게 손이 2개밖에 없는 경우, 완전한 설계(각 블록의 모든 처리)를 사용할 수 없다.

참조

_[1] 서적
_[2] 서적
_[3] 간행물 On balanced incomplete-block designs with repeated blocks 2007-10-01
_[4] 문서
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 서적
_[9] 문서
_[10] 서적
_[11] 서적
_[12] 서적
_[13] 서적
_[14] 서적
_[15] 서적
_[16] 인용 From Biplanes to the Klein quartic and the Buckyball http://www.neverendi[...] 2008-04-17
_[17] 서적
_[18] 서적
_[19] 서적
_[20] 서적
_[21] 서적
_[22] 서적
_[23] 서적
_[24] 서적
_[25] 서적
_[26] 서적
_[27] 서적
_[28] 서적
_[29] 서적
_[30] 서적
_[31] 서적
_[32] 서적
_[33] 서적
_[34] 서적
_[35] 문서
_[36] harvnb
_[37] 논문 Expurgated PPM Using Symmetric Balanced Incomplete Block Designs 2012-07
_[38] 서적 Design theory. Volume 1 Cambridge University Press
_[39] 서적 Design theory. Volume 2 Cambridge University Press
_[40] 서적 Combinatorial designs: constructions and analysis https://archive.org/[...] Springer-Verlag
_[41] 서적 Block designs: analysis, combinatorics and applications World Scientific
_[42] 서적 Theory of association schemes Springer-Verlag
_[43] 저널 Association schemes and coding theory 1998-10
_[44] 저널 On ''t''-designs https://projecteucli[...] 1975
_[45] 저널 The nonexistence of certain finite projective planes
_[46] 저널 Combinatorial problems https://archive.org/[...]
_[47] 저널 XV. Or PRIZE QUEST. (1733) https://babel.hathit[...] 1844
_[48] 저널 On a problem in combinations 1847
_[49] 저널 11. Combinatorische Aufgabe http://resolver.sub.[...]
_[50] 저널 Tactical configurations of rank two https://archive.org/[...]
_[51] 저널 Die 5-Fach transitiven Gruppen von Mathieu 1938
_[52] 저널 An examination of the different possible solutions of a problem in incomplete blocks 1940-01

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com